随机过程（4）——返回时间，访问频率定理应用，离出分布，离出时间

学弱猹

发布于 2021-08-10 11:31:47

1K0

发布于 2021-08-10 11:31:47

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

上一节笔记：随机过程（3）——无限状态的平稳测度，返回时间，访问频率：几个定理的证明

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

大家好！

经历了第三节之后，相信很多人对“随机过程随机过”这句话，有了更加深刻的体会……

在这一节，我们会结束大定理的这一部分，开始介绍它的应用，和离出分布相关的内容。

那么我们开始吧。

长期代价：函数形式的极限定理

上一节我们讨论了一些极限状态下，访问次数和返回时间的一些等价定理。这一部分是最后一个延伸，我们不仅仅是关注随机变量

X_n

本身的性质变化，也会开始关注

f(X_n)

的情况。也就是说，当它嵌套一个函数之后，结论会有什么变化，这就是这一部分所关注的内容。

Theorem 1: Long Run Cost 设马尔科夫链不可约，且存在平稳分布

\pi

，并且

\sum_x |f(x) | \pi_x < \infty

，那么有

\frac 1n \sum_{m = 1}^n f(X_m) \overset{n \to \infty} \rightarrow \sum_x f(x) \pi_x, a.s.

再提醒一遍，

a.s.

是almost surely的意思，但在应用层面，可以不管这个。

我们首先看一下式子的含义。很明显，左边就是观察随机变量从

m = 1

到

的取值情况，并且对

f(X_m)

求均值。那么这里我们的讨论思路和上一节的Theorem 3比较类似。对于某一个固定的状态

，我们讨论它每一次出现的时间。下面这张图描述了我们的想法。

现在我们设

Y_k = \sum_{m = T_{k - 1} + 1}^{T_k} f(X_m)

，

k \ge 1

，也就是每两个

之间所经过的其他状态的和。那么很明显，根据马尔科夫性，

Y_k

相互独立，并且同分布（不懂的可以看上一节Theorem 3的证明细节）。所以容易得到

\frac{Y_1 + \cdots + Y_k}{k} \to E(Y_2), k \to \infty

这是因为

Y_1

单独不会有什么大的影响，而

Y_2

之后的随机变量都是同分布的，所以利用强大数定律就可以得到这个结论。

写到这里，对于讨论左边的式子，还差一点。对于某个状态

，两个

出现的时间跨过了临界时间

，也完全有可能。所以我们这里要稍微拆一下，把式子写为

\frac 1n \sum_{m = 1}^n f(X_m) = \frac 1n \sum_{m = 1}^{T_{N_n(x)}} f(X_m) + \frac 1n \sum_{m = T_{N_n(x)} + 1}^n f(X_m)

如果不记得

N_n(x)

的定义了，记得翻上一节的Theorem 3。用图来表示，就是下面这个意思。

最后的一部分，因为下一个点

不再是

之前的了，所以相当于会“遗留一段”。这一段就对应了上面求和中，被拆分出来的第二段。

最后一部分，在

n \to \infty

的时候，可以忽略掉，毕竟求和的式子是有限值，否则就不是不可约了。所以接下来，我们只需要关心第一个分量就可以了。

注意到我们有

\frac 1n \sum_{m = 1}^{T_{N_n(x)}} f(X_m) = \frac 1n \sum_{l = 1} ^{N_n(x)} Y_l = \frac{N_n(x)}{n} \frac{1}{N_n(x)} \sum_{l = 1}^{N_n(x)}Y_l

这么写的原因是

\frac{N_n(x)}n

的极限，根据上一节的Theorem 3，我们有它趋近于

\frac 1 {E_x (T_x)}

。那么剩下的部分，自然容易看出它是一个时间的均值。但是这个时间的均值是多少，就要好好算一下了。而根据我们上面的推导，事实上最终就是对

E(Y_2)

这个量的求解。

注意到

E(Y_2)=E(\sum_{m = T_1 + 1}^{T_2} f(X_m)) = E(\sum_{m = T_1 }^{T_2 - 1} f(X_m)) = E_x(\sum_{m = 0}^{T_x - 1}f(X_m))

前几步的推导都不难看出原因。至于最后一个等号，其实就是因为，从

Y_2

开始的阶段，每一个时间事实上都是从一个

到另外一个

中间经过的时间，所以统一为最后一个写法，相当于把“任意起点”改成了“以

为起点”。

为了比较好的观察到我们的结论，我们把

X_m

拆开。具体来说，就是

E_x(\sum_{m = 0}^{T_x - 1}f(X_m)) = E_x(\sum_y f(y) \sum_{m = 0}^{T_x - 1} I(X_m = y)) = \sum_y f(y) E_x(\sum_{m = 0}^{T_x - 1} I(X_m = y))

那么注意到上一节我们提到过一个结论

\mu_x (y) = E_x (\sum_{n = 0}^{T_x - 1}I(X_n = y))

当时被用来更好的解释上一节Theorem 2中，step 1的证明思路。那么在这里，我们代入，就可以得到

E_x(\sum_{m = 0}^{T_x - 1}f(X_m)) = \sum_y f(y) \mu_x(y)

然后把这个式子再代回之前的推导，可以得到

\frac 1n \sum_{m = 1}^{T_{N_n(x)}} f(X_m) \to \frac{1}{E_x(T_x)}\sum_y f(y)\mu_x(y)

又因为

\frac{\mu_x(y)}{E_x(T_x)} = \pi_y

（这是因为

\sum_y \mu_x(y) = E_x(T_x)

），所以事实上，我们已经足够说明结论成立了。

这个结论最重要的就是把上一节所提到的平均返回时间定理（Theorem 4）做了一个推广，让这个“平均”有了更多的用武之地。事实上，读者可以验证，如果设

f(y) = I(x = y)

，那么得到的定理就是平均返回时间定理。

好的，我们终于可以开始举例子了。

Problem 1 考虑第2节的Problem 2，也即醉汉走路问题。分析为什么岔路口多的地方，醉汉更容易出现。

第2节（随机过程（2）——极限状态的平稳分布与周期（上），一些特殊的马尔科夫链）的Problem 2中，我们分析了每一个点的平稳分布为

\pi_u = \frac{d(u)}{\sum_u d(u)}

其中

d(u)

表示

结点的度。那么根据平均返回时间定理，我们有

\pi_u = \frac 1 {E_u(T_u)}

。所以很明显，

d(u)

越大，

\pi_u

就越大，

E_u(T_u)

就越小，换句话说醉汉从

出发，回到

的期望时间更短。如果相比较其他点，这个点的返回时间更短的话，也就不难理解为什么更容易在这个点发现醉汉了。

当然了，这里我们要假设图是一个连通图，或者在连通分量上讨论这个结论，否则会影响不可约性，也就不能使用平均返回时间定理。

Problem 2 考虑一个具备3个关键零件的机器，只要零件有2个在工作，机器就可以正常工作。如果有两个零件损坏，就会被立刻更换，保证机器继续工作。设零件1每天有

0.01

的概率损坏，零件2有

0.02

，零件3有

0.04

，并且假设一天内不会同时损坏两个及以上的零件，损坏事件相互独立，问在1800天的工作时长内，会更换多少零件1，零件2和零件3？

问题的描述看似比较抽象，但也就是一个状态转移的过程。我们假设有这么几个状态

[0, 1, 2, 3, 12, 13, 23]

表示没有零件损坏，

表示零件1损坏，

表示零件1，零件2都损坏，以此类推。那么根据这7个状态，可以写出它们的转移概率矩阵

P = \begin{bmatrix}0.93 & 0.01 & 0.02 & 0.04 & 0 & 0 & 0 \\ 0 & 0.94 & 0 & 0 & 0.02 & 0.04 & 0 \\ 0 & 0 & 0.95 & 0 & 0.01 & 0 & 0.04 \\ 0 & 0 & 0 & 0.97 & 0 & 0.01 & 0.02 \\ 1 & 0 & 0 & 0& 0& 0&0 \\ 1 & 0 & 0 & 0& 0& 0&0 \\ 1 & 0 & 0 & 0& 0& 0&0 \\\end{bmatrix}

从左到右，从上到下，按照上面所写的状态顺序。比方说左上角，就是“从

到

转移的概率为

0.93

”，这是因为一天不会同时损坏多个零件。

这个概率矩阵的平稳分布计算绝对不是一个善茬，利用matlab，这里直接给出结果

\pi = [\frac {3000}{8190}, \frac{500}{8190}, \frac{1200}{8190}, \frac{4000}{8190}, \frac{22}{8190}, \frac{60}{8190}, \frac{128}{8190}]

那么对于零件1，我们可以得到时间大致为

1800 * (\pi_{12} + \pi_{13}) = 17

天，这里因为更换是立刻发生的，而状态

12, 13

是两种需要更换零件1的情形（不会出现状态

123

）。另外结合之前的渐近频率定理（Theorem 3），我们可以知道，

\pi_{12}

就是零件1和零件2都损坏的极限频率比（

\frac{N_n(y)}{n}

），因此乘上时间1800天，就可以得到大约的，零件1和零件2都损坏的时间，也就是会被更换的时间。

多说一句，直译说“更换了17天的零件1”听起来有些拗口。但是如果每一次更换都不需要时间（正如本题一样），那么就不好量化“更换次数”这个概念了。

类比可以计算，零件2的更换时间为

天，零件3为

天。很有趣的事情在于，虽然它们损坏的概率是

1:2:4

，但是最终更换的时间并不是严格的

1:2:4

的比例。

Problem 3 考虑一个库存管理问题。已知货物最多有3个，卖出

0, 1, 2, 3

个货物的概率分别为

0.3, 0.4, 0.2, 0.1

，每一天卖出一个货物，可以获得

\$12

的收益，而每一个未卖出的货物，每一天都会收

\$2

的折旧费。现在考虑

(s, S)

管理策略，也就是说，如果货物数量不超过

，那么就购买货物，使得货物数量变为

个。试找到最好的策略

(s, S)

，使得销售的期望收益最大。

这个题是比较复杂的，情况一共有6种（因为

S \le 3, s < S

），这里我们只讨论

(1, 3)

的计算，读者可以自己计算其它的五种。

对于

(1, 3)

，我们可以写出这样的转移矩阵

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

从左到右，从上到下分别对应状态

(0, 1, 2, 3)

，比方说

p(0, 0) = 0.1

，是因为

的时候，会通过策略使得货物变为

个，然后卖出

个概率为

0.1

。

还是一样，这样的题很明显，也是一个需要依赖平稳分布的题目。通过matlab计算平稳分布，可以得到

\pi = [\frac{19}{110}, \frac{30}{110}, \frac{40}{110}, \frac{21}{110}]

比方说

\pi_1 = \frac {30}{110}

，根据渐近频率定理，相当于说，货物为1个的时间差不多占据了

\frac{30}{110}

。因此可以通过这个，先算出一个平均的折旧费

2\pi_1 + 4\pi_2 + 6\pi_3 = 3.15

那么获利怎么算呢？看似很简单，根据卖出货物的概率，可以算出一个期望

0.4 \times 12 + 0.2 \times 24 + 0.1 \times 36 = 13.2

但是有一个问题，就是并不是所有的情况都适合于这个式子，很多时候我们想卖的数量多于库存，那就卖不到我们想要的个数。比方说在这里，有一个例外是，当我们存量为2的时候，希望卖出3个，这就最多卖出2个，相当于损失了1个。因此计算的时候，这一部分的获利要去掉。所以最终的获益是

13.2 - \pi_2 \times 0.1 \times 12 = 12.76

所以最终可以得到收益为

9.61

（读者可以自己检验没有其它例外，存量为1的时候，根据策略，会自动补成3）。注意这个收益只是一个期望值，但是每一个策略，它们的比较标准都是一致的，因此不影响我们的比较选择。

类似的，可以算出

(2,3)

的收益是

9.40

，

(0, 3)

的收益是

9.11

。而当

S < 3

的时候，其实结果会更差，但我们这里就不多说了。

好的，这一部分我们总算是讲完了。

离出分布

离出分布（exit distribution）是一种特殊的马尔科夫链所具备的性质。有的马尔科夫链的某些状态将具备一种“黑洞”的性质，也就是说，进入这个状态之后，就再也无法逃脱，相当于“退出了主流的马尔科夫链的状态转移”。这种情况平稳分布对应的定理就会失效，因为马尔科夫链不再具备不可约性，这个时候相关的问题，就是离出分布这一部分的主要内容。

下面这个定理就是离出分布的主要定理。虽然定理本身可能比较抽象（如果你认真读完第三节，这个定理的难度就不算啥了），但是它所带来的这一类问题的解决方案，却是直观而易用的。

Theorem 2: 考虑一个状态空间为

的马尔科夫链。给定集合

，设

V_F = \min \{n \ge 0: X_n \in F\}

表示第一次状态进入集合

的时间，

A, B

为不交的

的子集，且

C = S - A \cup B

是一个有限集，设

h(a) = 1, a \in A

，

h(b) = 0, b \in B

，并且对

x \in C

，有

h(x) = \sum_y p(x, y) h(y)

。那么只要

P_x(V_A \land V_B < \infty) > 0

，那么

h(x) = P_x(V_A < V_B)

。

请记住这个

的含义，后面会频繁使用它。

这里的

V_A \land V_B

可以理解为

\min \{V_A, V_B\}

的意思。而我们要证明的

h(x)

的性质，其实含义就是“从

出发，先会进入

的概率”。那么假如说

表示之前提到的“黑洞”，这个概率自然就是状态“从

退出”的概率。

至于集合的关系，下图画的更加明显一些。

首先我们来看看

h(x)

的定义。很明显，对

x \in C

，

x \not \in C

，结果会不一样。如果

x \not \in C

，注意到

A, B

都是黑洞，所以这个时候，

h(x)

是固定的。但是如果

x \in C

，这个时候，注意到

h(x) = \sum_{y \in S} p(x, y)h(y)

这个定义，它和我们的概率转移公式是不是长得一样？所以这个时候，可以对应上的是，它是从

出发，做了一步状态转移得到的结果。这个观察可以让我们推出这么一个结论

h(x) = E_x (h(X_{T \land 1}))

因为两种情况分别对应了

T = 0

和

T \ge 1

，这里的

就是状态掉入黑洞所经过的时间

V_A \land V_B

。

这个观察可以让我们接着向后推广。我们有理由相信

h(x) = E_x (h(X_{T \land n})), \forall n

因为我们走了一步之后，到达下一个状态，如果一开始

就在黑洞内，那么下一步依然会在黑洞。如果不在，那么下一步还是在

中。简而言之，在下一个状态下，

所处的状态和上一个状态一模一样，上一个状态的转移没有对分析造成任何影响。所以不管

取多少，转移多少次，我们只要走相同的分析，就能推出这个期望依然是

h(x)

。

如果是这样，根据控制收敛定理（在第三节的最后有用到过，是实分析的内容），我们有

h(x) = E_x (h(X_T)) = E_x (h(X_{V_A}))I(V_A < V_B) + E_x(h(X_{V_B}))I(V_B < V_A) = P_x(V_A < V_B)

所以这么推导，结论就成立了。但是为了严谨，我们要把中间那个

h(x)

的表达式，用数学归纳法推一遍。

Lemma 1: 证明

h(x) = E_x (h(X_{T \land n})), \forall n

首先

h(x) = E_x (h(X_{T \land 1}))

很好说明，按照上面思路走就好，留给读者。现在假如说

h(x) = E_x(h(X_{T \land n}))

成立，我们要证明

n + 1

的情况同样成立。在这种情况下，分开来看，我们有

E_x(h(X_{T \land n})) = E_x(h(X_T))I(T \le n) + E_x(h(X_n)) I(T >n)

= E_x(h(X_T))I(T < n + 1) + E_x(h(X_n)) I(T >n)

所以前半部分其实不用推，如果能够推出来后半部分是

E_x(h(X_{n + 1}))I(T > n)

，就可以得到

h(x) = E_x(h(X_{T \land n + 1}))

，那么数学归纳法就证好了。

我们先看后半部分，因为后半部分的

X_n

是一个固定的常数，好讨论一些。注意到

E_x(h(X_n)) I(T >n) = \sum_{y \in C} h(y) P(X_0, \cdots, X_{n} \in C, X_n = y |X_0 = x)

= \sum_{y \in C} \sum_{z \in S} h(z) p(y, z) P(X_0, \cdots, X_{n} \in C, X_n = y | X_0 = x)

= \sum_{z \in S} h(z) P(X_{n + 1} = z ,X_0, \cdots, X_{n} \in C | X_0 = x) = E_x(h(X_{n + 1}))I(T >n)

第一行是翻译了

T > n

的含义，第二行则是代入定义，讨论了从

到

n + 1

步状态可能的转移情况。第三行则是利用了全概率公式。

到此，我们就完成了证明。但是其实还可以简单做一个延伸，我们可以推出下面这个结论。

Proposition 1: 证明在

P_x(T < \infty) > 0

的条件下，有

P_x(T < \infty) = 1

。

如果这个定理成立，说明在有限时间内，几乎（almost surely）可以肯定状态在有限时间内掉入黑洞。

要证明这个，其实只需要说明

P_x(T = \infty) = 0

。这个不是很困难，因为如果

x \not \in C

，那没什么好说的。如果

x \in C

，那么因为

P_x(T < \infty) > 0

，所以对于某一个

而言，一定会存在

k_x, \alpha_x

，使得

P_x(T \le k_x) \ge \alpha_x

（这是数学分析的基本结论，如果不能理解，说明数分的基本内容都没有掌握）。结合

是有一个有限集，可以得到

P_x (T \le k) \ge \alpha, \forall x

因为相当于把每一个

k_x, \alpha_x

取了一个最大值和最小值。

有了这个之后，我们不难得到的是

P_x(T > k) < 1 - \alpha

，那么根据我们第1节（随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态）的Proposition 4，我们就有

P_x(T > nk) < (1-\alpha)^n

。令

n \to \infty

就可以得到结论。

这个定理刻画了离出分布，但是很明显具备一些局限性，就是它需要保证只能有两类黑洞状态

A, B

。我们后面举的例子，也符合这里定理的要求。而这个定理提供了一个解决这种问题的一个有力的工具。

Problem 4 考虑一个两年社区大学的随机过程，一共有四个状态

(1, 2, G, D)

，

1, 2

表示学生在上一年级和二年级。

表示毕业，

表示退学。其转移概率矩阵为

P = \begin{bmatrix}0.25 & 0.6 & 0 & 0.15 \\ 0 & 0.2 & 0.7 & 0.1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

（从上到下，从左到右），问一，二年级学生有多少概率会毕业？

这就是一个典型的离出分布的问题，而这里的“毕业”和“退学”状态，就是之前定理所说的两个黑洞状态，分别设为

A, B

（也就是说它们俩都是单点集）。这是因为一旦走到了

G, D

，就再也没办法逃脱了，下一个状态只会是自己，不会转移到别的状态。

如果要问毕业的概率，其实在这里就是

P_x(V_G < V_D)

（想想为什么？）。如果问一年级学生，那么就是

P_1(V_G < V_D)

。所以我们设

h(x) = P_x(V_G < V_D)

。那么根据上面的定理，我们有

h(G) = 1, h(D) = 0

，并且

\begin{cases}h(1) = 0.25 h(1) + 0.6 h(2) \\ h(2) = 0.2 h(2) + 0.7\end{cases}

和矩阵元素对应一下，相信可以发现这个等式的对应关系，不难写出来，因为它就是我们通过“一步转移”思路得到的式子。比方说第一个式子

h(1) = 0.25 h(1) + 0.6 h(2)

表示从

出发，下一步有0.25概率到

，0.6的概率到

。所以

h(1)

的情况可以被归结为

0.25h(1) + 0.6 h(2)

，这也是我们定理证明的一个思路的运用。

解这个方程组，就可以得到

h(2) = 0.875, h(1) =0.7

，也就是说，一年级学生毕业的概率为70%，二年级为87.5%。

Problem 5 考虑一个公平的赌博游戏。路人甲有15枚硬币，路人乙有10枚硬币。每一局，两个人都各有

\frac 12

的概率获胜，获胜者要从对方手里拿走一枚硬币。当一个人拥有了全部硬币，游戏结束，且他获得胜利。问路人甲获胜的概率。

这个问题建模也不难，假如说状态

是路人甲所拥有的硬币数，那么这个问题就等价于问

P_{15}(V_{25} < V_0)

，状态

0, 25

就是两个黑洞，因为一旦到达，游戏就结束了，自然不可能再说有“转移到其他状态”的可能。

设

h(x) = P_x(V_{25} < V_0)

，那么

h(25) = 1, h(0) = 0

，并且根据“一步转移”，我们有

h(x) = \frac 12 h(x - 1) + \frac 12 h(x+ 1), 1 \le x \le 24

（有

\frac 12

的概率到

x-1

，有

\frac 12

的概率到

x + 1

）化简一下，可以得到

h(x+1) - h(x) = h(x) - h(x- 1)

所以

关于离散点是一个等差数列，因此可以直接得到

h(15) = 0.6

，也就是这个题的答案。

离出时间

离出分布的一个类似的问题就是离出时间（exit time）。离出时间的场景和离出分布一致，研究的问题稍有不同。它关注的是状态多久会进入黑洞。注意，这就体现出我们这一节Proposition 1的作用了。因为如果你不知道它是“一定会进入黑洞的”，你又怎么敢讨论它能“多快”进入黑洞呢？

下面是离出时间的定理。和离出分布一样，这个定理也告诉我们了应该如何解决这一类问题。

Theorem 3: 考虑一个状态空间为

的马尔科夫链，

A \subset S

，且

C = S - A

是有限集合，

P_x(V_A < \infty) > 0, \forall x \in C

。设

g(a) = 0, a \in A

，且

g(x) = 1 + \sum_{y \in S} p(x, y)g(y), x \in C

，那么

g(x) = E_x V_A

。

这里的

E_x (V_A)

就是从

出发，第一次到达

的时间。

这个定理的证明非常类似，如果

x \in A

（也就是

x \not \in C

），那么根据定义，

g(x) = 0 = E_x (V_A)

，结论成立。如果

x \in C

，那么容易得到

g(x) = 1 + \sum_{y \in S} p(x, y)g(y) = 1 + E_x (g(X_1)) = E_x (V_A) \land 1 + E_x (g(X_{V_A \land 1})), x \in S

因此我们有

g(x) = E_x (V_A )\land 1 + E_x (g(X_{V_A \land 1})), x \in S

。根据和之前一模一样的讨论，我们有

g(x) = E_x (V_A) \land n + E_x( g(X_{V_A \land n})), x \in S, \forall n

证明细节我们交给读者。把

E_x( g(X_{V_A \land n}))

按照

V_A, n

的大小关系拆分一下就可以了。

现在按照常理，应该令

n \to \infty

，但是在这之前需要说明

E_x V_A

是有限的，否则第一项就不好处理（很多人觉得看似可以直接得到第一项，在

n \to \infty

的时候就是

E_x V_A

。但是为了严谨性，我们还是要说明这一点。否则得到一个

E_xV_A = \infty

，在应用层面上也毫无价值）。

注意到和Theorem 2一样的推导（第1节的Proposition 4），我们可以利用

P_x(V_A < \infty) > 0

，得到

\exists k, \alpha, s.t. P_x(V_A > kn) \le (1 - \alpha)^n

因此可以每一段做一个放缩，得到

E_x (V_A) = \sum_{m = 1}^\infty P(V_A \ge m) \le k P(V_A >0) + kP(V_A > k) + \cdots

\le k \sum_{i = 0}^\infty(1-\alpha)^i < \infty

所以这一部分也说明白了。

最后就是利用控制收敛定理，我们有

E_x(g(X_{V_A \land n})) \to E_x g(X_{V_A}) = 0

加在一起就可以得到

g(x) = E_x(V_A)

。

通过这个定理可以看出，我们只有一类的黑洞状态。换句话说，我们只能够回答一种“通用，模糊”的到达时间的问题。具体跌，可以看下面的例子。

Problem 5 考虑Problem 3的情景，问一个一，二年级学生平均需要多长时间，才能够毕业或退学。

这里的“毕业或退学”，就体现了“模糊”的含义。而这个，其实也就是

E_xV_A

，其中

A = \{G, D\}

。

设

g(x) = E_x V_A

，那么

g(G) = g(D) = 0

，且根据定理，我们也可以得到下面的方程组

\begin{cases} g(1) = 1 + 0.25 g(1) + 0.6 g(2) \\ g(2) = 1 + 0.2 g(2) \end{cases}

理解的思路和离出分布差不多，除了转移的时候要加一个1，因为转移一次，走了一步，需要消耗一个单位的时间。

解这个方程组，可以得到

g(1) = \frac 73

，

g(2) = 1.25

。简单来说就是，一年级学生平均需要

\frac 73

年毕业，二年级学生平均需要

1.25

年毕业。

Problem 6 考虑掷硬币游戏。问平均需要等几轮，才能第一次看到最近的两轮中，第一轮是

，第二轮是

。这里

是head，

是tail的意思。

这一个问题不是直接代入公式就可以解决的，而是需要真正理解定理来做的。我们来分析一下这个问题。

首先，状态是不难定义的。我们可以写出四个状态

[HH, HT, TH, TT]

比方说

就表示最近的两轮都是

。那么这样的话，转移概率矩阵就可以写成

P = \begin{bmatrix}\frac 12 & \frac 12 & 0 & 0 \\ 0 & 0 & \frac 12 & \frac 12 \\ \frac 12 & \frac12 & 0 & 0 \\ 0 & 0 & \frac 12 & \frac 12\end{bmatrix}

从左到右，从上到下对应了上面所写的状态顺序。

注意到

E(T_{HT}) = 1 + \frac 12 E_T(V_{HT}) + \frac 12 E_T(V_{HT}) = 1 + \frac 12 E_T(T_{HT}) + \frac 12 E_H(T_{HT})

因为

E(T_{HT})

相当于寻找在一开始状态为空的时候，能够得到

的最少次数的平均值（这种情况它和

E(V_{HT})

是相同的，但是如果一开始的状态是

，情况就不一样了。换句话说，

E_{HT}(V_{HT}) = 0

，但是

E_{HT}(T_{HT})

不是）。那么投掷一次之后，花费了一步时间，并且有

\frac 12

的概率得到

，

\frac 12

的概率得到

。

接下来，注意到

E_T(T_{HT}) = E(T_{HT})

（因为从

出发，下一步只能得到

TH, TT

，得不到

，所以和一开始状态为空出发，并没有什么区别），我们可以适当化简，得到。

\frac 12 E(T_{HT}) = 1 + \frac 12 E_H(T_{HT})

现在我们计算

E_H(T_{HT})

。那么同样的思路，我们有

E_H(T_{HT}) = 1 + \frac 12 E_{HT}(V_{HT}) + \frac 12 E_{HH}(V_{HT}) = 1 + \frac 12 E_H(V_{HT})

这里

E_{HH}(V_{HT}) = E_H(V_{HT})

的原因类似，一开始状态为

，和一开始状态为

，在这个问题的语境下（只关心最近两次的硬币正反面）是没有区别的。

所以

E_H(T_{HT}) = E_H(V_{HT}) = 2

，再带回，就可以得到

E(T_{HT}) = 4

。

这一个题目乍一看和离出时间的语境是不相关的，我们并没有什么所谓的黑洞状态。但是这种“一步转移”的思路却贯穿始终，同时对问题的分析可以使得我们对问题的理解得到简化。同时也要注意，这个题同样不能够直接使用平稳分布来进行计算。因为我们只有

\pi_y = \frac 1 {E_y (T_y)}

，并没有

E(T_y)

的式子。

类似的思路，读者可以自己计算出

E(T_{TT}) = 6

。如果可以独立推导出来，说明这一个思路已经掌握了。这也是一个很好的练习。

好的，关于离出时间，我们就说这么多。

小结

本节我们对上一节最后的渐近频率定理，以及平均返回时间定理做了一个推广。结束这些定理之后，我们介绍了离出分布和离出时间的概念，并且举了一些实际应用的例子。从理论层面上来说，一步转移的核心在于马尔可夫链的“无记忆性”，而从应用层面上，对于一部转移的灵活使用也是解复杂题目的必需技能。

下一节我们会开始进一步介绍无限状态马尔可夫链。如果有足够的空间的话，我们就会开始介绍被广泛应用的泊松分布。

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

原始发表：2020-12-19，如有侵权请联系 cloudcommunity@tencent.com 删除

网站

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

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

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

网站