电子商务网站建设题6,优质做网站费用,企业网站官网制作,合肥网络推广外包马氏链的定义和示例 马氏链的定义和示例1. 马氏链的定义2. 马氏链的示例2.1. 随机游走2.2. 分支过程2.3. Ehrenfest chain2.4. 遗传模型2.5. M/G/1 队列 马氏链的定义和示例
1. 马氏链的定义
对于可数状态空间的马氏链, 马氏性指的是给定当前状态, 其他过去的状态与未来的预测… 马氏链的定义和示例 马氏链的定义和示例1. 马氏链的定义2. 马氏链的示例2.1. 随机游走2.2. 分支过程2.3. Ehrenfest chain2.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_{n1}j \mid X_{n}i, X_{n-1}i_{n-1}, \ldots X_{0}i_{0}\right)P\left(X_{n1}j \mid X_{n}i\right) P(Xn1j∣Xni,Xn−1in−1,…X0i0)P(Xn1j∣Xni)
称条件概率 P ( X n 1 j ∣ X n i ) P\left(X_{n1}j \mid X_{n}i\right) P(Xn1j∣Xni)为马氏链 { X n , n 0 , 1 , 2 , . . . } \{X_n,n0,1,2,...\} {Xn,n0,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} XnX0ξ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_{n1} ξn1独立, 则由示例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_{n1} \in B \mid X_{n}\right)P\left(X_{n}\xi_{n1} \in B \mid X_{n}\right)\mu_{n1}\left(B-X_{n}\right) P(Xn1∈B∣Xn)P(Xnξn1∈B∣Xn)μn1(B−Xn) 故 P ( X n 1 ∈ B ∣ X n ) ∈ σ ( X n ) ⊂ F P\left(X_{n1} \in B \mid X_{n}\right)\in \sigma(X_n)\subset \mathcal{F} P(Xn1∈B∣Xn)∈σ(Xn)⊂F, 由定理4.1.12可得 P ( X n 1 ∈ B ∣ X n ) P ( X n 1 ∈ B ∣ F n ) P\left(X_{n1} \in B \mid X_{n}\right)P\left(X_{n1} \in B \mid \mathcal{F}_{n}\right) P(Xn1∈B∣Xn)P(Xn1∈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 Xi1; 若 U i θ U_{i}\theta Uiθ, X i − 1 X_{i}-1 Xi−1. S n X 1 ⋯ X n S_{n}X_{1}\cdotsX_{n} SnX1⋯Xn. ( i ) (i) (i) 转移概率 P ( X n 1 1 ∣ X 1 , … , X n ) P\left(X_{n1}1 \mid X_{1}, \ldots, X_{n}\right) P(Xn11∣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:im1}∣. 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_{n1}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_{n1}1\right)}{P\left(X_{1}i_{1}, \ldots, X_{n}i_{n}\right)}\\ (\text{重期望公式})\frac{\int \theta^{N1}(1-\theta)^{n-N} d \theta}{\int \theta^{N}(1-\theta)^{n-N} d \theta}\\ \frac{\left(S_{n}/2n/21\right) ! /(n2) !}{(S_{n}/2n/2)! /(n1) !}\frac{S_{n}n2}{2n4} \end{aligned} P(Xn11∣X1i1,…,Xnin)(重期望公式)P(X1i1,…,Xnin)P(X1i1,…,Xnin,Xn11)∫θN(1−θ)n−Ndθ∫θN1(1−θ)n−Ndθ(Sn/2n/2)!/(n1)!(Sn/2n/21)!/(n2)!2n4Snn2 上式由 ∫ 0 1 x m ( 1 − x ) k d x m ! k ! / ( m k 1 ) ! \int_{0}^{1} x^{m}(1-x)^{k} d xm ! k ! /(mk1) ! ∫01xm(1−x)kdxm!k!/(mk1)!得到. 习题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_{n1} Xn1依赖于 X n X_{n} Xn和 ξ n 1 \xi_{n1} ξn1, 自然是马氏链. 转移概率可以表示为: p ( k , k 1 ) 1 − k N , p ( k , k ) k N , p ( i , j ) 0 其他 p(k, k1)1-\frac{k}{N}, \quad p(k, k)\frac{k}{N}, \quad p(i, j)0 \text {其他} p(k,k1)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} S00,Snξ1⋯ξn是对称随机游走, X n max { S m : 0 ≤ m ≤ n } X_{n}\max \left\{S_{m}: 0 \leq m \leq n\right\} Xnmax{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 Xnm,Xn−1m−1, 则 X n S n X_nS_n XnSn, 故 P ( X n 1 m 1 ∣ X n m , X n − 1 m − 1 ) 1 / 2 \mathbb{P}\left(X_{n1}m1 \mid X_{n}m, X_{n-1}m-1\right)1/2 P(Xn1m1∣Xnm,Xn−1m−1)1/2 当 X n m , X n − 1 m X_{n}m,X_{n-1}m Xnm,Xn−1m, P ( X n 1 m 1 ∣ X n m , X n − 1 m ) 0 \mathbb{P}\left(X_{n1}m1 \mid X_{n}m, X_{n-1}m\right)0 P(Xn1m1∣Xnm,Xn−1m)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_{m1}^{i} \xi_{m}j) p(i,j)P(∑m1iξmj), . 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, k1)(r-k) / r, p(k, k-1)k / r, p(i, j)0 \quad \text {否则 }, p(k,k1)(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, n1) \frac{m-n}{m} \cdot \frac{b-n}{m},p(n, n-1) \frac{n}{m} \cdot \frac{mn-b}{m} p(n,n1)mm−n⋅mb−n,p(n,n−1)mn⋅mmn−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} piNi, 而出现基因 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_{n1}j \mid X_{n}i\right\} pijP{Xn1j∣Xni}.(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_{n1}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} pijP{Xn1j∣Xni}CNjpij(1−pi)N−jCNj(Ni)j(1−Ni)N−j 在这个模型中,状态 X 0 X0 X0和 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_{n1}\right) Xn(ξn,ξn1)是一个马氏链, 计算转移概率 p p p以及 p 2 p^{2} p2. 证明由于 X n ( ξ n , ξ n 1 ) X_{n}\left(\xi_{n}, \xi_{n1}\right) Xn(ξn,ξn1), 可知 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_0x X0x表示客户 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(ξik−1)ak. 可得 X n 1 ( X n ξ n 1 ) X_{n1}\left(X_{n}\xi_{n1}\right)^{} Xn1(Xnξn1) (正部分仅在 X n 0 X_n0 Xn0和 ξ n 1 − 1 \xi_{n1}−1 ξn1−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-1k)a_{k} \quad \text {若 } j \geq 1 \text { 或} k1 p(0,0)a0a1,p(j,j−1k)ak若 j≥1 或k1其中, a k a_{k} ak形式复杂但不重要,可以假设 a k 0 , k ≥ 0 a_{k}0, k \geq 0 ak0,k≥0且 ∑ k 0 a k 1 \sum_{k0} a_{k}1 ∑k0ak1.
