随机过程 Markov 链（下）

Markov 链的应用

群体消失模型（分支过程）

考虑一个没有性别的群体，每个个体生命结束时以概率 p j ( j = 0 , 1 , 2 , ⋯ ) p_j\\,(j=0,\\,1,\\,2,\\,\\cdots) pj​(j=0,1,2,⋯) 产生 $j$ 个新的后代，与别的个体产生的后代个数相互独立。初始个体数 X 0 X_0 X0​ ，此 Markov 链 { X n , n = 0 , 1 , 2 , ⋯ } \\{X_n,\\,n=0,\\,1,\\,2,\\,\\cdots\\} {Xn​,n=0,1,2,⋯} 称为分支过程。

首先假设 X 0 = 1 X_0=1 X0​=1 ，即：
X n = ∑ i = 1 X n − 1 Z n − 1 , i X_n=\\sum\\limits_{i=1}^{X_{n-1}}Z_{n-1,\\,i} Xn​=i=1∑Xn−1​​Zn−1,i​
其中 Z n , i Z_{n,\\,i} Zn,i​ 代表第 $n$ 代的第 $i$ 个成员的后代个数。

首先来考虑第 $n$ 代的平均个体数 E ( X n ) E(X_n) E(Xn​) 。令每个个体后代数目均值 μ = ∑ i = 0 ∞ i p i \\mu=\\sum\\limits_{i=0}^{\\infty}ip_i μ=i=0∑∞​ipi​ 对 X n X_n Xn​ 取条件期望，有：
E ( X n ) = E [ E ( X n ∣ X n − 1 ) ] = μ E ( X n − 1 ) = ⋯ = μ n \\begin{align} E(X_n)=&\\,E[E(X_n|X_n-1)] \\\\ =&\\, \\mu E(X_{n-1}) \\\\ =&\\,\\cdots \\\\ =&\\,\\mu^n \\end{align} E(Xn​)====​E[E(Xn​∣Xn​−1)]μE(Xn−1​)⋯μn​​

• 若 $\mu <1$ ，则平均个体数单调下降趋于 $0$ ；
• 若 $\mu =1$ ，则各代平均个体数相同；
• 若 $\mu >1$ ，平均个体数按指数阶上升至无穷。

下面考虑群体最终会消亡的概率 π 0 \\pi_0 π0​ 。对第一代个体数取条件，得：
π 0 = P ( 群体消亡 ) = ∑ j = 0 ∞ P ( 群体消亡 ∣ X 1 = j ) ⋅ p j = ∑ j = 0 ∞ π 0 j p j \\begin{align} \\pi_0=&\\,P(\\text{群体消亡}) \\\\ =&\\,\\sum\\limits_{j=0}^{\\infty}P(\\text{群体消亡}|X_1=j)\\cdot p_j \\\\ =&\\,\\sum\\limits_{j=0}^{\\infty}\\pi_0^{j}p_j \\end{align} π0​===​P(群体消亡)j=0∑∞​P(群体消亡∣X1​=j)⋅pj​j=0∑∞​π0j​pj​​​
可以认为第一代的每个个体是一个群体的开端，则最终灭绝的概率为每一个群体都灭绝，即 π 0 j \\pi_0^j π0j​ （有点更新方程的意思）。

Th：设 0 < p 0 < 1 0\\lt p_0 \\lt 1 0<p0​<1 ， π 0 = 1 \\pi_0=1 π0​=1 的充要条件为 $\mu \le 1$ ；

（当然 p 0 = 1 p_0=1 p0​=1 一定会灭绝， p 0 = 0 p_0=0 p0​=0 一定不会灭绝，我们不考虑这两种平凡的情况）

记 F ( π 0 ) = ∑ j = 0 ∞ π 0 j p j F(\\pi_0)=\\sum\\limits_{j=0}^{\\infty}\\pi_0^j p_j F(π0​)=j=0∑∞​π0j​pj​ ，则 π 0 = F ( π 0 ) \\pi_0=F(\\pi_0) π0​=F(π0​) 代表 $y=x$ 和 $y=F(x)$ 两条曲线的交点。比如 $(1,1)$ 显然是一个交点；当 p 0 + p 1 = 1 p_0+p_1=1 p0​+p1​=1 时，$y=F(x)$ 就是一条直线；一般情况下， p 0 + p 1 < 1 p_0+p_1\\lt 1 p0​+p1​<1，有：
F ′ ( x ) = ∑ j = 1 ∞ j x j − 1 p j > 0 , 0 < x < 1 F ′ ′ ( x ) = ∑ j = 2 ∞ j ( j − 1 ) x j − 2 p j > 0 , 0 < x < 1 \\begin{align} F'(x)=&\\, \\sum\\limits_{j=1}^{\\infty}jx^{j-1}p_j \\gt 0 ,\\quad 0 \\lt x \\lt 1 \\\\ F''(x)=&\\, \\sum\\limits_{j=2}^{\\infty}j(j-1)x^{j-2}p_j \\gt 0 ,\\quad 0 \\lt x \\lt 1 \\end{align} F′(x)=F′′(x)=​j=1∑∞​jxj−1pj​>0,0<x<1j=2∑∞​j(j−1)xj−2pj​>0,0<x<1​​
因此 $F(x)$ 是一个单调递增的 convex 函数：

• 当 p 0 + p 1 = 1 p_0+p_1=1 p0​+p1​=1 时，只有一个交点 $(1,1)$ ，即 π 0 = 1 \\pi_0=1 π0​=1 ，该群体必然会消亡；此时也有 μ = ∑ j = 0 ∞ j p j = p 1 < 1 \\mu=\\sum\\limits_{j=0}^{\\infty}jp_j=p_1\\lt 1 μ=j=0∑∞​jpj​=p1​<1 ；

• 当 p 0 + p 1 < 1 p_0+p_1 \\lt 1 p0​+p1​<1 时，$y=F(x)$ 与 $y=x$ 可能会有至多两个交点，其中一个交点为 $(1,1)$ ，另一个交点可能在 $[0,1)$ ，也可能在 $(1,\infty )$ ；由于 π 0 \\pi_0 π0​ 代表概率，所以只有可能出现在 $[0,1]$ 中

  • $[0,1)$ 时，存在一个交点 $(s,s)$ 且 $s=F(s)$ ，可以用归纳法证明 π 0 \\pi_0 π0​ 是 $s$ 而不是 $1$ ：

    我们假设 $\pi$ 是 { π ∣ F ( x ) = x } \\{\\pi\\,|\\,F(x)=x\\} {π∣F(x)=x} 集合中的元素，即交点构成的集合中的其中一个交点：

    ① 当 $n=1$ 时（第一代），有：
    π = ∑ j = 0 ∞ π j p j ≥ π 0 p 0 = p 0 = P ( X 1 = 0 ) \\pi=\\sum\\limits_{j=0}^{\\infty}\\pi^jp_j\\geq \\pi^0p_0=p_0=P(X_1=0) π=j=0∑∞​πjpj​≥π0p0​=p0​=P(X1​=0)
    ② 假设 π ≥ P ( X n = 0 ) \\pi\\geq P(X_n=0) π≥P(Xn​=0) ，则：
    P ( X n + 1 = 0 ) = ∑ j = 0 ∞ P ( X n + 1 = 0 ∣ X 1 = j ) ⋅ p j = ∑ j = 0 ∞ P ( X n = 0 ) j ⋅ p j ≤ ∑ j = 0 ∞ π j ⋅ p j = π \\begin{align} P(X_{n+1}=0)=&\\,\\sum\\limits_{j=0}^{\\infty}P(X_{n+1}=0|X_1=j)\\cdot p_j \\\\ =&\\, \\sum\\limits_{j=0}^{\\infty}P(X_n=0)^j \\cdot p_j \\\\ \\leq &\\, \\sum\\limits_{j=0}^{\\infty}\\pi^j \\cdot p_j=\\pi \\end{align} P(Xn+1​=0)==≤​j=0∑∞​P(Xn+1​=0∣X1​=j)⋅pj​j=0∑∞​P(Xn​=0)j⋅pj​j=0∑∞​πj⋅pj​=π​​
    因此对于任意 $n$ ，都有 π ≥ P ( X n = 0 ) \\pi\\geq P(X_n=0) π≥P(Xn​=0) ，因此 π ≥ lim ⁡ n → ∞ P ( X n = 0 ) = P ( 群体最终会灭绝 ) = π 0 \\pi\\geq\\lim\\limits_{n\\to\\infty}P(X_n=0)=P(\\text{群体最终会灭绝})=\\pi_0 π≥n→∞lim​P(Xn​=0)=P(群体最终会灭绝)=π0​ ，故 π 0 \\pi_0 π0​ 是所有根中最小的，因此是 s

  在这种情况下，群体灭绝的概率不为 1，此时 μ = F ′ ( 1 ) > 1 \\mu=F'(1)\\gt 1 μ=F′(1)>1 （就是说如果有一个小于 1 的交点的话，$y=F(x)$ 在 1 处肯定是向上翘的）

• $(1,\infty )$ 或者没有第二个交点时，只能是 π 0 = 1 \\pi_0=1 π0​=1 ，此时 μ = F ′ ( 1 ) ≤ 1 \\mu=F'(1)\\le 1 μ=F′(1)≤1 （就是说如果有一个大于 1 的交点的话，$y=F(x)$ 在 1 处肯定比 $y=x$ 要更平缓；如果没有其他交点的话，则 $y=F(x)$ 与 $y=x$ 在 1 处相切）

综上，在所有 $y=F(x)$ 与 $y=x$ 的交点情况中，都有 π 0 = 1 ⟺ μ ≤ 1 \\pi_0=1 \\iff \\mu\\le 1 π0​=1⟺μ≤1 ，得证。

人口结构变化的 Markov 链模型

考虑一个社会的教育水平和文化程度的发展变化，将全国 16 岁以上的人口分为 7 个文化水平，结构的变化为升级、退化、进入（16 岁的人变多了）、迁出（移民或去世）。用 ( n 1 ( t ) , n 2 ( t ) , ⋯ , n 7 ( t ) ) (n_1(t),\\,n_2(t),\\,\\cdots,\\,n_7(t)) (n1​(t),n2​(t),⋯,n7​(t)) 表示第 $t$ 年各文化水平的人数， N ( t ) = ∑ i = 1 7 n i ( t ) N(t)=\\sum\\limits_{i=1}^{7}n_i(t) N(t)=i=1∑7​ni​(t) 为第 $t$ 年 16 岁以上的人口总数。

以 q i j q_{ij} qij​ 记每年从 $i$ 级转为 $j$ 级的百分比，则 Q = ( q i j ) 7 × 7 Q=(q_{ij})_{7\\times 7} Q=(qij​)7×7​ 是一个准转矩阵（因为还有迁出的人，因此每行的元素之和 $\le 1$ ）

考虑迁入迁出，以 w i w_i wi​ 记录每年从 $i$ 级迁出占 $i$ 级人数的百分比，则 ∑ j = 1 7 q i j + w i = 1 \\sum\\limits_{j=1}^7q_{ij}+w_i=1 j=1∑7​qij​+wi​=1 ；记 r i r_i ri​ 为每年进入 $i$ 级的人数占总进入人数的比例，则 ∑ i = 1 7 r i = 1 \\sum\\limits_{i=1}^7r_i=1 i=1∑7​ri​=1 ；

记 $R(t)$ 为总进入人数，$W(t)$ 为总迁出人数，则：
N ( t + 1 ) = N ( t ) + R ( t ) − W ( t ) n j ( t + 1 ) = ∑ i = 1 7 n i ( t ) q i j + r j R ( t ) − n j ( t ) w j \\begin{align} N(t+1)=&\\,N(t)+R(t)-W(t) \\\\ n_j(t+1)=&\\,\\sum\\limits_{i=1}^{7}n_i(t)q_{ij}+r_jR(t)-n_j(t)w_j \\end{align} N(t+1)=nj​(t+1)=​N(t)+R(t)−W(t)i=1∑7​ni​(t)qij​+rj​R(t)−nj​(t)wj​​​
令 16 岁以上人口变化为 $M(t)$ ，增长率为 $\alpha$（可能为负增长）：
M ( t ) = N ( t + 1 ) − N ( t ) = R ( t ) − W ( t ) = α N ( t ) α = N ( t + 1 ) N ( t ) − 1 \\begin{align} M(t)=&\\,N(t+1)-N(t)=R(t)-W(t)=\\alpha N(t) \\\\ \\alpha=&\\,\\frac{N(t+1)}{N(t)}-1 \\end{align} M(t)=α=​N(t+1)−N(t)=R(t)−W(t)=αN(t)N(t)N(t+1)​−1​​
于是
各文化水平人数占比 = n j ( t + 1 ) N ( t + 1 ) = N ( t ) N ( t + 1 ) [ ∑ i = 1 7 n i ( t ) N ( t ) q i j + r j R ( t ) N ( t ) − w j n j ( t ) N ( t ) ] = 1 1 + α [ ∑ i = 1 7 n i ( t ) N ( t ) q i j + r j R ( t ) N ( t ) − w j n j ( t ) N ( t ) ] \\begin{align} \\text{各文化水平人数占比}=\\frac{n_j(t+1)}{N(t+1)}=&\\,\\frac{N(t)}{N(t+1)}\\left[ \\sum\\limits_{i=1}^{7}\\frac{n_i(t)}{N(t)}q_{ij}+r_j\\frac{R(t)}{N(t)}-w_j\\frac{n_j(t)}{N(t)} \\right] \\\\ =&\\,\\frac{1}{1+\\alpha}\\left[ \\sum\\limits_{i=1}^{7}\\frac{n_i(t)}{N(t)}q_{ij}+r_j\\frac{R(t)}{N(t)}-w_j\\frac{n_j(t)}{N(t)} \\right] \\end{align} 各文化水平人数占比=N(t+1)nj​(t+1)​==​N(t+1)N(t)​[i=1∑7​N(t)ni​(t)​qij​+rj​N(t)R(t)​−wj​N(t)nj​(t)​]1+α1​[i=1∑7​N(t)ni​(t)​qij​+rj​N(t)R(t)​−wj​N(t)nj​(t)​]​​
记各文化水平人数占比为 a j ( t ) = n j ( t ) N ( t ) a_j(t)=\\frac{n_j(t)}{N(t)} aj​(t)=N(t)nj​(t)​ ，记 a ( t ) = ( a 1 ( t ) , a 2 ( t ) , ⋯ , a 7 ( t ) ) a(t)=(a_1(t),\\,a_2(t),\\,\\cdots,\\,a_7(t)) a(t)=(a1​(t),a2​(t),⋯,a7​(t)) ，则上式写成：
a j ( t + 1 ) = 1 1 + α [ ∑ i = 1 7 a i ( t ) q i j + r j R ( t ) N ( t ) − a i ( t ) w j ] a_j(t+1)=\\frac{1}{1+\\alpha}\\left[ \\sum\\limits_{i=1}^{7}a_i(t)q_{ij}+r_j\\frac{R(t)}{N(t)}-a_i(t)w_j\\right] aj​(t+1)=1+α1​[i=1∑7​ai​(t)qij​+rj​N(t)R(t)​−ai​(t)wj​]
由 R ( t ) = M ( t ) + W ( t ) = α N ( t ) + ∑ j = 1 7 n j ( t ) w j R(t)=M(t)+W(t)=\\alpha N(t)+\\sum\\limits_{j=1}^{7}n_j(t)w_j R(t)=M(t)+W(t)=αN(t)+j=1∑7​nj​(t)wj​ ，则上式写成：
a j ( t + 1 ) = 1 1 + α [ ∑ i = 1 7 a i ( t ) ( q i j + r j w i ) − a i ( t ) w j + α r j ] a_j(t+1)=\\frac{1}{1+\\alpha}\\left[ \\sum\\limits_{i=1}^{7}a_i(t)(q_{ij}+r_jw_i)-a_i(t)w_j +\\alpha r_j \\right] aj​(t+1)=1+α1​[i=1∑7​ai​(t)(qij​+rj​wi​)−ai​(t)wj​+αrj​]
特别地，当 $\alpha =0$ 时，有：
a j ( t + 1 ) = ∑ i = 1 7 a i ( t ) ( q i j + r j w i ) − a i ( t ) w j a_j(t+1)=\\sum\\limits_{i=1}^{7}a_i(t)(q_{ij}+r_jw_i)-a_i(t)w_j aj​(t+1)=i=1∑7​ai​(t)(qij​+rj​wi​)−ai​(t)wj​
记 P ~ = ( p ~ i j ) \\tilde{P}=(\\tilde{p}_{ij}) P~=(p~​ij​) ，其中：
p ~ i j = { q i j + r j w i i ≠ j q j j + r j w j − w j i = j \\tilde{p}_{ij}=\\left \\{ \\begin{array}{l} q_{ij}+r_jw_i & i\\not=j \\\\ q_{jj}+r_jw_j-w_j & i=j \\\\ \\end{array} \\right . p~​ij​={qij​+rj​wi​qjj​+rj​wj​−wj​​i=ji=j​
则上式直接变成 a ( t + 1 ) = a ( t ) ⋅ P ~ a(t+1)=a(t)\\cdot \\tilde{P} a(t+1)=a(t)⋅P~ （这个是矩阵相乘），所以 P ~ \\tilde{P} P~ 才是实际上的 Markov 转移矩阵。

在实际中，我们希望文化水平过低或者过高的人不需要太多，人口结构维持一个合理稳定的水平 a ∗ a^* a∗ 。比如在瓷器国，通过考试可以控制人口进入各级的比例 r = ( r 1 , r 2 , ⋯ , r 7 ) r=(r_1,\\,r_2,\\,\\cdots,\\,r_7) r=(r1​,r2​,⋯,r7​) 来尽快达到这个稳定水平。（后边看不懂，不想看了）

连续时间 Markov 链

定义与性质

连续时间 Markov 链：过程 { X ( t ) , t ≥ 0 } \\{X(t),\\,t\\geq 0\\} {X(t),t≥0} 的状态空间 $S$ 为离散空间（记为 { 0 , 1 , ⋯ } \\{0,\\,1,\\,\\cdots\\} {0,1,⋯} ），若对一切 $s,t\ge 0$ 及 $i,j\in S$ ，有：
$$P(X(t+s)=j|X(s)=i,X(u)=x(u),0\le u\le s)=P(X(t+s)=j|X(s)=i)$$
成立（即将来的状态只和当前的状态有关），则称该过程为连续时间 Markov 链。此时转移概率 p i j ( s , t ) p_{ij}(s,\\,t) pij​(s,t) 为条件概率 $P(X(t+s)=j|X(s)=i)$ ，转移概率矩阵为 P ( s , t ) = ( p i j ( s , t ) ) P(s,\\,t)=(p_{ij}(s,\\,t)) P(s,t)=(pij​(s,t))

时齐 Markov 链：这里的时齐概念有点不一样，若 p i j ( s , t ) p_{ij}(s,\\,t) pij​(s,t) 与 $s$ 无关，简记 p i j ( s , t ) = p i j ( t ) p_{ij}(s,\\,t)=p_{ij}(t) pij​(s,t)=pij​(t) ，相应地记为 P i j ( t ) = ( p i j ( t ) ) P_{ij}(t)=(p_{ij}(t)) Pij​(t)=(pij​(t))

（我们后边也只讨论时齐的 Markov 链）

Th：对于连续时间 Markov 链 { X ( t ) , t ≥ 0 } \\{X(t),\\,t\\geq 0\\} {X(t),t≥0} ，假设时刻 0 过程刚刚到达 $i(i\in S)$ ，以 τ i \\tau_i τi​ 记过程在离开 $i$ 之前停留的时间，则 τ i \\tau_i τi​ 服从指数分布。

证明：之前概率论的时候有学过，连续型随机变量的分布里只有指数分布是具有无记忆性的（可以证明，虽然我证不出来），所以我们只需证明对 $s,t\ge 0$ ，有：
P ( τ i > s + t ∣ τ i > s ) = P ( τ i > t ) P(\\tau_i\\gt s+t|\\tau_i\\gt s)=P(\\tau_i\\gt t) P(τi​>s+t∣τi​>s)=P(τi​>t)
注意到：
{ τ i > s } ⟺ { X ( u ) = i , 0 < u ≤ s ∣ X ( 0 ) = i } { τ i > s + t } ⟺ { X ( u ) = i , 0 < u ≤ s , X ( v ) = i , s < v ≤ s + t ∣ X ( 0 ) = i } \\begin{align} \\{ \\tau_i \\gt s \\} \\iff&\\, \\{ X(u)=i,\\,0\\lt u\\leq s \\,|\\, X(0)=i \\} \\\\ \\{ \\tau_i \\gt s+t \\} \\iff&\\, \\{ X(u)=i,\\,0\\lt u\\leq s ,\\, X(v)=i,\\,s\\lt v \\leq s+t \\,|\\, X(0)=i \\} \\end{align} {τi​>s}⟺{τi​>s+t}⟺​{X(u)=i,0<u≤s∣X(0)=i}{X(u)=i,0<u≤s,X(v)=i,s<v≤s+t∣X(0)=i}​​
则：
P ( τ i > s + t ∣ τ i > s ) = P ( X ( v ) = i , s < v ≤ s + t ∣ X ( u ) = i , 0 < u ≤ s ) = P ( X ( v ) = i , s < v ≤ s + t ) = P ( X ( v ) = i , 0 < v ≤ t ) = P ( τ i > t ) \\begin{align} &\\, P(\\tau_i\\gt s+t|\\tau_i\\gt s) \\\\ =&\\, P(X(v)=i,\\,s\\lt v \\leq s+t \\,|\\, X(u)=i,\\,0\\lt u\\leq s) \\\\ =&\\, P(X(v)=i,\\,s\\lt v \\leq s+t) \\\\ =&\\, P(X(v)=i,\\,0\\lt v \\leq t) \\\\ =&\\, P(\\tau_i \\gt t) \\end{align} ====​P(τi​>s+t∣τi​>s)P(X(v)=i,s<v≤s+t∣X(u)=i,0<u≤s)P(X(v)=i,s<v≤s+t)P(X(v)=i,0<v≤t)P(τi​>t)​​
即 $\tau$ 具有无记忆性，因此服从指数分布，得证。

因此，我们可以从另一种角度理解连续时间 Markov 链：

• 在转移到下一种状态之前，处于状态 $i$ 的时间服从参数为 μ i \\mu_i μi​ 的指数分布；
• 在过程离开状态 $i$ 时，将以概率 p i j p_{ij} pij​ 到达 $j$ ，并且 ∑ j ∈ S p i j = 1 \\sum\\limits_{j\\in S}p_{ij=1} j∈S∑​pij=1​

若 μ i = ∞ \\mu_i=\\infty μi​=∞ ，则状态 $i$ 上停留的时间为 0，称状态 $i$ 为瞬过状态。我们一般假设 Markov 链中不存在瞬过状态（因为瞬过状态其实也可以合并到其他状态上）。

若 μ i = 0 \\mu_i=0 μi​=0 ，则一旦进入状态 $i$ ，停留的平均时间为无限长，这样的状态称为吸收状态。

连续时间 Markov 链是一个做如下运动的随机过程：它以一个 Markov 链的方式在各种状态之间转移，在两次转移之间以指数分布停留。并且这个指数分布仅与当前所处状态有关，而与下一个将要转移的状态独立。

正则性：若一个连续时间 Markov 链以概率 1 在任意有限长的时间内转移的次数是有限的，则称它是正则的。（我去查了一些资料，有些把这个叫做 Feller 性质或者正常性，而正则性指对于所有的初始状态，它们最终都能够达到同一个稳定分布）

正则的连续时间 Markov 链可以得到以下连续性条件：
lim ⁡ t → 0 p i j ( t ) = δ i j = { 1 i = j 0 i ≠ j \\lim\\limits_{t\\to 0} p_{ij}(t)=\\delta_{ij}=\\left\\{ \\begin{array}{l} 1 & i = j \\\\ 0 & i \\not= j \\end{array} \\right. t→0lim​pij​(t)=δij​={10​i=ji=j​

（这一节的例题可以看连续时间 Markov 链的应用，主要是判断某个过程是否是连续时间的 Markov 链，以及如何计算转移概率）

Kolmogorov 微分方程

离散时间 Markov 链的 $n$ 步转移矩阵，可以直接由转移矩阵的 $n$ 次方得到。但是连续时间的就比较复杂，我们先考虑 p i j ( t ) p_{ij}(t) pij​(t) 的一些性质。

连续时间 Markov 链转移概率的性质：

• p i j ( t ) ≥ 0 p_{ij}(t)\\geq 0 pij​(t)≥0 ；
• ∑ j ∈ S p i j ( t ) = 1 \\sum\\limits_{j\\in S}p_{ij}(t)=1 j∈S∑​pij​(t)=1 ；
• C-K 方程： p i j ( t + s ) = ∑ k ∈ S p i k ( t ) p k j ( t ) p_{ij}(t+s)=\\sum\\limits_{k\\in S}p_{ik}(t)p_{kj}(t) pij​(t+s)=k∈S∑​pik​(t)pkj​(t) ；

证明：第一和第二点根据定义显然可以知道。现在证明第三点（其实也挺显然的）：
p i j ( t + s ) = P ( X ( t + s ) = j ∣ X ( 0 ) = i ) = ∑ k ∈ S P ( X ( t + s ) = j , X ( t ) = k ∣ X ( 0 ) = i ) = ∑ k ∈ S P ( X ( t + s ) = j ∣ X ( t ) = k , X ( 0 ) = i ) ⋅ P ( X ( t ) = k ∣ X ( 0 ) = i ) = ∑ k ∈ S P ( X ( t + s ) = j ∣ X ( t ) = k ) p i k ( k ) = ∑ k ∈ S p i k ( k ) p k j ( s ) \\begin{align} p_{ij}(t+s)=&\\, P(X(t+s)=j\\,|\\,X(0)=i) \\\\ =&\\, \\sum\\limits_{k\\in S} P(X(t+s)=j,\\,X(t)=k\\,|\\,X(0)=i) \\\\ =&\\, \\sum\\limits_{k\\in S} P(X(t+s)=j\\,|\\,X(t)=k,\\,X(0)=i)\\cdot P(X(t)=k\\,|\\,X(0)=i) \\\\ =&\\, \\sum\\limits_{k\\in S} P(X(t+s)=j\\,|\\,X(t)=k)p_{ik}(k) \\\\ =&\\, \\sum\\limits_{k\\in S} p_{ik}(k)p_{kj}(s) \\end{align} pij​(t+s)=====​P(X(t+s)=j∣X(0)=i)k∈S∑​P(X(t+s)=j,X(t)=k∣X(0)=i)k∈S∑​P(X(t+s)=j∣X(t)=k,X(0)=i)⋅P(X(t)=k∣X(0)=i)k∈S∑​P(X(t+s)=j∣X(t)=k)pik​(k)k∈S∑​pik​(k)pkj​(s)​​

• 第二行到第三行可以这样理解，记 $A$ 为事件 $X(t+s)=j$ ，$B$ 为事件 $X(t)=k$ ，$C$ 为事件 $X(0)=i$ ，则：

P ( X ( t + s ) = j , X ( t ) = k ∣ X ( 0 ) = i ) = P ( A B ∣ C ) = P ( A B C ) P ( C ) = P ( A ∣ B C ) P ( B ∣ C ) = P ( A B C ) P ( B C ) P ( B C ) P ( C ) = P ( X ( t + s ) = j ∣ X ( t ) = k , X ( 0 ) = i ) P ( X ( t ) = k ∣ X ( 0 ) = i ) \\begin{align} &\\,P(X(t+s)=j,\\,X(t)=k\\,|\\,X(0)=i) \\\\ =&\\,P(AB|C) \\\\ =&\\,\\frac{P(ABC)}{P(C)} \\\\ =&\\,P(A|BC)P(B|C) \\\\ =&\\,\\frac{P(ABC)}{P(BC)}\\frac{P(BC)}{P(C)} \\\\ =&\\, P(X(t+s)=j\\,|\\,X(t)=k,\\,X(0)=i)P(X(t)=k\\,|\\,X(0)=i) \\end{align} =====​P(X(t+s)=j,X(t)=k∣X(0)=i)P(AB∣C)P(C)P(ABC)​P(A∣BC)P(B∣C)P(BC)P(ABC)​P(C)P(BC)​P(X(t+s)=j∣X(t)=k,X(0)=i)P(X(t)=k∣X(0)=i)​​

• 第三行到第四行是 Markov 链的定义，转移概率与过去的状态无关

Th ： q i j q_{ij} qij​ 称为状态 $i$ 转移到状态 $j$ 的转移速率，具有以下性质：（没有证明，估计有点困难）

• lim ⁡ t → 0 1 − p i i ( t ) t = q i i ≤ + ∞ \\lim\\limits_{t\\to 0}\\frac{1-p_{ii}(t)}{t}=q_{ii} \\leq +\\infty t→0lim​t1−pii​(t)​=qii​≤+∞ ；
• lim ⁡ t → 0 p i j ( t ) t = q i j < + ∞ \\lim\\limits_{t\\to 0}\\frac{p_{ij}(t)}{t}=q_{ij} \\lt +\\infty t→0lim​tpij​(t)​=qij​<+∞ ；

推论：对有限状态时齐的连续时间 Markov 链，有：
q i i = ∑ j ≠ i q i j < + ∞ q_{ii}=\\sum\\limits_{j\\not=i}q_{ij} \\lt +\\infty qii​=j=i∑​qij​<+∞
证明：有 ∑ j ∈ S p i j ( t ) = 1 \\sum\\limits_{j\\in S}p_{ij}(t)=1 j∈S∑​pij​(t)=1 ，即 1 − p i i ( t ) = ∑ j ≠ i p i j ( t ) 1-p_{ii}(t)=\\sum\\limits_{j\\not=i}p_{ij}(t) 1−pii​(t)=j=i∑​pij​(t) ，故：（中间有一步交换极限和求和的顺序，因为状态有限，所以可以交换）
lim ⁡ t → 0 1 − p i i ( t ) t = lim ⁡ t → 0 ∑ j ≠ i p i j ( t ) t = ∑ j ≠ i lim ⁡ t → 0 p i j ( t ) t = ∑ j ≠ i q i j < ∞ \\begin{align} \\lim\\limits_{t\\to 0}\\frac{1-p_{ii}(t)}{t} =&\\, \\lim\\limits_{t\\to 0}\\sum\\limits_{j\\not=i}\\frac{p_{ij}(t)}{t} \\\\ =&\\, \\sum\\limits_{j\\not=i}\\lim\\limits_{t\\to 0}\\frac{p_{ij}(t)}{t} \\\\ =&\\, \\sum\\limits_{j\\not=i}q_{ij} \\lt \\infty \\end{align} t→0lim​t1−pii​(t)​===​t→0lim​j=i∑​tpij​(t)​j=i∑​t→0lim​tpij​(t)​j=i∑​qij​<∞​​
Tip：对于无限状态的情况，一般只能得到 q i j ≥ ∑ j ≠ i q i j q_{ij}\\geq \\sum\\limits_{j\\not =i}q_{ij} qij​≥j=i∑​qij​ ；为简单起见，设状态空间为 S = { 1 , 2 , ⋯ } S=\\{1,\\,2,\\,\\cdots\\} S={1,2,⋯} ，此时记：
Q = [ − q 11 q 12 q 13 ⋯ q 1 i ⋯ q 21 − q 22 q 23 ⋯ q 2 i ⋯ ⋮ ⋮ ⋮ ⋮ q i 1 q i 2 q i 3 ⋯ − q i i ⋯ ⋮ ⋮ ⋮ ⋮ ] Q=\\begin{bmatrix} -q_{11} & q_{12} & q_{13} & \\cdots & q_{1i} & \\cdots \\\\ q_{21} & -q_{22} & q_{23} & \\cdots & q_{2i} & \\cdots \\\\ \\vdots & \\vdots & \\vdots & & \\vdots & & \\\\ q_{i1} & q_{i2} & q_{i3} & \\cdots & -q_{ii} & \\cdots \\\\ \\vdots & \\vdots & \\vdots & & \\vdots & & \\\\ \\end{bmatrix} Q= ​−q11​q21​⋮qi1​⋮​q12​−q22​⋮qi2​⋮​q13​q23​⋮qi3​⋮​⋯⋯⋯​q1i​q2i​⋮−qii​⋮​⋯⋯⋯​​ ​
称为连续时间 Markov 链的 Q-矩阵 。当矩阵元素 q i i = ∑ j ≠ i q i j < + ∞ q_{ii}=\\sum\\limits_{j\\not=i}q_{ij} \\lt +\\infty qii​=j=i∑​qij​<+∞ 时，称该矩阵是保守的。