§4 連續Markov

C1 連續Markov

1）連續Markov：$P\{X(t+s) = j|X(t) = i ,X(u)=x(u),u\in[0,s)\}=P\{X(t+s)=j|X(t) =i\}$

• 狀態連續停留時間$\sim e(v_i)$，$v_i$稱轉移速率
• 記離開狀態$i$後進入狀態$j$的概率爲$P_{i,j}$，顯然$P_{ii}=0$

2）平穩/時齊性：$P\{X(t+s)=j|X(t)=i\}$獨立於s

3）生滅過程：系統個體數爲$n$時，下一次增加1的時間$\sim e(\lambda_n)$，下一次減少1的時間$\sim e(\mu_n)$

• $v_i = \lambda_i+\mu_i$

• $P_{i,i+1}=\frac{\lambda_i}{\lambda_i+\mu_i};P_{i,i-1}=\frac{\mu_i}{\lambda_i+\mu_i};P_{01}=1$

• 泊松過程$\forall n\ge0,\mu_n=0,\lambda_n=\lambda$

• 純生過程$\forall n\ge 0,\mu_n=0$

• 帶移民線性增長模型：$\lambda_n = n\lambda+\theta_1;\mu_n=n\mu+\theta_2$

  記$M(t) = E[X(t)]$，取條件於$X(t)$，有$M(t+h) = E[E[X(t+h)|X(t)]]$

  由於$X(t+h)=\begin{cases}X(t)+1,p_{+1}=(\lambda X(t)+\theta_1)h+o(h)\\X(t)-1,p_{-1}=(\mu X(t)+\theta_2)h+o(h)\\X(t),p_0\end{cases}$

  有$M(t+h)=M(t)+(\lambda-\mu)X(t)h+(\theta_1-\theta_2)h+o(h)$

  解$M'(t) = (\lambda-\mu)M(t)+\theta_1-\theta_2$可得$M'(t)$

• 記$T_i$爲$i\to i+1$的時間，有$ET_i = \begin{cases}\frac{1-(\lambda/\mu)^{i+1}}{\lambda-\mu},\lambda\neq\mu\\\frac{i+1}{\lambda},\lambda=\mu\end{cases}$

C2 狀態轉移概率函數

1）狀態轉移概率函數：在狀態$i$下$t$時間後處於$j$的概率，記爲$P_{ij}(t)$

2）純生過程：若$i\neq j$時$\lambda_i\neq \lambda_j$

• $P\{X(t)\lt j\} = P\{\sum\limits_{k=i}^{j-1}T_k\gt t\}$

  • $j\gt i$時由亞指數分佈得$P\{X(t)<j|X(0)=i\}=\sum\limits_{k=i}^{j-1}e^{-\lambda_kt}\prod\limits_{r\neq k,r=i}^{j-1}\frac{\lambda_r}{\lambda_r-\lambda_k}\implies P_{ij}(t)$
  • 按柯爾莫哥洛夫方程積分得$P_{ij}(t) = \lambda_{j-1}e^{-\lambda_j t}\int_0^t e^{\lambda_j s}P_{i,j-1}(s)\mathrm{d}s$
  • $P_{ii} = e^{-\lambda_i t}$

• 尤爾過程：$\lambda_n = n\lambda$，得$P_{ii} = e^{-i\lambda t},P_{ij}(t) =C_{j-1}^{i-1}e^{-i\lambda t}(1-e^{-\lambda t})^{j-i}$

  等價問題推導：投擲正面概率爲$e^{-\lambda t}$的硬幣，在時刻$t$得到第$i$次正面

  由公式推導：
  $\begin{aligned} &\sum\limits_{k=i}^{j}e^{-\lambda_kt}\prod\limits_{r\neq k,r=i}^{j}\frac{\lambda_r}{\lambda_r-\lambda_k}- \sum\limits_{k=i}^{j-1}e^{-\lambda_kt}\prod\limits_{r\neq k,r=i}^{j-1}\frac{\lambda_r}{\lambda_r-\lambda_k}\\ &=\sum\limits_{k=i}^{j}e^{-k\lambda t}\prod\limits_{r\neq k,r=i}^{j}\frac{r}{r-k}- \sum\limits_{k=i}^{j-1}e^{-k\lambda t}\prod\limits_{r\neq k,r=i}^{j-1}\frac{r}{r-k}\\ &=e^{-j\lambda t}\prod\limits_{r\neq j,r=i}^{j}\frac{r}{r-j}+\sum\limits_{k=i}^{j-1}e^{-k\lambda t}(\prod\limits_{r\neq k,r=i}^{j}\frac{r}{r-k} -\prod\limits_{r\neq k,r=i}^{j-1}\frac{r}{r-k})\\ &=(-1)^{j-i}e^{-j\lambda t} +\sum\limits_{k=i}^{j-1}e^{-k\lambda t}\frac{k}{j-k}\prod_{r\neq k,r=i}^{j-1}\frac{r}{r-k}\\ &=(-1)^{j-i}e^{-j\lambda t} +\sum\limits_{k=i}^{j-1}e^{-k\lambda t}(-1)^{k-i}\frac{(j-1)!}{(k-i)!(j-k)!(i-1)!}\\ &=(-1)^{j-i}e^{-j\lambda t} +\sum\limits_{k=i}^{j-1}e^{-k\lambda t}\frac{(j-1)!}{(i-1)!(j-i)!}(-1)^{k-i}C_{j-i}^{k-i}\\ &=(-1)^{j-i}e^{-j\lambda t} +C_{j-1}^{i-1}\sum\limits_{k=i}^{j-1}C_{j-i}^{k-i}(-1)^{k-i}e^{-k\lambda t} \\ &=(-1)^{j-i}e^{-j\lambda t} +C_{j-1}^{i-1}e^{-i\lambda t}\sum\limits_{k=0}^{j-i-1}C_{j-i}^{k}(-1)^{k}e^{-k\lambda t} \\ &=C_{j-1}^{i-1}e^{-i\lambda t}(1-e^{-\lambda t})^{j-i} \end{aligned}$

3）瞬時轉移率：$q_{ij} = v_iP_{ij}$

• $v_i = \sum\limits_j v_iP_{ij}=\sum\limits_j q_{ij}$
• $\lim\limits_{h\to 0}\frac{1-P_{ii}(h)}{h}=v_i;\lim\limits_{h\to 0}\frac{P_{ij}(h)}{h}=q_{ij}$

4）C-K方程：$\forall s,t\ge 0:P_{ij}(s+t) = \sum\limits_k P_{ik}(s)P_{kj}(t)$

• 柯爾莫哥洛夫向後方程(KBE)：$P'_{ij}(t) =-v_iP_{ij}(t) +\sum\limits_{k\neq i}q_{ik}P_{kj}(t)$，要求求和與極限可換

  證明：$\frac{P_{ij}(s+t)-P_{ij}(t)}{s} =-(1-P_{ii}(s))P_{ij}(t)+ \sum\limits_{k\neq i}P_{ik}(s)P_{kj}(t)$

  當求和與極限可換易證

• 柯爾莫哥洛夫向前方程(KFE)：$P'_{ij}(t) =-v_jP_{ij}(t) +\sum\limits_{k\neq j}q_{kj}P_{jk}(t)$

• 聯立求解一階微分方程組即可求出轉移概率

C3 極限概率

1）連續Markov在時刻$t$處於$i$的狀態收斂於一定值$P_j$，即長程比例/平穩概率

2）若極限概率收斂，則$\lim\limits_{t\to \infin}P_{ij}(t) = P_j$

• 充分條件：狀態間互通且正常返

3）求極限概率：

• 若極限與求和可換則$\lim\limits_{t\to \infin}P'_{ij}(t) = -v_jP_j +\sum\limits_{k\neq j}\lim\limits_{t\to\infin}q_{kj}P_{jk}(t)=-v_jP_j+\sum\limits_{k\neq i}q_{kj}P_k$
• 由於$P(t)$有界，故$\lim\limits_{t\to \infin} P'_{ij}(t)= 0$，得$v_jP_j=\sum\limits_{k\neq i} q_{kj}P_k$，稱平衡方程(進出速率相等)
• 聯立$\begin{cases} v_jP_j=\sum\limits_{k\neq i} q_{kj}P_k\\\sum\limits_i P_j = 1\end{cases}$可求得極限概率
  • 生滅過程：$P_0 = \frac{1}{1+\sum\limits_{n=1}^\infin\prod\limits_{k=1}^n\frac{\lambda_{k-1}}{\mu_k}},P_n =\frac{\lambda_{n-1}}{\mu_n}P_{n-1}$，收斂條件：$\sum\limits_{n=1}^\infin\prod\limits_{k=1}^n\frac{\lambda_{k-1}}{\mu_k}$收斂
  • M/M/1排隊系統$P_i = (\frac{\lambda}{\mu})^i(1-\frac{\lambda}{\mu})$
• 事實上可得出矩陣方程$P'(t) = RP(t)\implies P(t) = e^{R(t)}$
  • 直接求解存在舍入誤差
  • 近似方式：$e^{R(t)} = \lim\limits_{n\to \infin}(E+\frac{R(t)}{n})^n=\lim\limits_{n\to\infin}(E-\frac{R(t)}{n})^{-n}$

C4 時間可逆性

1）嵌入鏈：僅記錄連續Markov過程狀態序列，不記時間的Markov鏈

2）定理：記嵌入鏈平穩概率爲$\pi$，則有$P_i = \frac{\pi_iv_i}{\sum\limits_j \pi_j v_j}$

證明：$v_iP_i = \sum\limits_{j\neq i}q_{ji}P_j=\sum\limits_{j}v_jP_{ji}P_j$，故原式成立只需$\pi_i = \sum\limits_j \pi_jP_{ji}$

3）定理：連續Markov過程的逆過程也是連續Markov過程，且$Q_{ij} = \frac{\pi_jP_{ji}}{\pi_i}$，且$v_i,P_i$不變

• 若可求得$q'_{ij},P_i\ge 0$使得$\begin{cases}P_i q'_{ij} = P_jq_{ji},i\neq j\\\sum\limits_{j\neq i}q'_{ij}=\sum\limits_{j\neq i}q_{ij}\\\sum\limits_iP_i=1\end{cases}$，則$q'_{ij}$是倒逆鏈瞬時轉移速率，而$P_i$是極限概率

4）時間可逆性：嵌入鏈可逆$\pi_i P_{ij} = \pi_j P_{ji}\iff P_iq_{ij}=P_jq_{ji}$雙向轉移速率相等

• 遍歷生滅過程時間可逆$\implies$M/M/s服務系統中若$\lambda\lt s\mu$，則輸出是速率爲$\lambda$的泊松過程
• $\begin{cases}P_iq_{ij}=P_jq_{ji}\\\sum\limits_i P_i = 1\end{cases}$若有解$P_i$，則Markov鏈可逆，且$P_i$是極限概率

5）截止：將$i\in A,j\neq A$的$q_{ij}$設定爲0，即不允許轉移出$A$

• 易證，若Markov時間可逆，則截止鏈也時間可逆，且極限概率$P'_j = \frac{P_j}{\sum\limits_{i\in A}P_i}$
• 截止於${1,2,\dots,N}$的M/M/1排隊系統有$P_i =\frac{(\lambda/\mu)^i}{\sum\limits_{j=1}^N(\lambda/\mu)^j}$

6）命題：若過程$X_i(t)$獨立時間可逆，則向量過程$(X_1(t),\dots,X_n(t))$也時間可逆

C5 均勻化

1）均勻化：若$\forall v_i<v$，令$P_{ij}' = \begin{cases} 1-\frac{v_i}{v},j=i\\\frac{v_i}{v}P_{ij},j\neq i\end{cases}$，稱均勻化概率

• 此時$P_{ij}(t) = \sum\limits_{n=0}^\infin P'^n_{ij} e^{-vt}\frac{(vt)^n}{n!}$