3.1. 马氏链-马氏链的定义和示例

马氏链的定义和示例

1. 马氏链的定义

对于可数状态空间的马氏链, 马氏性指的是给定当前状态, 其他过去的状态与未来的预测无关. 即对任意状态$i_0,\dots i_{n-1},i$, $j$
$$P\left(X_{n+1}=j\mid X_n=i,X_{n-1}=i_{n-1},\dots X_0=i_0\right)=P\left(X_{n+1}=j\mid X_n=i\right)$$

称条件概率$P\left(X_{n+1}=j\mid X_n=i\right)$为马氏链 { X n , n = 0 , 1 , 2 , . . . } \{X_n,n=0,1,2,...\} {Xn​,n=0,1,2,...}的一步转移概率, 简称转移概率, 记为$p_{ij}$, 表示处于状态$i$的过程下一步转移到状态$j$的概率.

2. 马氏链的示例

2.1. 随机游走

示例5.1.1 (随机游走的转移概率) 令${\xi }_1,{\xi }_2,\dots \in {\mathbf{Z}}^d$独立, 分布为$\mu$. $X_n=X_0+{\xi }_1+\cdots +{\xi }_n$, 其中$X_0$是常数. 则$X_n$是马氏链,转移概率为 p ( i , j ) = μ ( { j − i } ) p(i, j)=\mu(\{j-i\}) p(i,j)=μ({j−i}).

证明: 证明$X_n$是马氏链. 若${\mu }_j$是${\xi }_j$的分布, 由于$X_n$和${\xi }_{n+1}$独立, 则由示例4.1.7 (二元独立随机变量函数关于某变量的条件期望)
$$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\left(X_{n+1}\in B\mid X_n\right)\in \sigma (X_n)\subset \mathcal{F}$, 由定理4.1.12可得
$$P\left(X_{n+1}\in B\mid X_n\right)=P\left(X_{n+1}\in B\mid {\mathcal{F}}_n\right)$$

习题5.1.6 (以概率$\theta$正向走, $1-\theta$负向走的随机游走是一个非时齐的马氏链) 令$\theta ,U_1,U_2,\dots$是$(0,1)$上的独立均匀分布. 若$U_i\le \theta$,$X_i=1$; 若$U_i>\theta$, $X_i=-1$. $S_n=X_1+\cdots +X_n$.

• $(i)$ 转移概率 $P\left(X_{n+1}=1\mid X_1,\dots ,X_n\right)$只与$S_n$相关;
• $(ii)$ $S_n$是一个非时齐马尔可夫链. 自然, $S_n$是一个估计$\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}∣.
$$\begin{array}{rl}P\left(X_{n+1}=1\mid X_1=i_1,\dots ,X_n=i_n\right)& =\frac{P\left(X_1=i_1,\dots ,X_n=i_n,X_{n+1}=1\right)}{P\left(X_1=i_1,\dots ,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{array}$$
上式由${\int }_0^1{x}^m(1-x{)}^{k}dx=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$. 证明 X n = ∣ { ξ 1 , … , ξ n } ∣ X_{n}=\left|\left\{\xi_{1}, \ldots, \xi_{n}\right\}\right| Xn​=∣{ξ1​,…,ξn​}∣是马氏链, 并计算转移概率.

证明：$X_{n+1}$依赖于$X_n$和${\xi }_{n+1}$, 自然是马氏链. 转移概率可以表示为:
$$p(k,k+1)=1-\frac{k}{N},p(k,k)=\frac{k}{N},p(i,j)=0\text{其他}$$

习题5.1.2.对称随机游走最大值序列不是马氏链 $S_0=0,S_n={\xi }_1+\cdots {\xi }_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=m,X_{n-1}=m-1$, 则$X_n=S_n$, 故
$$\mathbb{P}\left(X_{n+1}=m+1\mid X_n=m,X_{n-1}=m-1\right)=1/2$$
当$X_n=m,X_{n-1}=m$, $\mathbb{P}\left(X_{n+1}=m+1\mid X_n=m,X_{n-1}=m\right)=0$, $X_n$非马氏链.

2.2. 分支过程

示例 5.1.2 (分支过程的转移概率) S = { 0 , 1 , 2 , … } S=\{0,1,2, \ldots\} S={0,1,2,…}, 第$n$代每个个体$i$产生i.i.d的后代数${\xi }_1,{\xi }_2,\dots$, 则$p(i,j)=P({\sum }_{m=1}^i{\xi }_m=j)$, .

2.3. Ehrenfest chain

示例 5.1.3 (Ehrenfest chain) 第一个瓮有$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\text{否则 },$$Ehrenfest用此模拟两个腔室(大小形状相同,一个小孔连接)间空气分子的划分.

习题5.1.5. 假设左瓮和右瓮, 每个瓮$m$个球. $b$ ($\le m$ ) 个黑色球, $2m-b$个白色球. 每次从每个瓮中选择一个球然后互相交换. 计算左瓮黑球数的转移概率.

证明：$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}$

2.4. 遗传模型

示例 5.1.4 (Wright–Fisher遗传模型) 设总体中的个体数为$N$, 每个个体的基因按基因 $A$ 的基因频率的大小, 在下一代中转移成为基因 $A$.
换句话说, 如果在第$n$代母体中基因$A$出现了$i$次, 基因$a$出现了$N-i$次, 则下一代出现基因$A$的概率为 $p_i=\frac{i}{N}$, 而出现基因 $a$ 的概率为 $1-p_i$.

• (i) 令$X_n$表示第$n$代基因$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$在下一代有概率$\mu$是$a$, 而$a$在下一代有概率$\nu$是$A$.

证明：(i) 记 $X_n$ 为第 $n$ 代中携带基因 $A$ 的个体数, 则易知 { X n } \left\{X_{n}\right\} {Xn​} 是一个状态空间为 S = { 0 , 1 , ⋯ , N } S=\{0,1, \cdots, N\} S={0,1,⋯,N} 的时齐Markov链, 其转移概率矩阵为 $\mathbf{P}=\left(p_{ij}\right)$, 其中
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}=CNj​pij​(1−pi​)N−j=CNj​(Ni​)j(1−Ni​)N−j
在这个模型中,状态$X=0$和$N$对应于总体是$A$和$a$,称为吸收状态 (absorbing states), 即$p(x,x)=1$. 这个链最终将进入状态$0$或状态$N$.

(ii) 产生$A$的概率是${\rho }_i=(i/N)(1-u)+(N-i/N)v$. 转移概率为
$$p(i,j)=\left(\begin{array}{c}N\\ j\end{array}\right){\left({\rho }_i\right)}^j{\left(1-{\rho }_i\right)}^{N-j}$$
如果$u$和$v$都是正的,$0$和$N$就不再是吸收态了,系统可收敛到一个平衡分布.

习题5.1.3 (连续成对的抛硬币序列). 令 ξ 0 , ξ 1 , … ∈ { H , T } \xi_{0}, \xi_{1}, \ldots\in\{H, T\} ξ0​,ξ1​,…∈{H,T}独立同分布, 每个取值概率为$1/2$ (硬币正反面). $X_n=\left({\xi }_n,{\xi }_{n+1}\right)$是一个马氏链, 计算转移概率$p$以及$p^2$.

证明：由于$X_n=\left({\xi }_n,{\xi }_{n+1}\right)$, 可知$X_{n-2}=\left({\xi }_{n-2},{\xi }_{n-1}\right),\cdots ,X_0=\left({\xi }_0,{\xi }_1\right)$与$X_n$独立,因此$X_n$是马氏链. 易计算得到转移概率$p$及$p^2$.

习题5.1.4 (兄弟姐妹结对遗传). 两只动物交配的直系后代中随机选择两个异性个体交配, 过程持续. 假设个体是$AA,Aa,aa$中的一个, 从每个父母中选择一个字母来决定后代类型, 计算第$n$代基因型对的转移概率.

证明：该马氏链第$n$代基因型对共有以下6个状态, 易计算转移概率
$$AA,AAAA,AaAA,aaAa,AaAa,aaaa,aa$$

2.5. M/G/1 队列

示例5.1.5. M/G/1 队列:客户$n$开始服务的队列人数 客户按照速率为$\lambda$的泊松过程到达. 不相交时间间隔内的到达数独立,每个客户服务时长独立,分布为$F$.
设$X_n$为第$n$个客户进入服务时队列的客户数(包括服务中的客户). $X_0=x$表示客户$0$刚开始服务时队列有$x$人. 计算$X_n$的转移概率.

证明：在一个服务时间内$k$个顾客到达的概率为$a_k$
$$a_k={\int }_0^{\infty }{e}^{-\lambda t}\frac{(\lambda t{)}^k}{k!}dF(t)$$
令${\xi }_i$表示第$i$次服务时间内到达的客户数减去完成服务的1个客户, 则${\xi }_1,{\xi }_2,\dots$独立同分布, 且 $P\left({\xi }_i=k-1\right)=a_k$. 可得$X_{n+1}={\left(X_n+{\xi }_{n+1}\right)}^{+}$ (正部分仅在$X_n=0$和${\xi }_{n+1}=-1$时生效).
很容易看出,序列${\xi }_i$是一个具有如下转移概率的马尔可夫链
$$p(0,0)=a_0+a_1,p(j,j-1+k)=a_k\text{若 }j\ge 1\text{ 或}k>1$$其中, $a_k$形式复杂但不重要,可以假设$a_k>0,k\ge 0$且${\sum }_{k>0}{a}_k=1$.