习题四¶

1¶

\(p(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\cdots,X_0=i_0)=p(X_{n+1}=j|X_n=i)\),(独立性),从而\(X\)是马尔可夫链
当且仅当\(X_n\)独立同分布时,\(X\)是齐次马尔可夫链

2¶

(1)¶

令 \(x_n=i . x_{n+1}=j\). 当 \(i=0\) 时. \(j \in \{1\}\). 即 :\(p\left(x_{n+1}=1 \mid x_n=0\right)=1 ,\;i.e. p_{01}=1\). 当 \(i \geqslant 1\) 时. \(j \in\{i-1, i+1\}\)

\[ \begin{aligned} p\left(x_{n+1}\right. & \left.=i+1 \mid x_n=i\right)=p\left(S_{n+1}=i+1 \mid S_n=i\right) p\left(S_n=i|| S_n \mid=i\right)+p\left(S_{n+1}=-i-1 \mid S_n=-i\mid |S_n|=i\right) \\ & =p\left(\xi_{n+1}=1\right) p\left(S_n=i||S_n|=i\right)+p\left(\xi_{n+1}=-1\right) p\left(S_n=i||S_n|=i\right) . \end{aligned} \]

若 \(n=2 k\) 为偶. 则 \(X_n=i=2l\) 为偶于是 \(p\left(S_n=i\right)=C_{2 k}^{p+l} p^{k+l}(1-p)^{k-l} p\left(S_n=-i\right)=C_{2 k}^{k-l} p^{k-l}(1-p)^{k+l}\)

\[ \Rightarrow P\left(S_n=i||S_n \mid=i\right)=\frac{p^i}{P^i+(1-p)^i} \]

对 \(n\) 为奇时,同样有上式。于是有

\[ p\left(x_{m+1}=i+1 \mid x_n=i\right)=p \frac{p^i}{p^i+(1-p)^i}+(1-p) \frac{(1-p)^i}{p^i+(1-p)^i}=\frac{p^{i+1}+(1-p)^{i+1}}{p^i+(1-p)^i} \]

同理 \(p\left(x_{n+1}=i-1 \mid x_n=i\right)=\frac{(1-p) p^i+p(1-p)^i}{p^i+(1-p)^i}\)

于是有

\[ P_{i j}=\left\{\begin{array}{cl} \frac{p^{i+1}+(1-p)^{i+1}}{p^i+(1-p)^i} & j=i+1, i \geqslant 1 . \\ \frac{(1-p) p^i+p \phi(1-p)^i}{p^i+(1-p)^i} & j=i-1, i \geqslant 1 . \\ 1 & j=1, i=0 .\\ 0 & \text { 其他 } \end{array}\right. \]

(2)¶

显然有 \(M_{n+1}=\max \left\{M_n, S_{n+1}\right\}\) ，于是 \(Y_{n+1}=\max \left\{ M_n , S_{n+1}\right\}\). 于是为 Markov的

\[ Y_n \in\{0,1-2 \ldots n\} . M_n \geqslant 0 \text {. } \]

\(Y_n=0\) 时

\[ \begin{aligned} & P\left(Y_{n+1}=1 \mid Y_n=0\right)=p\left(S_{n+1}=-1\right)=1-p . \\ & p\left(Y_{n+1}=0 \mid Y_n=0\right)=p\left(S_{n+1}=1\right)=p . \end{aligned} \]

\(Y_n=i \geqslant 1 \text { 时. } Y_{n+1} \in\{i-1, i+1\}\)

\[ \begin{aligned} & P\left(Y_{n+1}=i+1 \mid Y_n=i\right)=P\left(S_{n+1}=S_{n}-1\right)=1-p \\ & P\left(Y_{n+1}=i-1 \mid Y_n=i\right)=P\left(S_{n+1}=S_{n}+1\right)=p . \end{aligned} \]

\[ \text { 于是 } P_{i j}=\left\{\begin{array}{cc} P & i=j=0 . \\ 1-P & i \geqslant 0, j=i+1 \\ P & i \geqslant 1, j=i-1 \\ 0 & \text { 其它. } \end{array}\right. \]

3¶

\(\exists h^{-1}: \mathcal{E}' \mapsto \mathcal{E}\) 是双射

\[ \begin{aligned} p\left(Y_{n+1}\right. & \left.=j \mid Y_n=i_n, Y_{n-1}=i_{n-1} \ldots Y_1=i_1\right) \\ & =p\left(X_{n+1}=h^{-1}(j) \mid X_n=h^{-1}\left(i_n\right) \ldots, X_1=h^{-1}\left(i_1\right)\right) \\ & =p\left(X_{n+1}=h^{-1}(j) \mid X_n=h^{-1}\left(i_n\right)\right)=p\left(Y_{n+1}=j \mid Y_n=i_n\right) \end{aligned} \]

于是 \(Y=\left(Y_n, n \geqslant 0\right)\) 是从 Markov链。

4¶

5¶

\[ \begin{aligned} &P\left(x_0=1, x_1=2, x_2=3\right)=P_0(1) P_{12} P_{23}=0.3 \times 0.2 \times 0=0.3 \end{aligned} \]

6¶

\(p\left(X_2=2, X_3=21 X_1=1\right)=P_{12} P_{22}=0.2 \times 0.6=0.12\)

\(P\left(X_1=2, X_2=2 \mid X_0=1\right)=P_{12} \cdot P_{22}=0.12\)

7¶

\(P\left(X_0=2, X_1=2, X_2=1\right)=P_0(2) P_{22} P_{21}=0.5 \times 0.1 \times 0.5=0.025\)

\(P\left(X_1=2, X_2=2, X_3=1\right)=\left(P_0(1) P_{12}+P_0(2) P_{22}+P_0(3) P_{32}\right) P_{22} P_{21}=0.0075\)

8¶

\[ X_{n+1}=\max \left\{\xi_{n+1}, X_n\right\}\in \{i\geq X_n,i\in\{0,1,2,3\}\} \]

故为 Markov的

\[P = \begin{pmatrix} 0.1 & 0.3 & 0.2 & 0.4 \\ & 0.4 & 0.2 & 0.4 \\ & & 0.6 & 0.4 \\ & & & 1\end{pmatrix}\]

9¶

\(p\left(X_0=1 \mid X_0=1\right)=1 . \quad p\left(X_1=1 \mid X_0=1\right)=0 . p\left(X_2=1 \mid X_0=1\right)=\sum p_{0i} p_{i_0}=\frac{1}{2}\).

\(P\left(X_3=1 \mid X_0=1\right)=\sum\limits_{i,j} P_{0 i} P_{i j} p_{j 0}=\frac{1}{4} . \quad P\left(X_4=1 \mid X_0=1\right)=\frac{3}{8}\).

10¶

\(p\left(X_3=1 \mid X_0=1, T=n\right)=0 . \quad \forall n \geqslant 4\)

\(P\left(X_3=1 \mid X_0=1,T>3\right)=0\)

11¶

\(X_n \in\{2,1,0,-1\}\)

令 \(X_n=i,X_{n+1}=j\).

(1) 当 \(i=0,-1\) 时. \(j \in\{0,1,2\}\)

\[ p\left(x_{n+1}=j \mid x_n=i\right)=p\left(\xi_{n+1}=2-j\right) \]

(2) 当 \(i=1\) 时. \(j \in\{1,0,-1\}\)

\[ p\left(x_{n+1}=j \mid x_n=i\right)=p\left(\xi_{n+1}=1-j\right) \]

(3) 当 \(i=2\) 时. \(j \in\{2,1,0\}\)

\[ p\left(x_{n+1}=j \mid x_n=i\right)=p\left(\xi_{n+1}=2-j\right) \]

故

\[ P = \begin{pmatrix} 0 & \frac{1}{10} & \frac{2}{5} & \frac{1}{2} \\ 0 & \frac{1}{10} & \frac{2}{5} & \frac{1}{2} \\ \frac{1}{10} & \frac{2}{5} & \frac{1}{2} & 0 \\ 0 & \frac{1}{10} & \frac{2}{5} & \frac{1}{2} \end{pmatrix} \]

12¶

\(\begin{cases} q_1 = 0.3q_1+0.2q_2 \\ q_2 = 0.5q_1+0.1q_2+0.4\end{cases}\)

\(\implies q_2 = \frac{28}{53}\)

13¶

\(f_{ij}=\sum\limits_{k=1}^\infty f_{ij}^{(k)}\)

\[\begin{cases} q_1 = p_{11}q_1 + \cdots + p_{1,N}q_N\\ \vdots \\ q_N = p_{N-1,1}q_1 + \cdots + p_{N-1,N}q_N\\ q_N = 1\end{cases}\]

\(LHS = \frac{i}{N}\)

\(RHS = \sum\limits_{j=1}^NP_{ij}q_j=\sum\limits_{j=1}^Np_{ij}\frac{i}{N} = \frac{i}{N}\)

14¶

必要性 : 设 \(Q = \begin{pmatrix}a & 1-a \\ 1-b & b\end{pmatrix}\)

\(P=Q^2 = \begin{pmatrix}a^2+(1-a)(1-b) & * \\ * & b^2+(1-a)(1-b)\end{pmatrix}\)

\(\implies p_{11}+p_P{22} = a^2+(1-a)(1-b)+b^2+(1-a)(1-b)=(a+b-1)^2+1\geq 1\)

充分性 : 设 \(P = \begin{pmatrix}p & 1-p \\ 1-q & q\end{pmatrix}\)

注意到 \(Q = \begin{pmatrix} \frac{p-\sqrt{p+q-1}}{1-\sqrt{p+q-1}} & \frac{1-p}{1-\sqrt{p+q-1}} \\ \frac{q-\sqrt{p+q-1}}{1-\sqrt{p+q-1}} & \frac{1-q}{1-\sqrt{p+q-1}}\end{pmatrix}\) 是一个马尔科夫两步状态转移矩阵,且 \(P=Q^2\)

15¶

(1) : \(1 \leftrightarrow 2 \leftrightarrow 3,4 \rightarrow 1\). 但 \(1 \rightarrow 4\). 于是 \(d_1=d_2=d_3\).

\[ \begin{aligned} & p_{11}^{(2)}=p_{13} p_{31}=1 \times \frac{1}{2}=\frac{1}{2} \quad P_{11}^{(3)}=P_{13} p_{32} p_{21}=1 \times \frac{1}{2} \times 1=\frac{1}{2} . \\ & \text { 于是 } d_1=d_2=d_3=\operatorname{ged}\{2.3\}=1 . \\ & d_4=1 . \end{aligned} \]

故 \(d_1=d_2=d_3=d_4=1\).

(2) : \(1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4\). F是 \(d_1=d_2=d_3=d_4\).

\[ p_{11}^{(3n)}=p_{12} p_{24} p_{41} \cdot\left(p_{24} p_{43} p_{32}\right)^{n-1}=\frac{1}{3} \times\left(\frac{2}{3}\right)^{n-1} \text {. } \]

于是 \(d_1=d_2=d_3=d_4=\operatorname{g}(d\{3 n: n \in \mathbb{Z}\}=3\).

16¶

\(i\leftrightarrow j,\forall i,j\), 于是存在 \(n,s.t.p_{ii}^{(n)}>0\), 但 \(P^2=P\), 于是 \(n=1\) 换句话说 \(p_{ii}>0\), 从而 \(d_i=1,\forall i\) 从而 Markov链是非周期的

于是其为非周期不可约的,从而极限分布等于平稳分布

令 \(P=(\alpha_1,\alpha_2,\cdots,\alpha_n)\) 则 \(\alpha_i P = \alpha_i\), 于是 \(\alpha_i\) 是平稳分布,从而 \(\alpha_1=\alpha_2=\cdots=\alpha_n\)

\(\implies p_{ij}=p_{jj}\)

17¶

\[\begin{aligned} & P=Q \operatorname{diag}\left(1, \frac{1}{2},-\frac{1}{2}\right) Q^{-1} \\ & \quad \text { 其中 } Q=\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & -1 \\ 1 & 0 & 0 \end{array}\right), Q^{-1}=\left(\begin{array}{ccc} 0 & 0 & 1 \\ \frac{1}{2} & \frac{1}{2} & -1 \\ \frac{1}{2} & -\frac{1}{2} & 0 \end{array}\right) \end{aligned}\]

于是 \(P^k=Q \operatorname{diag}\left(1 , \frac{1}{2^k},\left(\frac{-1}{2}\right)^k\right) Q^{-1}\)

\[ =\left(\begin{array}{ccc} \frac{1+(-1)^k}{2^{k+1}} & \frac{1-(-1)^k}{2^{k+1}} & 1-\frac{1}{2^k} \\ \frac{1-(-1)^k}{2^{k+1}} & \frac{1+(1))^k}{2} & 1-\frac{1}{2 k} \\ 0 & 0 & 1 \end{array}\right) \text {. } \]

(2): \(1 \leftrightarrow 2\)

\[ \begin{aligned} & 1 \leftrightarrow 2 . \\ & p_{11}^{(2 n)}=\left(p_{12} p_{21}\right)^n=\frac{1}{4^n} \quad \text { 故 } \quad d_1=d_2=2 . \quad d_3=1 . \\ & \sum p_{11}^{(n)}<\infty . \quad \sum p_{22}^{(n)}<\infty . \quad \sum p_{33}^{(n)}=\infty . \end{aligned} \]

1,2为瞬时的,3 为常返的

19.¶

\(2 \leftrightarrow 3\)

\(f_{11}=a<1,p_{11}^{(n)}=a^n\implies \sum\limits_{n=1}^\infty p_{11}^{(n)}=\frac{a}{1-a}<\infty\) 从而1 为瞬时状态

显然有 \(p_{22}^{(2 n)}=p_{33}^{(n)}=1\). 于是 \(\sum p_{22}^{(n)}=\sum p_{33}^{(n)}=\infty\) 从而 2,3 为常返状态

21¶

状态空间包含三个互达等价类 \(\{1,2\} ，\{3,4\} ，\{5,6\}\). 其中 \(\{1,2\}\) 与 \(\{3,4\}\) 是常返的,而 \(\{5,6\}\) 是瞬时的. 且状态 \(\{1,2,3,4\}\) 均是非周期的. 从而由推论 4.1 可知,

\[ \lim _{n \rightarrow \infty} p_{6 j}^{(n)}=\frac{f_{6 j}}{\tau_j} . \]

其中， \(f_{i j}\) 为从 \(i\) 出发可达到 \(j\) 的概率， \(\tau_j\) 为状态 \(j\) 的平均返回时间. 观察转移概率矩阵的最后两行, 不难发现 \(f_{61}=f_{62}=f_{63}=f_{64}=\frac{1}{2}\). 对于状态 1 而言, \(\tau_1=E\left(T_1 \mid X_0=1\right)=1 \times \frac{1}{3}+\sum_{k=2}^{\infty} k \cdot \frac{2}{3} \cdot\left(\frac{1}{3}\right)^{k-2} \cdot \frac{2}{3}=2\), 从而

\[ \lim _{n \rightarrow \infty} p_{61}^{(n)}=\frac{f_{61}}{\tau_1}=\frac{1}{4} \]

同理于状态 \(\{2,3,4\}\), 经计算可得

\[ \begin{aligned} & \lim _{n \rightarrow \infty} p_{62}^{(n)}=\frac{f_{62}}{\tau_2}=\frac{1}{4}, \\ & \lim _{n \rightarrow \infty} p_{63}^{(n)}=\frac{f_{63}}{\tau_3}=\frac{2}{19}, \\ & \lim _{n \rightarrow \infty} p_{64}^{(n)}=\frac{f_{64}}{\tau_4}=\frac{15}{38} . \end{aligned} \]

另一方面，由于状态 \(\{5,6\}\) 是瞬时的，显然有

\[ \lim _{n \rightarrow \infty} p_{65}^{(n)}=\lim _{n \rightarrow \infty} p_{66}^{(n)}=0 . \]

2.由于状态 6 是个吸收态, 从而显然有

\[ \lim _{n \rightarrow \infty} p_{61}^{(n)}=\lim _{n \rightarrow \infty} p_{62}^{(n)}=\lim _{n \rightarrow \infty} p_{63}^{(n)}=\lim _{n \rightarrow \infty} p_{64}^{(n)}=\lim _{n \rightarrow \infty} p_{65}^{(n)}=0, \lim _{n \rightarrow \infty} p_{66}^{(n)}=1 \]

22¶

\(p_0\neq 0\implies d_i=1,\forall i\), 又存在 \(j\neq 0,s.t.p_j\neq 0\), 于是 \(\forall i,j: i\leftrightarrow j\), 于是其非周期不可约

注意到 \(\pi = (\frac{1}{m+1},\cdots,\frac{1}{m+1})\) 是平稳分布, 于是 \(\lim\limits_{n\to\infty} p_{ij}^{(n)} =\frac{1}{1+m}\)

24¶

用有序对 \(X_n=(*, *)\) 表示第 \(n\) 天与第 \(n+1\) 天的天气状况, 且其状态空间为 \(\{1,2,3,4\}\),其中, \(1=\) (晴, 晴 \(), 2=(\) 晴, 云 \(), 3=(\) 云, 晴 \(), 4=(\) 云, 云 \()\). 那么, 显然 \(X=\left\{X_n, n \geq 1\right\}\) 是一个 Markov 链, 且其转移概率矩阵为

\[ P=\left[\begin{array}{cccc} 0.8 & 0.2 & 0 & 0 \\ 0 & 0 & 0.4 & 0.6 \\ 0.6 & 0.4 & 0 & 0 \\ 0 & 0 & 0.1 & 0.9 \end{array}\right] . \]

设 \(\pi\) 是 \(X\) 的平稳分布, 则满足下面方程组

\[ \left\{\begin{array}{c} \pi_1=0.8 \pi_1+0.6 \pi_3 \\ \pi_2=0.2 \pi_1+0.4 \pi_3 \\ \pi_3=0.4 \pi_2+0.1 \pi_4 \\ \pi_4=0.6 \pi_2+0.9 \pi_4 \\ \pi_1+\pi_2+\pi_3+\pi_4=1 \end{array}\right. \]

求解可得， \(\pi=\left(\frac{3}{11}, \frac{1}{11}, \frac{1}{11}, \frac{6}{11}\right)\). 此外，从长远来看，晴天的概率为 \(\frac{3}{11}+\frac{1}{11}=\frac{4}{11}\).

25¶

\(\pi = (\frac{9}{20},\frac{6}{20},\frac{5}{20})\)
计算可得 \(P^*=P\)

26¶

\(P\left(X_2=2, X_1=2 \mid X_0=1\right)=p_{12} p_{22}=0.1\).
\(P\left(X_2=1 \mid X_0=3\right)=p_{31}^{(2)}=0.36\).
记 \(T=\min \left\{n \geq 1: X_n \neq 3 \mid X_0=3\right\}\) ，那么 \(T\) 服从参数为 0.8 的几何分布, 从而 \(E(T)=\frac{5}{4}\).

27¶

\(\pi = (\frac{6}{25},\frac{10}{25},\frac{9}{25})\)
由定理 4.9 可知 \(\tau_j=\frac{1}{\pi_j}\)

28¶

\(P_1\) 不是, 考察回路 \((1,2,3,1)\) 即可

\(P_2\) 是 (画图容易看出只需要验证 \(\sigma_1 = (1,2,3,1),\sigma_2=(2,3,4,2)\))

\(P_3\) 是 (画图容易看出)

\(P_4\) 不是, 考察回路 \((1,2,3,1)\) 即可