讯阳文艺网随机过程习题集
上一节笔记：随机过程（D）——鞅的极限性质的应用，布朗运动概述
————————————————————————————————————
大家好！
这一节开始我们进入习题课。我们会对于每一个部分的内容给出一些习题，并计划以计算题为主，证明题为辅。注意到在每一节的正文其实或多或少都有一些题目用于概念和性质的理解和应用，所以在这里我们挑选的题目不会特别简单，更多的是需要一些思考或计算的题目，这也是我一直写习题课保持的一个习惯。
那么我们开始吧。
马尔科夫链Problem 1:
考虑下面这个转移概率矩阵，判断其中的常返与瞬时状态。
这一个题的解决方案很简单，就是画一张有向图。对应下面这个图。
这样的话，找出环之后，会发现剩下的两个点，到达集合内的某个点之后就“无法逃逸”了，因此根据第2节（随机过程（2）——极限状态的平稳分布与周期（上），一些特殊的马尔科夫链）的开头的例子就可以得到，是瞬时状态，其余的4个为常返状态。
Problem 2:
考虑状态，从左到右，从上到下排序，且转移概率矩阵为，证明
这个题本质上可以理解为是一个马尔可夫性对应条件概率的应用，对应的法子我们在第1节其实说过，就是利用乘法公式。注意到
Problem 3:
考虑一个时钟上的随机游走问题。时钟上有共12个点，设为第步所在的位置，并且假设每一次，都会等概率的往顺时针/逆时针方向走一步，那么
(1) 离开某一个点之后，再回到这一个点，平均需要多少步？
(2) 在离开某一个点之后，回到这一个点之前已经访问到其它所有个点的概率是多少？
这是一个很经典的离出分布和离出时间的问题，也是某一年的丘成桐大学生数学竞赛概率方向的考题。
建模上是不困难的，它的转移概率就是
读者容易验证，这个是一个双随机链（见第2节的特殊的马尔科夫链部分）。简单来说，它的平稳分布就是一个均匀分布，因此有
当然也可以看出，这里的所有状态其实都是常返状态，涉及到平稳分布的计算的问题，一定要检查各个状态的常返性。
有了这个式子，很容易看出来，这就是第一题的答案。
对于第二题，不妨假设是从开始移动的，那么因为一步一步的移动，所以如果要在回到的时候，让访问过从到的所有状态，实质上就可以得到答案是
其中。
这个答案是怎么推出来的？首先不难看出这里要利用离出分布，那就是要弄清楚，也就是这里的究竟是什么？这里的很容易得到，就是，但是呢？注意到是起点，那么这个题目，看似起点可以是，但是从出发之后，下一步只会到达和，那么这样的话，如果到达，那么很明显，到达之前，如果先到达，就一定到达了所有的状态。另外一个情况是类似的，所以这样就可以得到我们的计算目标。
这两个计算目标其实对应的是两个离出分布，剩下的就是“一步转移”的应用，这个可以对照第4节（随机过程（4）——返回时间，访问频率定理应用，离出分布，离出时间）的例子去看。结果是
这个结果比较类似第4节的Problem 5。读者如果这个题很难验证，可以参考Problem 5也可以把改成一个更小的数，这样会好计算一些。
Problem 4:
考虑Ehrenfest链，即满足转移概率为，。设为从出发，回到所需要的步数，证明，并且据此推断出最终的结论。
这一个题也不是严格的离出时间的问题，但是本质上的“一步转移”的思路是不变的，和Problem 3的推理也很相似。即考虑直接计算，再利用重期望公式。
注意到
那么两边加上，同时我们还要做到凑出两边一致的结构，也即为
这就说明了，可以解出来。放到这个题目，就是可以得到
那么注意到，剩下的推导相信对读者已经非常容易了，不写了可以吧？
Problem 5:
考虑一个投掷硬币的游戏。路人甲和路人乙分别会选择一个3个硬币组成的序列（由和，也就是字面和花面，组成）。一枚公平的硬币每一次都会投掷并由二人记录结果，哪一个序列先出现，哪位就会获胜。验证下面几个序列的选择和对应的路人乙的获胜概率
(1) 甲：，乙：，获胜概率：。
(2) 甲：，乙：，获胜概率：。
(3) 甲：，乙：，获胜概率：。
(4) 甲：，乙：，获胜概率：。
事实上这个题目说明了，无论甲选择什么序列，乙都能找到另外一个序列，使得自己获胜的概率不小于，因为如果甲第一个序列选择了，事实上只需要把和交换一下就可以了，它们俩的地位是相同的。
这个题实际上就是第4节的Problem 6，思路是一模一样的。当然事实上这个题也可以通过画出转移概率矩阵然后硬计算离出分布来得到，但这里可以看出，状态一共有8种，所以这个矩阵其实也不是特别好解。
我们只验证第3种情况，剩下的情况读者可以自己去验证。
对于第3种情况，要求的其实就是（当然这里也可以写，因为起点并不是或者），那么根据一步转移递推，我们有
接着往下，我们有，这是因为
把这个结果代回，并对剩下的部分继续使用“一步转移”，我们有
Problem 6:
考虑一个无限状态马尔可夫链，转移概率为 0″ data-formula-type=”inline-equation” style=””>，，证明它常返，但只有的时候才是正常返。
这里对应第5节（随机过程（5）——无限状态马尔科夫链的进一步探讨，泊松分布引入，复合泊松分布）对无限状态马尔科夫链的一个讨论。事实上，在讨论它的性质的时候，我们所使用的其实依然是标准计算离出分布和离出时间的时候，“一步转移”的思路。
首先我们说明常返。这只需要说明。那么注意到我们有
所以求和的式子如果是一个无穷大，那么对应就有，那就不是正常返了。所以第二个式子也完成了证明。
在进入泊松过程之前，强调一句，传统的离出分布和离出时间的计算题，已经在正文给出了，所以这里我们就没有再多提。
泊松过程Problem 7:
考虑一个列车经过的问题。假如说两辆列车经过的间隔时间服从，并且旅客到达车站的数目服从一个速率为的泊松过程，设表示每一辆车可以登上的人数，计算它的均值和方差。
这个题目实际上就是要我们判断这个东西的均值和方差。但是明眼人可以看出来，这里的和都是变量，因此求解的时候必然要依赖条件期望和重期望公式。
注意到
对于方差，使用的也是同样的法子，注意到
Problem 8:
考虑一个速率为的泊松过程，设为内最后一次到达的时间，计算
我们设，那么这个问题的关键是，的“最后一次到达”，究竟是第几次？如果没有到达，对应的就是，设表示第次与下一次到达的间隔时间，那么有
t) = e ^{-lambda t}” data-formula-type=”inline-equation” style=””>
但是如果有到达，这个时候对应的概率密度就不太一样了，因为可能可以是很多情况，对于每一个情况，设是到达时间，那么就会有 t” data-formula-type=”inline-equation” style=””>。根据这个结果，我们可以得出
x)
” data-formula-type=”block-equation” style=” text-align: center; overflow: auto; “>注意到和是具备独立性的，所以可以拆开这两个部分。另外，注意到，这相当于个独立同分布的指数分布相加，得到的是一个伽马分布（可以参考《数理统计》的第1节（https://zhuanlan.zhihu.com/p/70018601））。所以代入它的密度函数，我们有
x) = sum_{n = 1}^infty f_{T_n}(t – x) P(tau_{n + 1} > x)
” data-formula-type=”block-equation” style=” text-align: center; overflow: auto; “>
关于泊松分布的三大变换，在正文都有对应的习题，这里也不再补充。
更新过程Problem 9:
考虑一个医院的故事。急诊室进来的病人服从一个速率为的泊松过程，即平均下来一个小时会来个人。医生必须要在没有病人来的时候才可以睡觉。也就是说，一旦有病人进来，医生就必须重新开始工作，结束了之后才能睡觉。假设病人工作时间忽略不计，问
(1) 长期来看，医生大概有多少比例的时间在睡觉？
(2) 计算医生的平均醒来的时间。
这是一个很典型的更新奖赏过程（见第7节（随机过程（7）——更新奖赏过程：交替更新过程，生存与濒死时间，观察悖论）），对于第一个题来说，“奖赏”就是医生睡觉的时间。但是要注意的是，这个时间是受制于上一个阶段的，因此必然还需要依赖条件期望。
具体来说，我们可以把它建模成这样的一个更新奖赏过程。这里的就是两个病人到来间隔的时间，定义在上面，那么如果 0.6″ data-formula-type=”inline-equation” style=””>，医生才有可能休息，所以可以得到
0.6) P(t_i > 0.6) + 0 times P(t_i < 0.6) " data-formula-type="block-equation" style="text-align: center;overflow: auto;">
这就是第一个问题的答案。
对于第二个问题，这相当于一个交替更新过程，因为先醒来，再睡着，睡着和醒来这两个状态一定是交替着的。那么对于这个问题，可以得到
Problem 10:
考虑一个风暴修车问题。雪地车在雪地进行作业，风暴来的时间服从速率为的泊松过程，并且风暴来会摧毁雪地车。科学家每隔时间就会检查一次，如果检查出雪地车被损毁，就会去把它修好。假设修好它的过程不需要时间，问
(1) 长期来看，雪地车作业时间的占比是多少？
(2) 假如说雪地车每一小时采集的数据的价值为，但每一次检查都会消耗的价值（这个价值你可以理解为人民币或美金）。计算最好的，这里只需要提供计算过程，不需要提供最终结果。
这也是一个很明显的更新奖赏过程。那么最关键的地方就是，在两次科学家到来的时间间隔中，到底它会工作多长时间。
注意到如果设是工作的时间，那么根据指数分布的无记忆性，有，这样的话，奖赏就是。那么这样的话，容易计算
对于第二个问题，其实可以得到，在每一个单位的时间内，有
求导有，解这个式子就可以了。
可以看出，对于更新奖赏过程的题目，如果要求诸如“极限比例”这样的问题，最关键的便是定义好和。
Problem 11:
考虑一个停车问题。停车场允许每一辆车停两个小时，且每两个小时，都会有人来巡逻。巡逻一次都会给在停车场的车打一个标记。如果一辆车有两个标记，就会被罚款。假如说一辆车停车的时间服从，问多大的概率会被罚款？
这一个题有点摸不着头脑，其实是一个生存和濒死时间的问题，对应的是正文的第7节后半部分。定义是我们的泊松过程的间隔时间，那么这个时候，我们定义为第一次巡逻的人来的时候，的剩余时间（也就是濒死时间），那么的计算套用公式就可以了，也就是
z)}{E(t_i)} = frac {1 – z /4} 2 I(0
然后再求一个积分，就可以得到 2) = frac 14″ data-formula-type=”inline-equation” style=””>是答案。
这一个题目的关键是怎么定义出这个濒死时间。当然可能也有的人会问，为什么选择“第一次巡逻的人来的时间”作为我们的的起点，这本质上还是一个指数分布无记忆性的应用，留给读者思考吧。
Problem 12:
已知一个机器的寿命服从，问
(1) 它的生存时间的分布是什么？
(2) 如果使用泊松过程，理解为两个指数分布的和，如何求解这个问题？
第一个题很简单，直接计算 z)}{E(t_1)}” data-formula-type=”inline-equation” style=””>，注意到伽马分布的期望公式，有，而至于分子，因为有
z) = int_z^infty lambda^2 x e^{-lambda x} dx = lambda z e^{-lambda z} + e^{-lambda z}
” data-formula-type=”block-equation” style=” text-align: center; overflow: auto; “>所以我们有。
掌握了生存和濒死时间的计算公式，就不难。不过其实我们的目的还是希望通过第二个题，来看一看不同的思考的视角。
考虑一个交替泊松过程，意思是红蓝两点交替，形成一个速率为的泊松过程，具体可以看下面这张图。
那么生存时间由什么决定呢？可以通过给红点和蓝点赋予不同的意义来解决。这里我们设蓝点表示“损坏”，这样如果单看蓝点，和本题是一致的。
注意到事实上，下一个点是红点还是蓝点，其实是等概率的。如果是红点的话，那么对应的就是正常，那么对应的密度函数就是。如果是蓝点的话，相当于提前损坏，那么对应的密度函数就是。所以最终的密度就是两个密度函数的等加权。就和我们上面的答案一样。
好的，剩下的题目，我们放到下一节说。
扫码关注我们
学弱猹的精品小屋
知乎学弱猹，厦门大学计算数学系16级本科，教育部“拔尖计划”成员，从事互联网数据算法相关工作。乐于数学，编程类知识分享，阅读量300w+
