马氏链的定义和示例
- 马氏链的定义和示例
- 1. 马氏链的定义
- 2. 马氏链的示例
- 2.1. 随机游走
- 2.2. 分支过程
- 2.3. Ehrenfest chain
- 2.4. 遗传模型
- 2.5. M/G/1 队列
马氏链的定义和示例
1. 马氏链的定义
对于可数状态空间的马氏链, 马氏性指的是给定当前状态, 其他过去的状态与未来的预测无关. 即对任意状态 i 0 , … i n − 1 , i i_{0}, \ldots i_{n-1}, i i0,…in−1,i, j j j
P ( X n + 1 = j ∣ X n = i , X n − 1 = i n − 1 , … X 0 = i 0 ) = P ( X n + 1 = j ∣ X n = i ) P\left(X_{n+1}=j \mid X_{n}=i, X_{n-1}=i_{n-1}, \ldots X_{0}=i_{0}\right)=P\left(X_{n+1}=j \mid X_{n}=i\right) P(Xn+1=j∣Xn=i,Xn−1=in−1,…X0=i0)=P(Xn+1=j∣Xn=i)
称条件概率 P ( X n + 1 = j ∣ X n = i ) P\left(X_{n+1}=j \mid X_{n}=i\right) P(Xn+1=j∣Xn=i)为马氏链 { X n , n = 0 , 1 , 2 , . . . } \{X_n,n=0,1,2,...\} {Xn,n=0,1,2,...}的一步转移概率, 简称转移概率, 记为 p i j p_{ij} pij, 表示处于状态 i i i的过程下一步转移到状态 j j j的概率.
2. 马氏链的示例
2.1. 随机游走
示例5.1.1 (随机游走的转移概率) 令 ξ 1 , ξ 2 , … ∈ Z d \xi_{1}, \xi_{2}, \ldots \in \mathbf{Z}^{d} ξ1,ξ2,…∈Zd独立, 分布为 μ \mu μ. X n = X 0 + ξ 1 + ⋯ + ξ n X_{n}=X_{0}+\xi_{1}+\cdots+\xi_{n} Xn=X0+ξ1+⋯+ξn, 其中 X 0 X_{0} X0是常数. 则 X n X_{n} Xn是马氏链,转移概率为 p ( i , j ) = μ ( { j − i } ) p(i, j)=\mu(\{j-i\}) p(i,j)=μ({j−i}).
证明: 证明 X n X_{n} Xn是马氏链. 若 μ j \mu_{j} μj是 ξ j \xi_{j} ξj的分布, 由于 X n X_n Xn和 ξ n + 1 \xi_{n+1} ξn+1独立, 则由示例4.1.7 (二元独立随机变量函数关于某变量的条件期望)
P ( X n + 1 ∈ B ∣ X n ) = P ( X n + ξ n + 1 ∈ B ∣ X n ) = μ n + 1 ( B − X n ) P\left(X_{n+1} \in B \mid X_{n}\right)=P\left(X_{n}+\xi_{n+1} \in B \mid X_{n}\right)=\mu_{n+1}\left(B-X_{n}\right) P(Xn+1∈B∣Xn)=P(Xn+ξn+1∈B∣Xn)=μn+1(B−Xn)
故 P ( X n + 1 ∈ B ∣ X n ) ∈ σ ( X n ) ⊂ F P\left(X_{n+1} \in B \mid X_{n}\right)\in \sigma(X_n)\subset \mathcal{F} P(Xn+1∈B∣Xn)∈σ(Xn)⊂F, 由定理4.1.12可得
P ( X n + 1 ∈ B ∣ X n ) = P ( X n + 1 ∈ B ∣ F n ) P\left(X_{n+1} \in B \mid X_{n}\right)=P\left(X_{n+1} \in B \mid \mathcal{F}_{n}\right) P(Xn+1∈B∣Xn)=P(Xn+1∈B∣Fn)
习题5.1.6 (以概率 θ \theta θ正向走, 1 − θ 1-\theta 1−θ负向走的随机游走是一个非时齐的马氏链) 令 θ , U 1 , U 2 , … \theta, U_{1}, U_{2}, \ldots θ,U1,U2,…是 ( 0 , 1 ) (0,1) (0,1)上的独立均匀分布. 若 U i ≤ θ U_{i} \leq \theta Ui≤θ, X i = 1 X_{i}=1 Xi=1; 若 U i > θ U_{i}>\theta Ui>θ, X i = − 1 X_{i}=-1 Xi=−1. S n = X 1 + ⋯ + X n S_{n}=X_{1}+\cdots+X_{n} Sn=X1+⋯+Xn.
- ( i ) (i) (i) 转移概率 P ( X n + 1 = 1 ∣ X 1 , … , X n ) P\left(X_{n+1}=1 \mid X_{1}, \ldots, X_{n}\right) P(Xn+1=1∣X1,…,Xn)只与 S n S_n Sn相关;
- ( i i ) (ii) (ii) S n S_{n} Sn是一个非时齐马尔可夫链. 自然, S n S_{n} Sn是一个估计 θ \theta θ的充分统计量.
证明：(i) 令 i 1 , … , i n ∈ { − 1 , 1 } i_{1}, \ldots, i_{n} \in\{-1,1\} i1,…,in∈{−1,1}, N = ∣ { m ≤ n : i m = 1 } ∣ N=\left|\left\{m \leq n: i_{m}=1\right\}\right| N=∣{m≤n:im=1}∣.
P ( X n + 1 = 1 ∣ X 1 = i 1 , … , X n = i n ) = P ( X 1 = i 1 , … , X n = i n , X n + 1 = 1 ) P ( X 1 = i 1 , … , X n = i n ) ( 重期望公式 ) = ∫ θ N + 1 ( 1 − θ ) n − N d θ ∫ θ N ( 1 − θ ) n − N d θ = ( S n / 2 + n / 2 + 1 ) ! / ( n + 2 ) ! ( S n / 2 + n / 2 ) ! / ( n + 1 ) ! = S n + n + 2 2 n + 4 \begin{aligned} P\left(X_{n+1}=1 \mid X_{1}=i_{1}, \ldots, X_{n}=i_{n}\right)&=\frac{P\left(X_{1}=i_{1}, \ldots, X_{n}=i_{n}, X_{n+1}=1\right)}{P\left(X_{1}=i_{1}, \ldots, X_{n}=i_{n}\right)}\\ (\text{重期望公式})&=\frac{\int \theta^{N+1}(1-\theta)^{n-N} d \theta}{\int \theta^{N}(1-\theta)^{n-N} d \theta}\\ &=\frac{\left(S_{n}/2+n/2+1\right) ! /(n+2) !}{(S_{n}/2+n/2)! /(n+1) !}=\frac{S_{n}+n+2}{2n+4} \end{aligned} P(Xn+1=1∣X1=i1,…,Xn=in)(重期望公式)=P(X1=i1,…,Xn=in)P(X1=i1,…,Xn=in,Xn+1=1)=∫θN(1−θ)n−Ndθ∫θN+1(1−θ)n−Ndθ=(Sn/2+n/2)!/(n+1)!(Sn/2+n/2+1)!/(n+2)!=2n+4Sn+n+2
上式由 ∫ 0 1 x m ( 1 − x ) k d x = m ! k ! / ( m + k + 1 ) ! \int_{0}^{1} x^{m}(1-x)^{k} d x=m ! k ! /(m+k+1) ! ∫01xm(1−x)kdx=m!k!/(m+k+1)!得到.
习题5.1.1. i.i.d序列取值数量序列是马氏链 . 令 ξ 1 , ξ 2 , … ∈ { 1 , 2 , … , N } \xi_{1}, \xi_{2}, \ldots\in\{1,2, \ldots, N\} ξ1,ξ2,…∈{1,2,…,N} i.i.d, 各点取值概率 1 / N 1 / N 1/N. 证明 X n = ∣ { ξ 1 , … , ξ n } ∣ X_{n}=\left|\left\{\xi_{1}, \ldots, \xi_{n}\right\}\right| Xn=∣{ξ1,…,ξn}∣是马氏链, 并计算转移概率.
证明： X n + 1 X_{n+1} Xn+1依赖于 X n X_{n} Xn和 ξ n + 1 \xi_{n+1} ξn+1, 自然是马氏链. 转移概率可以表示为:
p ( k , k + 1 ) = 1 − k N , p ( k , k ) = k N , p ( i , j ) = 0 其他 p(k, k+1)=1-\frac{k}{N}, \quad p(k, k)=\frac{k}{N}, \quad p(i, j)=0 \text {其他} p(k,k+1)=1−Nk,p(k,k)=Nk,p(i,j)=0其他
习题5.1.2.对称随机游走最大值序列不是马氏链 S 0 = 0 , S n = ξ 1 + ⋯ ξ n S_{0}=0, S_{n}=\xi_{1}+\cdots \xi_{n} S0=0,Sn=ξ1+⋯ξn是对称随机游走, X n = max { S m : 0 ≤ m ≤ n } X_{n}=\max \left\{S_{m}: 0 \leq m \leq n\right\} Xn=max{Sm:0≤m≤n}. X n X_{n} Xn不是马氏链.
证明：当 X n = m , X n − 1 = m − 1 X_{n}=m,X_{n-1}=m-1 Xn=m,Xn−1=m−1, 则 X n = S n X_n=S_n Xn=Sn, 故
P ( X n + 1 = m + 1 ∣ X n = m , X n − 1 = m − 1 ) = 1 / 2 \mathbb{P}\left(X_{n+1}=m+1 \mid X_{n}=m, X_{n-1}=m-1\right)=1/2 P(Xn+1=m+1∣Xn=m,Xn−1=m−1)=1/2
当 X n = m , X n − 1 = m X_{n}=m,X_{n-1}=m Xn=m,Xn−1=m, P ( X n + 1 = m + 1 ∣ X n = m , X n − 1 = m ) = 0 \mathbb{P}\left(X_{n+1}=m+1 \mid X_{n}=m, X_{n-1}=m\right)=0 P(Xn+1=m+1∣Xn=m,Xn−1=m)=0, X n X_{n} Xn非马氏链.
2.2. 分支过程
示例 5.1.2 (分支过程的转移概率) S = { 0 , 1 , 2 , … } S=\{0,1,2, \ldots\} S={0,1,2,…}, 第 n n n代每个个体 i i i产生i.i.d的后代数 ξ 1 , ξ 2 , … \xi_{1}, \xi_{2}, \ldots ξ1,ξ2,…, 则 p ( i , j ) = P ( ∑ m = 1 i ξ m = j ) p(i, j)=P(\sum_{m=1}^{i} \xi_{m}=j) p(i,j)=P(∑m=1iξm=j), .
2.3. Ehrenfest chain
示例 5.1.3 (Ehrenfest chain) 第一个瓮有 k k k个球, 第二个瓮有 r − k r-k r−k个, 随机挑选一个球移到另一个瓮中. 令 S = { 0 , 1 , … , r } S=\{0,1, \ldots, r\} S={0,1,…,r}, 第一个瓮中球数的转移概率为
p ( k , k + 1 ) = ( r − k ) / r , p ( k , k − 1 ) = k / r , p ( i , j ) = 0 否则 , p(k, k+1)=(r-k) / r, p(k, k-1)=k / r, p(i, j)=0 \quad \text {否则 }, p(k,k+1)=(r−k)/r,p(k,k−1)=k/r,p(i,j)=0否则 ,Ehrenfest用此模拟两个腔室(大小形状相同,一个小孔连接)间空气分子的划分.
习题5.1.5. 假设左瓮和右瓮, 每个瓮 m m m个球. b b b ( ≤ m \leq m ≤m ) 个黑色球, 2 m − b 2 m-b 2m−b个白色球. 每次从每个瓮中选择一个球然后互相交换. 计算左瓮黑球数的转移概率.
证明： p ( n , n + 1 ) = m − n m ⋅ b − n m , p ( n , n − 1 ) = n m ⋅ m + n − b m p(n, n+1) =\frac{m-n}{m} \cdot \frac{b-n}{m},p(n, n-1) =\frac{n}{m} \cdot \frac{m+n-b}{m} p(n,n+1)=mm−n⋅mb−n,p(n,n−1)=mn⋅mm+n−b
2.4. 遗传模型
示例 5.1.4 (Wright–Fisher遗传模型) 设总体中的个体数为 N N N, 每个个体的基因按基因 A A A 的基因频率的大小, 在下一代中转移成为基因 A A A.
换句话说, 如果在第 n n n代母体中基因 A A A出现了 i i i次, 基因 a a a出现了 N − i N-i N−i次, 则下一代出现基因 A A A的概率为 p i = i N p_{i}=\frac{i}{N} pi=Ni, 而出现基因 a a a 的概率为 1 − p i 1-p_{i} 1−pi.
- (i) 令 X n X_n Xn表示第 n n n代基因 A A A出现的次数, 计算 p i j = P { X n + 1 = j ∣ X n = i } p_{i j}=P\left\{X_{n+1}=j \mid X_{n}=i\right\} pij=P{Xn+1=j∣Xn=i}.
- (ii) 引入变异, 即 A A A在下一代有概率 μ \mu μ是 a a a, 而 a a a在下一代有概率 ν \nu ν是 A A A.
证明：(i) 记 X n X_{n} Xn 为第 n n n 代中携带基因 A A A 的个体数, 则易知 { X n } \left\{X_{n}\right\} {Xn} 是一个状态空间为 S = { 0 , 1 , ⋯ , N } S=\{0,1, \cdots, N\} S={0,1,⋯,N} 的时齐Markov链, 其转移概率矩阵为 P = ( p i j ) \boldsymbol{P}=\left(p_{i j}\right) P=(pij), 其中
p i j = P { X n + 1 = j ∣ X n = i } = C N j p i j ( 1 − p i ) N − j = C N j ( i N ) j ( 1 − i N ) N − j p_{i j}=P\left\{X_{n+1}=j \mid X_{n}=i\right\}=\mathrm{C}_{N}^{j} p_{i}^{j}\left(1-p_{i}\right)^{N-j}=\mathrm{C}_{N}^j\left(\frac{i}{ N}\right)^{j}\left(1-\frac{i}{N}\right)^{N-j} pij=P{Xn+1=j∣Xn=i}=CNjpij(1−pi)N−j=CNj(Ni)j(1−Ni)N−j
在这个模型中,状态 X = 0 X=0 X=0和 N N N对应于总体是 A A A和 a a a,称为吸收状态 (absorbing states), 即 p ( x , x ) = 1 p(x,x)=1 p(x,x)=1. 这个链最终将进入状态 0 0 0或状态 N N N.
(ii) 产生 A A A的概率是 ρ i = ( i / N ) ( 1 − u ) + ( N − i / N ) v \rho_{i}=({i}/{N})(1-u)+({N-i}/{N}) v ρi=(i/N)(1−u)+(N−i/N)v. 转移概率为
p ( i , j ) = ( N j ) ( ρ i ) j ( 1 − ρ i ) N − j p(i, j)=\left(\begin{array}{c} N \\ j \end{array}\right)\left(\rho_{i}\right)^{j}\left(1-\rho_{i}\right)^{N-j} p(i,j)=(Nj)(ρi)j(1−ρi)N−j
如果 u u u和 v v v都是正的, 0 0 0和 N N N就不再是吸收态了,系统可收敛到一个平衡分布.
习题5.1.3 (连续成对的抛硬币序列). 令 ξ 0 , ξ 1 , … ∈ { H , T } \xi_{0}, \xi_{1}, \ldots\in\{H, T\} ξ0,ξ1,…∈{H,T}独立同分布, 每个取值概率为 1 / 2 1 / 2 1/2 (硬币正反面). X n = ( ξ n , ξ n + 1 ) X_{n}=\left(\xi_{n}, \xi_{n+1}\right) Xn=(ξn,ξn+1)是一个马氏链, 计算转移概率 p p p以及 p 2 p^{2} p2.
证明：由于 X n = ( ξ n , ξ n + 1 ) X_{n}=\left(\xi_{n}, \xi_{n+1}\right) Xn=(ξn,ξn+1), 可知 X n − 2 = ( ξ n − 2 , ξ n − 1 ) , ⋯ , X 0 = ( ξ 0 , ξ 1 ) X_{n-2}=\left(\xi_{n-2}, \xi_{n-1}\right), \cdots, X_{0}=\left(\xi_{0}, \xi_{1}\right) Xn−2=(ξn−2,ξn−1),⋯,X0=(ξ0,ξ1)与 X n X_{n} Xn独立,因此 X n X_{n} Xn是马氏链. 易计算得到转移概率 p p p及 p 2 p^{2} p2.
习题5.1.4 (兄弟姐妹结对遗传). 两只动物交配的直系后代中随机选择两个异性个体交配, 过程持续. 假设个体是 A A , A a , a a AA,Aa,aa AA,Aa,aa中的一个, 从每个父母中选择一个字母来决定后代类型, 计算第 n n n代基因型对的转移概率.
证明：该马氏链第 n n n代基因型对共有以下6个状态, 易计算转移概率
A A , A A A A , A a A A , a a A a , A a A a , a a a a , a a A A, A A \quad A A, A a \quad A A, a a \quad A a, A a \quad A a, a a \quad a a, a a AA,AAAA,AaAA,aaAa,AaAa,aaaa,aa
2.5. M/G/1 队列
示例5.1.5. M/G/1 队列:客户 n n n开始服务的队列人数 客户按照速率为 λ \lambda λ的泊松过程到达. 不相交时间间隔内的到达数独立,每个客户服务时长独立,分布为 F F F.
设 X n X_n Xn为第 n n n个客户进入服务时队列的客户数(包括服务中的客户). X 0 = x X_0=x X0=x表示客户 0 0 0刚开始服务时队列有 x x x人. 计算 X n X_n Xn的转移概率.
证明：在一个服务时间内 k k k个顾客到达的概率为 a k a_k ak
a k = ∫ 0 ∞ e − λ t ( λ t ) k k ! d F ( t ) a_{k}=\int_{0}^{\infty} e^{-\lambda t} \frac{(\lambda t)^{k}}{k !} d F(t) ak=∫0∞e−λtk!(λt)kdF(t)
令 ξ i \xi_{i} ξi表示第 i i i次服务时间内到达的客户数减去完成服务的1个客户, 则 ξ 1 , ξ 2 , … \xi_{1}, \xi_{2}, \ldots ξ1,ξ2,…独立同分布, 且 P ( ξ i = k − 1 ) = a k P\left(\xi_{i}=k-1\right)=a_{k} P(ξi=k−1)=ak. 可得 X n + 1 = ( X n + ξ n + 1 ) + X_{n+1}=\left(X_{n}+\xi_{n+1}\right)^{+} Xn+1=(Xn+ξn+1)+ (正部分仅在 X n = 0 X_n=0 Xn=0和 ξ n + 1 = − 1 \xi_{n+1}=−1 ξn+1=−1时生效).
很容易看出,序列 ξ i \xi_{i} ξi是一个具有如下转移概率的马尔可夫链
p ( 0 , 0 ) = a 0 + a 1 , p ( j , j − 1 + k ) = a k 若 j ≥ 1 或 k > 1 p(0,0)=a_{0}+a_{1},p(j, j-1+k)=a_{k} \quad \text {若 } j \geq 1 \text { 或} k>1 p(0,0)=a0+a1,p(j,j−1+k)=ak若 j≥1 或k>1其中, a k a_{k} ak形式复杂但不重要,可以假设 a k > 0 , k ≥ 0 a_{k}>0, k \geq 0 ak>0,k≥0且 ∑ k > 0 a k = 1 \sum_{k>0} a_{k}=1 ∑k>0ak=1.
