随机过程（E）——习题课（马尔科夫链-更新过程）

学弱猹

发布于 2021-08-10 11:36:19

1.8K0

发布于 2021-08-10 11:36:19

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：随机过程（D）——鞅的极限性质的应用，布朗运动概述

————————————————————————————————————

大家好！

这一节开始我们进入习题课。我们会对于每一个部分的内容给出一些习题，并计划以计算题为主，证明题为辅。注意到在每一节的正文其实或多或少都有一些题目用于概念和性质的理解和应用，所以在这里我们挑选的题目不会特别简单，更多的是需要一些思考或计算的题目，这也是我一直写习题课保持的一个习惯。

那么我们开始吧。

马尔科夫链

Problem 1: 考虑下面这个转移概率矩阵，判断其中的常返与瞬时状态。

P = \begin{bmatrix}0.1 & 0 & 0 & 0.4 & 0.5 & 0 \\ 0.1 & 0.2 & 0.2 & 0 & 0.5 & 0 \\ 0 & 0.1 & 0.3 & 0 & 0 & 0.6 \\ 0.1 & 0 & 0 & 0.9 & 0 & 0 \\ 0 & 0 & 0 & 0.4 & 0 & 0.6 \\ 0 & 0 & 0 & 0 & 0.5 & 0.5\end{bmatrix}

其中状态

[1, 2, 3, 4, 5, 6]

从左到右，从上到下排序。

这一个题的解决方案很简单，就是画一张有向图。对应下面这个图。

这样的话，找出环之后，会发现剩下的两个点

2, 3

，到达集合内的某个点之后就“无法逃逸”了，因此根据第2节（随机过程（2）——极限状态的平稳分布与周期（上），一些特殊的马尔科夫链）的开头的例子就可以得到，

\{2, 3\}

是瞬时状态，其余的4个为常返状态。

Problem 2: 考虑状态

[1, 2]

，从左到右，从上到下排序，且转移概率矩阵为

\begin{bmatrix}1 -a & a \\ b & 1- b\end{bmatrix}

，证明

P(X_{n + 1} = 1) - \frac b {a + b} = (1 - a - b)[P(X_n = 1) - \frac b { a + b}]

这个题本质上可以理解为是一个马尔可夫性对应条件概率的应用，对应的法子我们在第1节其实说过，就是利用乘法公式。注意到

P(X_{n + 1} = 1) = \sum_i P(X_n = i, X_{n + 1} = 1) = \sum_i P(X_n = i)P(X_{n + 1} = 1 | X_n = i)

= \sum _i P(X_n = i) p(i, 1) = P(X_n = 1)(1 - a) + (1 - P(X_n = 1))b

= (1- a - b) P(X_n = 1) + b

这样的话，就不难通过一些等式变换得到最终的结论了。剩下的部分我们交给读者。

Problem 3: 考虑一个时钟上的随机游走问题。时钟上有

[1, 2, \ldots, 12]

共12个点，设

X_n

为第

步所在的位置，并且假设每一次，都会等概率的往顺时针/逆时针方向走一步，那么 (1)

X_n

离开某一个点之后，再回到这一个点，平均需要多少步？ (2)

X_n

在离开某一个点之后，回到这一个点之前已经访问到其它所有

个点的概率是多少？

这是一个很经典的离出分布和离出时间的问题，也是某一年的丘成桐大学生数学竞赛概率方向的考题。

建模上是不困难的，它的转移概率就是

p(i, i + 1) = p(i, i-1) = \frac 12 , 2 \le i \le 11

p(1, 12) = p(1, 2) = p (12, 1) = p(12, 11) = \frac 12

读者容易验证，这个是一个双随机链（见第2节的特殊的马尔科夫链部分）。简单来说，它的平稳分布就是一个均匀分布，因此有

\pi(x) = \frac 1 {E_x(T_x)} = \frac 1 {12}

当然也可以看出，这里的所有状态其实都是常返状态，涉及到平稳分布的计算的问题，一定要检查各个状态的常返性。

有了这个式子，很容易看出来

E_x(T_x) = 12

，这就是第一题的答案。

对于第二题，不妨假设

X_n

是从

开始移动的，那么因为一步一步的移动，所以如果要在回到

的时候，让

X_n

访问过从

到

的所有状态，实质上就可以得到答案是

\frac 12 P_1 (V_{11} < V_{12}) + \frac 12 P_{11}(V_1 < V_{12})

其中

V_y = \min \{n \ge 0: X_n = y\}

。

这个答案是怎么推出来的？首先不难看出这里要利用离出分布，那就是要弄清楚

P_x(V_a < V_b)

，也就是这里的

x, a, b

究竟是什么？这里的

很容易得到，就是

，但是

x, a

呢？注意到

是起点，那么这个题目，看似起点可以是

1, 2, \cdots, 11

，但是从

出发之后，下一步只会到达

和

，那么这样的话，如果到达

，那么很明显，到达

之前，如果先到达

，就一定到达了所有的状态。另外一个情况是类似的，所以这样就可以得到我们的计算目标。

这两个计算目标其实对应的是两个离出分布，剩下的就是“一步转移”的应用，这个可以对照第4节（随机过程（4）——返回时间，访问频率定理应用，离出分布，离出时间）的例子去看。结果是

P_1(V_{11} < V_{12}) = P_{11}(V_1 < V_{12}) = \frac 1 {11}

这个结果比较类似第4节的Problem 5。读者如果这个题很难验证，可以参考Problem 5也可以把

改成一个更小的数，这样会好计算一些。

Problem 4: 考虑Ehrenfest链，即满足转移概率为

p(i, i + 1) = \frac {N- i}{N}

，

p(i, i - 1) = \frac i N, 0 \le i \le N

。设

\mu_n = E_x(X_n)

为从

出发，回到

所需要的步数，证明

\mu_{n + 1} = 1 + (1 - \frac 2 N) \mu_n

，并且据此推断出最终的结论

\mu_n = \frac N 2 + (1 - \frac 2 N)^n(x - \frac N 2)

。

这一个题也不是严格的离出时间的问题，但是本质上的“一步转移”的思路是不变的，和Problem 3的推理也很相似。即考虑直接计算

E(X_{n+1}|X_n)

，再利用重期望公式。

注意到

E(X_{n + 1} |X_n) = (X_n + 1)\frac{N- X_n} N + (X_n - 1)\frac {X_n}N = 1 + X_n\frac{N - 2}N

重期望公式可以得到

E(X_{n + 1}) = 1 + \frac {N- 2} N E(X_n)

，这个就是我们的第一个式子。之后的一个式子实际上就是一个递推数列的问题，是高中数学竞赛的题目。假如说我们抽象这个式子为

a_{n + 1} = 1 + m a_n

那么两边加上

，同时我们还要做到凑出两边一致的结构，也即为

a_{n + 1} + k = m (a_n + k) = 1 + m a_n + k

这就说明了

km = 1 + k

，可以解出来

k = \frac 1 {m - 1}

。放到这个题目，就是可以得到

\mu_{n + 1} - \frac N 2 = (1 - \frac 2N)(\mu_n - \frac N 2)

那么注意到

\mu_0 = x

，剩下的推导相信对读者已经非常容易了，不写了可以吧？

Problem 5: 考虑一个投掷硬币的游戏。路人甲和路人乙分别会选择一个3个硬币组成的序列（由

和

，也就是字面和花面，组成）。一枚公平的硬币每一次都会投掷并由二人记录结果，哪一个序列先出现，哪位就会获胜。验证下面几个序列的选择和对应的路人乙的获胜概率 (1) 甲：

HHH

，乙：

THH

，获胜概率：

\frac 78

。 (2) 甲：

HHT

，乙：

THH

，获胜概率：

\frac 34

。 (3) 甲：

HTH

，乙：

HHT

，获胜概率：

\frac 23

。 (4) 甲：

HTT

，乙：

HHT

，获胜概率：

\frac 23

。

事实上这个题目说明了，无论甲选择什么序列，乙都能找到另外一个序列，使得自己获胜的概率不小于

\frac 23

，因为如果甲第一个序列选择了

，事实上只需要把

和

交换一下就可以了，它们俩的地位是相同的。

这个题实际上就是第4节的Problem 6，思路是一模一样的。当然事实上这个题也可以通过画出转移概率矩阵然后硬计算离出分布来得到，但这里可以看出，状态一共有8种，所以这个矩阵其实也不是特别好解。

我们只验证第3种情况，剩下的情况读者可以自己去验证。

对于第3种情况，要求的其实就是

P(T_{HHT} < T_{HTH})

（当然这里也可以写

，因为起点并不是

HHT

或者

HTH

），那么根据一步转移递推，我们有

P(T_{HHT} < T_{HTH}) = \frac 12 P_H(T_{HHT} < T_{HTH}) + \frac 12 P_T(T_{HHT} < T_{HTH})

= \frac 14P_{HH}(T_{HHT} < T_{HTH}) + \frac 14 P_{HT}(T_{HHT} < T_{HTH}) + \frac 12 P(T_{HHT} < T_{HTH})

这里的推导是因为

P_T(T_{HHT} < T_{HTH}) = P(T_{HHT} < T_{HTH})

，因为有了一个

之后，并不会有可能得到

HHT, HTH

中的一个，所以相当于这一次硬币没投。

接着往下，我们有

P_{HH}(T_{HHT} < T_{HTH}) = 1

，这是因为

P_{HH}(T_{HHT} < T_{HTH}) = \frac 12 P_{HHH}(T_{HHT} < T_{HTH}) + \frac 12 P_{HHT}(V_{HHT} < V_{HTH})

= \frac 12 P_{HH}(T_{HHT} < T_{HTH}) + \frac 12

直观来解释，相当于说，有了两个

之后，再投掷出一个

，就会直接导致

HHT

先出现，投掷出一个

，相当于回到了两个

，因为三个

并没有匹配上这两个中的任何一个，所以只能把最旧的那个结果去掉。所以简单来说，要不

HHT

先出现，要不就回到原点，那就会导致“

HHT

先出现”变成一个必然事件。

把这个结果代回，并对剩下的部分继续使用“一步转移”，我们有

\frac 14P_{HH}(T_{HHT} < T_{HTH}) + \frac 14 P_{HT}(T_{HHT} < T_{HTH}) + \frac 12 P(T_{HHT} < T_{HTH})

= \frac 14 + \frac 18 P(V_{HHT} < V_{HTH}) + 0 + \frac 12 P(T_{HHT} < T_{HTH})

这里

P_{HTT}(V_{HHT} < V_{HTH}) = P(V_{HHT} < V_{HTH})

，思路是一致的（去掉最旧的一个，变成

，

对所有开头是

的序列都没有任何作用，所以相当于没有）到最后解一下方程就可以了。

Problem 6: 考虑一个无限状态马尔可夫链，转移概率为

p(i, i - 1) = 1, i > 0

，

p(0, i) = p_i, i \ge 0

，证明它常返，但只有

\sum_n n p_n < \infty

的时候才是正常返。

这里对应第5节（随机过程（5）——无限状态马尔科夫链的进一步探讨，泊松分布引入，复合泊松分布）对无限状态马尔科夫链的一个讨论。事实上，在讨论它的性质的时候，我们所使用的其实依然是标准计算离出分布和离出时间的时候，“一步转移”的思路。

首先我们说明常返。这只需要说明

P_0(T_0 < \infty) = 1

。那么注意到我们有

P_0(T_0 < \infty) = p_0 P_0(V_0 < \infty) + \sum_{i = 1}^\infty p_i P_i(T_0 < \infty) = \sum_{i = 0}^\infty p_i = 1

这是因为

P_i(T_0 < \infty) = 1, i \ge 1

。所以这个很容易证明。至于正常返性，我们考虑求解

E_0(T_0)

，注意到

E_0(T_0) = 1 + \sum_{i = 0}^\infty p_i E_i(V_0) = 1 + \sum_{n = 1}^\infty n p_n

这里是因为

E_i(V_0) = i

，毕竟每一次都一定会往回退一步。

所以求和的式子如果是一个无穷大，那么对应就有

E_0(T_0) = \infty

，那就不是正常返了。所以第二个式子也完成了证明。

在进入泊松过程之前，强调一句，传统的离出分布和离出时间的计算题，已经在正文给出了，所以这里我们就没有再多提。

泊松过程

Problem 7: 考虑一个列车经过的问题。假如说两辆列车经过的间隔时间

服从

U(1, 2)

，并且旅客到达车站的数目服从一个速率为

的泊松过程，设

表示每一辆车可以登上的人数，计算它的均值和方差。

这个题目实际上就是要我们判断

N(T)

这个东西的均值和方差。但是明眼人可以看出来，这里的

和

N(\cdot)

都是变量，因此求解的时候必然要依赖条件期望和重期望公式。

注意到

E(X) = E(N(T)) = E(E(N(T)|T)) = E(24T) = 36

这里是因为

E(T) = \frac 32

，并且有

N(T) | T \sim Poisson(24 T)

，这是因为取了

作为条件之后，

N(T)

这个泊松过程中的

相当于变成了常量，所以这就变成了我们第5节后半部分一直讨论的标准的泊松过程。

对于方差，使用的也是同样的法子，注意到

Var(X) = E(Var(N(T)|T)) + Var(E(N(T)|T)) = E(24T)+Var(24T)

=24 \times \frac 32 + 24^2 \times \frac 1 {12} = 84

这就完成了这个题。这里对应上的其实就是第5节，复合泊松过程的部分。

Problem 8: 考虑一个速率为

\lambda

的泊松过程，设

为

[0, t]

内最后一次到达的时间，计算

E(t - L)

我们设

X = t- L

，那么这个问题的关键是，

的“最后一次到达”，究竟是第几次？如果没有到达，对应的就是

L = 0

，设

\tau_i

表示第

次与下一次到达的间隔时间，那么有

P(X = t) = P(L = 0) = P(\tau_1 > t) = e ^{-\lambda t}

但是如果有到达，这个时候对应的概率密度就不太一样了，因为

可能可以是很多情况，对于每一个情况，设

T_n

是到达时间，那么就会有

T_n = L, \tau_{n + 1}+ T_n > t

。根据这个结果，我们可以得出

f_X(x) = P(L = t -x) = \sum_{n = 1}^\infty P(T_n = t-x, \tau_{n + 1} >x)

注意到

T_n

和

\tau_{n + 1}

是具备独立性的，所以可以拆开这两个部分。另外，注意到

T_n = \sum_{i = 1}^n \tau_i

，这相当于

个独立同分布的指数分布相加，得到的是一个伽马分布

\Gamma(n,\lambda)

（可以参考《数理统计》的第1节（https://zhuanlan.zhihu.com/p/70018601））。所以代入它的密度函数，我们有

\sum_{n = 1}^\infty P(T_n = t-x, \tau_{n + 1} >x) = \sum_{n = 1}^\infty f_{T_n}(t - x) P(\tau_{n + 1} > x)

=\sum_{n = 1}^\infty \frac {\lambda^n (t-x)^{n - 1}}{(n -1)!} e^{-\lambda (t - x)} e^{-\lambda x} = \lambda e^{-\lambda x}

这个计算很明显是要利用Taylor展开的，这个技巧在概率论中也是极为常见，这里就不解释太多了，不懂得可以看概率论中，泊松分布是怎么计算期望和方差的。

关于泊松分布的三大变换，在正文都有对应的习题，这里也不再补充。

更新过程

Problem 9: 考虑一个医院的故事。急诊室进来的病人服从一个速率为

0.5

的泊松过程，即平均下来一个小时会来

0.5

个人。医生必须要在

0.6h

没有病人来的时候才可以睡觉。也就是说，一旦有病人进来，医生就必须重新开始工作，结束了

0.6h

之后才能睡觉。假设病人工作时间忽略不计，问 (1) 长期来看，医生大概有多少比例的时间在睡觉？ (2) 计算医生的平均醒来的时间。

这是一个很典型的更新奖赏过程（见第7节（随机过程（7）——更新奖赏过程：交替更新过程，生存与濒死时间，观察悖论）），对于第一个题来说，“奖赏”

r_i

就是医生睡觉的时间。但是要注意的是，这个时间是受制于上一个阶段的，因此必然还需要依赖条件期望。

具体来说，我们可以把它建模成这样的一个更新奖赏过程。这里的

t_i

就是两个病人到来间隔的时间，

r_i

定义在上面，那么如果

t_i > 0.6

，医生才有可能休息，所以可以得到

E(r_i) = E(t_i - 0.6 | t_i >0.6) P(t_i > 0.6) + 0 \times P(t_i < 0.6)

= \frac 1 {0.5}e^{-0.5 \times 0.6} = 2 e^{-0.3}

那么根据交替更新过程的定理，有

\frac {R(t)}{t} \to \frac {E(r_i)}{E(t_i)} = e^{-0.3}

这就是第一个问题的答案。

对于第二个问题，这相当于一个交替更新过程，因为先醒来，再睡着，睡着和醒来这两个状态一定是交替着的。那么对于这个问题，可以得到

\frac {E(s_i)}{E(u_i) + E(s_i)} = e^{-0.3}

其中

s_i

就是睡着的时间，

u_i

就是醒来的时间，

u_i + s_i = t_i

。这样的话，注意到

E(s_i) = 2

（这里用到的是指数分布的无记忆性，如果没有头绪的话记得回头看第7节），所以我们就可以得到

E(u_i) = 2 (e^{0.3} - 1)

。

Problem 10: 考虑一个风暴修车问题。雪地车在雪地进行作业，风暴来的时间服从速率为

的泊松过程，并且风暴来会摧毁雪地车。科学家每隔

时间就会检查一次，如果检查出雪地车被损毁，就会去把它修好。假设修好它的过程不需要时间，问 (1) 长期来看，雪地车作业时间的占比是多少？ (2) 假如说雪地车每一小时采集的数据的价值为

，但每一次检查都会消耗

c < a

的价值（这个价值你可以理解为人民币或美金）。计算最好的

，这里只需要提供计算过程，不需要提供最终结果。

这也是一个很明显的更新奖赏过程。那么最关键的地方就是，在两次科学家到来的时间间隔中，到底它会工作多长时间。

注意到如果设

是工作的时间，那么根据指数分布的无记忆性，有

X \sim \exp(1)

，这样的话，奖赏就是

r_i = X \land L

。那么这样的话，容易计算

E(r_i) = E(X \land L) = \int_0^\infty (x \land L) p(x) dx = \int_0^L x e ^{-x} dx + \int_L^\infty L e^{-x} dx

=-L e^{-L} - e^{-L} + 1 + Le^{-L} = 1 - e^{-L}

那么这个时候，根据定理，有

\frac {R(t)}t \to \frac {E(r_i)}{E(t_i)} = \frac { 1 - e^{- L}} L

这也就是第一个问题。

对于第二个问题，其实可以得到，在每一个单位的时间内，有

f(L) = a \frac {1 - e^{-L}} L - \frac c L

求导有

f'(L) = \frac { a L e^{-L} + a e^{-L} - a + c} {L^2} = 0

，解这个式子就可以了。

可以看出，对于更新奖赏过程的题目，如果要求诸如“极限比例”这样的问题，最关键的便是定义好

r_i

和

t_i

。

Problem 11: 考虑一个停车问题。停车场允许每一辆车停两个小时，且每两个小时，都会有人来巡逻。巡逻一次都会给在停车场的车打一个标记。如果一辆车有两个标记，就会被罚款。假如说一辆车停车的时间服从

U(0, 4)

，问多大的概率会被罚款？

这一个题有点摸不着头脑，其实是一个生存和濒死时间的问题，对应的是正文的第7节后半部分。定义

t_i

是我们的泊松过程的间隔时间，那么这个时候，我们定义

为第一次巡逻的人来的时候，

t_i

的剩余时间（也就是濒死时间），那么

的计算套用公式就可以了，也就是

f_Z(z) = \frac {P(t_i > z)}{E(t_i)} = \frac {1 - z /4} 2 I(0 < z < 4)

然后再求一个积分，就可以得到

P(Z > 2) = \frac 14

是答案。

这一个题目的关键是怎么定义出这个濒死时间。当然可能也有的人会问，为什么选择“第一次巡逻的人来的时间”作为我们的

的起点，这本质上还是一个指数分布无记忆性的应用，留给读者思考吧。

Problem 12: 已知一个机器的寿命服从

\Gamma(2, \lambda)

，问 (1) 它的生存时间的分布是什么？ (2) 如果使用泊松过程，理解为两个指数分布的和，如何求解这个问题？

第一个题很简单，直接计算

f(z) = \frac {P(t_1 > z)}{E(t_1)}

，注意到伽马分布的期望公式，有

E(t_1) = \frac 2 \lambda

，而至于分子，因为有

P(t_1 >z) = \int_z^\infty \lambda^2 x e^{-\lambda x} dx = \lambda z e^{-\lambda z} + e^{-\lambda z}

所以我们有

f(z) = \frac 12 \lambda^2 z e^{-\lambda z} + \frac 12 \lambda e^{-\lambda z}

。

掌握了生存和濒死时间的计算公式，就不难。不过其实我们的目的还是希望通过第二个题，来看一看不同的思考的视角。

考虑一个交替泊松过程，意思是红蓝两点交替，形成一个速率为

\lambda

的泊松过程，具体可以看下面这张图。

那么生存时间由什么决定呢？可以通过给红点和蓝点赋予不同的意义来解决。这里我们设蓝点表示“损坏”，这样如果单看蓝点，和本题是一致的。

注意到事实上，下一个点是红点还是蓝点，其实是等概率的。如果是红点的话，那么对应的就是正常，那么对应的密度函数就是

\Gamma(2, \lambda)

。如果是蓝点的话，相当于提前损坏，那么对应的密度函数就是

\exp(\lambda)

。所以最终的密度就是两个密度函数的等加权。就和我们上面的答案一样。

好的，剩下的题目，我们放到下一节说。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-02-27，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度