随机过程（F）——习题课（连续时间马尔科夫链-布朗运动）

学弱猹

发布于 2021-08-10 11:17:43

8150

发布于 2021-08-10 11:17:43

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

上一篇笔记：随机过程（E）——习题课（马尔科夫链-更新过程）

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

大家好！

这是《随机过程》系列习题课的第二部分。这一部分我们会介绍从连续时间马尔科夫链到布朗运动的一些习题。这一部分的难度相对大一些，当然了，我们提供的习题也会稍微少一些。

那么我们开始吧。

连续时间马尔科夫链

Problem 13: 一个商人在

A, B,C

三个地方出差，假设从一个地方到另一个地方服从一个指数分布，并且可以画出这样的转移速率矩阵

\begin{bmatrix}-4 & 2 & 2 \\ 3 & -4 & 1 \\ 5 & 0 & -5\end{bmatrix}

，单位是年，且状态沿

[A, B, C]

方向，从上到下，从左到右。问 (1) 长期来看，计算它停留在不同地方的时间占比。 (2) 长期来看，平均它一年会经历多少次

B \to A

出差？

这是一个标准的连续时间马尔科夫链的计算题，对应第9节（随机过程（9）——连续时间马尔科夫链的泊松过程描述，爆炸现象，离散马尔科夫链对比）的内容。我们在这里只需要计算平稳分布，可以得到

\pi_A = \frac 12, \pi_B = \pi_C = \frac 14

，这就是它呆在

A, B,C

的时间占比。

对于第二个题，根据正文，要把连续时间马尔科夫链理解成泊松过程的状态转移，

B \to A

，

B \to C

和

B \to B

都是会发生的。注意到

B \to B

的时间是

\frac 14

（根据Description 3，这里看的就是

对应那一行对角线元素的绝对值，也就是

）。而极限状态下的

的所居住的时间占比也碰巧是

\frac 14

，所以相当于说，平均下来一年从

出发的旅行次数就是

\frac 14 / \frac 14 = 1

。那么又因为

B \to A

的概率是

\frac 34

（对应的是矩阵中的第2行第1列），所以次数就是

\frac 34

，这个就是第二题的答案。

第二个题的题型并没有在正文出现过，所以一开始可能摸不着头脑。可以多花一些时间自行体会一下解题思路。

Problem 14: 考虑一个卖电脑的问题，假设顾客到来服从一个速率为

的泊松过程，只要电脑店有电脑，到来的顾客就会购买一台。一开始的时候电脑店里有3台电脑，只要电脑店只剩一台电脑了，就会订购2台，但是到达的时间服从

\exp(1)

。问 (1) 对电脑数量进行建模，并且计算出平稳分布。 (2) 电脑店卖出电脑的平均速度是？

这一个题目建模不是特别容易，首先从

到

的变化是容易的，相当于购买了两台电脑，那么因为需要等待，所以这个过程就是一个泊松过程，因此速率为

。但是不容易想到的是，从

到

的变化其实依然是一个速率为

的过程，考虑的依然是指数分布的无记忆性。其它的都不难想了，所以最终可以写出转移速率矩阵

Q = \begin{bmatrix}-1 & 0 & 1 & 0 \\ 2 & -3 & 0 & 1 \\ 0 & 2 & -2 & 0 \\ 0 & 0 & 2 & -2\end{bmatrix}

求解

\pi Q = 0

就可以得到最终的平稳分布

\pi = (\frac 2 5, \frac 1 5, \frac 3 {10}, \frac 1 {10})

。

对于第二个题，注意到，事实上卖出电脑的期望速率就是

（就是指数分布的期望），那么又因为概率为

\pi_1 + \pi_2 + \pi_3 = \frac 3 5

，所以最终的答案就是

\frac 6 5

。

Problem 15: 假设有3只青蛙在湖边游玩，如果它们在岸上，则每一只青蛙都会以速率为

的指数分布的概率跳到湖中。反过来，如果它们在湖中，则会以速率为

的指数分布的概率再跳回岸上，设

X_t

为时间

时的岸上的青蛙个数，问 (1) 刻画出

X_t

对应的转移速率矩阵和平稳分布。 (2) 如果考虑建模成三条独立的两状态马尔可夫链，应该如何求解？

有了前面两个题作为基础，这个题目应该就不难了。但是有一个细节是，如果有多只青蛙在岸上，那么先跳下去需要等待的时间，就是这些青蛙等待时间中的最小值，对应指数分布就是将参数相加（可以看第9节与排队论相关的例子，比如Problem 2）。所以我们有

Q = \begin{bmatrix}-6 & 6 & 0 & 0 \\ 1 & -5 & 4 & 0 \\ 0 & 2 & -4 & 2 \\ 0 & 0 & 3 & -3\end{bmatrix}

其中状态

[0, 1, 2, 3]

从上到下，从左到右排列。懂了上面那句话，就明白为什么

Q(0, 1) = 6

而不是

了。

这个平稳分布求解不是很困难，因为它是满足细致平衡条件的。因此计算的时候可以构造一连串的式子方便求解。具体来说就是设

\pi_0

是一个未知数，然后我们有

\pi_0 Q(0, 1) = \pi_1 Q(1, 0)

可以解出

\pi_1 = 6 \pi_0

。剩下的类似，可以得到最终的平稳分布

\pi = (\frac 1 {27}, \frac 6 {27}, \frac {12}{27}, \frac 8 {27})

对于第二问，其实就是解决这个问题的另一个视角。如果我们只考虑一只青蛙，那么很容易得到转移速率矩阵为

Q = \begin{bmatrix}-1 & 1 \\ 2 & -2\end{bmatrix}

其中状态

[0, 1]

从左到右，从上到下排序，并且

表示在岸上，

表示在湖中，那么可以求解出

\pi_0 = \frac 23 , \pi_1 = \frac 13

，这就对应上了每一只青蛙在湖中和在岸上的概率，相关的概念也可以在第9节，与离散马尔科夫链的对比中找到。

既然如此，因为三只青蛙的决策相互独立，所以相当于构造出了一个二项分布

Bi(3, \frac 2 3)

，所以这样的话，在岸上的概率就变成了单纯的一个概率论计算题。比如说如果要求

P(X_t = 0)

，那么结果就是

\binom{3}{0} (\frac 13)^3 = \frac 1 {27}

。剩下的几个结果也是类似的计算，这里就不多说了。

Problem 16: 考虑Problem 13的背景，也即他出差的转移速率矩阵为

\begin{bmatrix}-4 & 2 & 2 \\ 3 & -4 & 1 \\ 5 & 0 & -5\end{bmatrix}

，并且状态为

[A, B, C]

从上到下，从左到右排列。假设他刚刚从

离开，问 (1) 它平均会花多长时间会再回到

？ (2) 通过计算平稳分布来求解(1)。

这一个题是一个连续时间马尔科夫链中，离出分布和到达时间的问题，对应的是笔记的第A节（随机过程（A）——连续时间马尔科夫链的离出分布，到达时间。排队论模型与排队网络举例）。在这里，到达时间对应的就是离散马尔科夫链中的离出时间。

我们设

g(i) = E_i(V_A)

，那么我们可以列出这样的方程

\begin{cases}g(A) = 0 \\ g(B) = \frac 14 + \frac 34 g(A) + \frac 14 g(C) \\ g(C) = \frac 15 + g(A)\end{cases}

这里的

\frac 14, \frac 15

是怎么确定的，如果不熟悉的话就需要回头看一下笔记了。解方程组可以得到

g(B) = \frac 3 {10} , g(C) = \frac 15

。

有了这个之后，我们再用一次“一步转移”，注意到从

出发，到达

B, C

的概率各是

\frac 12

，所以有

\frac 12 E_B(V_A) + \frac 12 E_C(V_A) = \frac 14

当然了，我们可以利用平稳分布来求解，是因为我们在这里也介绍过一个思路，就是利用更新奖赏过程的结论，可以得到

E_A(T_A) = \frac {1 / \lambda_A}{\pi_A}

这里的

\lambda_A = 4

表示的是离开的速率（把它理解为一个泊松过程）。并且通过求解平稳分布可以知道

\pi_A = \frac 2 4

，所以最终我们可以得到

E_A(T_A) = \frac 1 2

。

到这里其实还没完，注意到，这个题目中，他是刚刚离开

的，而这个结果其实是包含了一段他停留在

的时间的。因此可以得到最终的答案是

E_A(T_A) - E(t_A) = \frac 14

所以这一个题其实并不是简单的一个求解

E_i(V_A)

的到达时间问题。还是需要一些额外的分析过程的。

Problem 17: 考虑一个打字员的问题。假如说经济系和社科系均有一个打字员，并且他们一天都可以打

封信件。已知经济系一天平均需要

封，而社科系需要

封，所以有可能出现系里需要的信件还没有被打完的可能，这个时候会有排队的现象。假设打信件的速度服从指数分布，问 (1) 每个部门的平均的队伍长度，等待排队的时间和在系统的时间。 (2) 如果两个打字员形成一个单独的部门为这两个系服务，问平均的等待排队的时间。

这一个题是一个典型的排队论的问题。虽然排队论的例子我们正文举了很多，但是它难也确实是真的难……我们看一下怎么建模这个问题。

对于第一题，对于经济系研究，那么就是一个典型的

M/M/1

模型。这个模型的转移概率我们也可以写出来为

q(i, i + 1) = 20, i = 0, 1, ,2 ,\cdots

q(i, i - 1) = 25, i = 1, 2, 3, \cdots

这个结论可以参考第9节的Problem 1的内容，也可以参考第8节（随机过程（8）——更新过程在排队论的两个应用，PASTA，连续时间马尔科夫链引入）的Problem 3，它们俩是一个题。

那么这样的话，注意到这个转移速率是满足细致平衡条件的（想想为什么？）那么自然的，我们会有

\pi(i) = \frac 15 (\frac 45)^i, \pi(0) = \frac 15

。这样的话，就会有

W_Q = E(T_Q) = \frac 4 {25}

W = W_Q + E(s_i) = \frac 15

L = \lambda W = 20 \times \frac 15 = 4

这里的

W_Q

是在队列的等待时间，

是在系统的等待时间（这里的区别怎么理解，去看一下排队论部分的第8节）。

是队伍的平均长度。

类似的，对于社科系，我们也可以得到平均等待时间为

\frac 1 {10}

，而等待的队列长度为

\frac 3 2

。

对于第二题，如果把打字员合并在一起，那么相当于变成了一个

M/M/2

问题。这个时候，情况要稍微复杂一点。对应的转移速率矩阵就会变为

q(i, i + 1) = 15 + 20 = 35, i = 0, 1, 2, \ldots

q(1, 0) = 25, q (i, i - 1) = 50, i = 2, 3, 4, \ldots

那么这样的话，求解平稳分布就有

\pi(0) = \frac 3 {17}, \pi(1) = \frac {21}{85}, \pi(i) = \frac {21}{85}(\frac 7 {10})^{i - 1}, i \ge 2

。

这个时候，对应的队伍长度为

L = E(X) = \sum_{n = 0}^\infty n P(X = n) = \frac{ 140}{51}

并且可以得到相对应的平均等待时间

W = \frac L \lambda = \frac 4 {51}

。

这一问，我们相当于用了另外一种更加直接的方式来计算

，并且反推

。

排队网络

这里我们补了两个排队网络的问题。虽然我们没有在正文中对排队网络展开来说，但是排队网络的题目的套路和建模都算比较好理解的，所以我们还是补了两个题目，给大家拓宽一些视野。

Problem 18: 考虑一个排队网络的问题，假如说用户到达

1, 2, 3

站台的速率为

3, 2, 1

，站台

1, 2, 3

服务的速率为

4, 5, 6

。用户在某站台服务结束之后，有可能会前往其他站台，对应的转移概率为

p(1, 2) = \frac 13, p(1, 3) = \frac 13 , p (2,3 ) = \frac 2 3

，其它为0。求解这个排队网络的平稳分布。

这里的站台其实就和理发店中的理发师，或者一般排队论模型中的“服务器”是一个意思。这里

p(1, 2) = \frac 13

就是从

到

的概率是

\frac 13

，剩下的

\frac 23

的概率

因为排队网络的正文没有展开，这里我们也会说的简略一点。注意到首先，要求解出一个长期的，不同站台的客户到达速率

r_i

。这样的话，因为系统稳定的时候，进站台和出站台对应的速率是相同的。所以可以通过解方程，得到

\begin{cases}r_1 = 3 \\ r_2 = 2 + \frac 13 r_1 \\ r_3 = 1 + \frac 23 r_2 + \frac 1 3 r_1\end{cases}

解方程可以得到

r_1 =r _2 = 3, r_3 = 4

。注意到

r_i < s_i

（

s_i

是每一个站台的服务速率），所以平稳分布是存在的。所以可以得到平稳分布

\pi(n_1, n_2, n_3) = (\frac 34)^{n_1} (1 - \frac 34) (\frac 35 )^{n_2}(1- \frac 35)(\frac 4 6)^{n_3}(1 - \frac 46)

= \frac 1{30} (\frac 34 )^{n_1} (\frac 35)^{n_2}(\frac 23)^{n_3}

最后的平稳分布，虽然我们没有讲一般情况下的公式，但对比第A节最后排队网络中，两站网络的介绍，相信你也可以对应的看出这里的计算公式究竟是怎么来的。

Problem 19: 考虑一个菜市场卖菜的问题。已知店铺

1, 2, 3

的顾客到达速率分别为

10, 8, 6

。每一个菜市场服务的速率足够大，保证整个排队网络存在平稳分布。其中顾客离开某一个店铺之后，可能会前往其它的店铺，对应的转移概率为

p(1, 2) = \frac 12

，

p(3, 2) = \frac 3 {10}

，

p(2, 1) = p(2, 3) = \frac 3{10}

。求解这三个店铺的服务总速率为多少？

这个答案其实是显而易见的，因为顾客到达和离开的速率必须是一致的，所以服务速率自然联想到应该是

10 + 8 + 6 = 24

。这里我们使用正规的排队网络的求解思路，把这个问题再重新考虑一下，不过也不难。

先求解极限状态下的进入和离开速率

r_i

，我们有

\begin{cases}r_1 = 10 + \frac 3{10} r_2 \\ r_2 = 8 + \frac 12 r_1 + \frac 3 {10} r_3 \\ r_3 = 6 + \frac 3 {10} r_2\end{cases}

求解方程组可以得到

r_1 = \frac{301}{19}, r_2 = \frac{370}{19}, r_3 = \frac{225}{19}

。那么这样的话，结合每一个顾客离开的概率，就可以得到最终的速率

\frac 12 r_1 + \frac 4 {10} r_2 + \frac 7 {10} r_3 = 24

鞅

Problem 20: 考虑一个乘积鞅的问题。

X_i = e^{\eta _i}

，其中

\eta_i \sim N(\mu, \sigma^2)

，问

\mu, \sigma^2

满足什么样的条件，可以使得

M_n = M_0 \cdot X_1\cdots X_n

是一个鞅。

这个问题就是一个概念题。注意到第B节（随机过程（B）——鞅的引入，性质与举例。可选停时定理）的乘积鞅的部分，我们提过说，必须要求

E(X_i) = 1

才可以。但是注意到，因为我们有

\log (X_i) = \eta_i

，所以对应可以知道，

X_i \sim \operatorname{Lognormal(\mu, \sigma^2)}

，所以有

E(X_i) = e^{\mu + \frac 12 \sigma^2}

（这也是概率论里的知识了）。所以条件就是

\mu + \frac 12 \sigma^2 = 0

。

Problem 21: 考虑一个“不公平的公平游戏”。设

Y_0 = 1

，并且对

n \ge 1

，

Y_n \sim U(0, Y_{n - 1})

。也就是说，如果设

U_1, U_2, \ldots \sim U(0, 1)

，那么有

Y_n = U_n U_{n - 1} \cdots U_0

。 (1) 证明

M_n = 2^n Y_n

是一个鞅。 (2) 证明

\frac {\log(Y_n)} n \to -1

（这里的

\log

就是

\ln

）。 (3) 利用(2)，证明

M_n \to 0

。

这里实际上还是乘积鞅的一个题目，我们仔细看看。设

A_v = \{M_0 = m_0, X_0 = x_0, \cdots, X_n = x_n\}

，那么我们有

E(M_{n + 1}|A_v) = 2M_nE(U_{n + 1} |A_v) = 2 M_n E(U_{n + 1}) = M_n

这是因为

E(U_n) = \frac 12, \forall n

。所以第一个题很好证明了。

对于第二个题，其实也是个概率论的大数定律的题目。注意到

\frac {\log (Y_n)} n = \frac 1n \sum_{i = 1}^n \log U_i \to E(\log (U_1)) = -1

这就足够得到结论了。如果

E(\log(U_1))

不会计算的话，说明微积分需要加强hh。

最后一个问题的话，注意到

M_n = 2^n Y_n = e^{\log (2^n Y_n)} = e^{n (\log 2 + \frac 1n \log (Y_n))}

注意到

\frac {\log(Y_n)} n \to -1

，而

\log 2 - 1 < 0

，所以自然的就有最终的结论成立了。

这一个问题很有意思的地方在于，如果我们认为

M_n

是财产的话，那么虽然

M_n

是一个鞅，但是最终的趋势却告诉我们

M_n \to 0

，相当于“游戏的规则公平，却一定会破产”，因此我们叫它“不公平的公平游戏”，也不是没有道理。

另外，关于可选停时定理的问题，我们在正文中其实已经做了很多举例，这里就不多提了。

布朗运动

Problem 22: 考虑一个投资问题。设资本服从一个带偏移的布朗运动，即

X_t = x + \mu t + \sigma B_t

，且

\mu > 0, x > 0

。设

\tau = \inf \{t: X_t \le 0\}

，计算

P(\tau < \infty)

。

这一个问题是一个布朗运动相关的问题，也是一个非常接近金融数学的题目了。我们用这一个问题来结束我们的习题课。

我们在正文的第C节（随机过程（C）——可选停时定理的应用，鞅的不等式与收敛性证明）介绍可选停时定理的应用的时候，其实也有类似的估计这种有限概率的问题。在这里，我们可以利用类似的证明方法，先找到一个鞅，再使用可选停时定理来求解。

这里比较常见的构造是指数鞅，因为指数鞅成立的条件是比较容易达成的。注意到对

\forall s \le t

，我们有

E(e^{\alpha X_t}|X_r, 0 \le r \le s) = e^{\alpha X_s} E(e^{\alpha (X_t - X_s)} |X_r , 0 \le r \le s)

=e^{\alpha X_s} E (e^{\alpha (X_t - X_s)}) = e^{\alpha X_s}e^{\alpha \mu (t - s)} E(e^{\alpha \sigma (B_t - B_s)})

=e^{\alpha X_s} e^{(\alpha \mu + \frac {\alpha^2 \sigma^2}2)(t -s)}

这里的

X_t

也是一个布朗运动，读者可以自己验证。一个好的理解是，这个“偏移“并没有带入任何“随机变量”相关的信息，自然也就不会影响独立性。

如果要求指数鞅，只需要我们的系数

\alpha \mu + \frac {\alpha^2 \sigma^2} 2 = 0

。所以可以得到

\alpha = - \frac {2\mu} {\sigma^2}

，那么根据可选停时定理，可以得到

E(e^{\alpha X_{\tau \land n}}) = E(e^{\alpha X_0}) = e^{\alpha x}

但另一方面，拆分

\tau

的范围，我们可以有

e^{-\frac {2 \mu} {\sigma^2} x } = E(e^{\alpha X_\tau} I(\tau \le n) + e^{\alpha X_n} I(\tau >n))

注意到在

\tau \le n

的时候，有

X_\tau = 0

（想想为什么？），所以有

\lim_{n \to \infty} E(e^{\alpha X_\tau} I(\tau \le n)) = \lim_{n \to \infty} P(\tau \le n) = P(\tau < \infty)

这一部分解答完之后，对于另外一个部分，注意到

X_t \to \infty

（这是因为

B_t

相比较一次项

来说，可以忽略不计，具体可以参考第D节正文中的Proposition 10），那么自然的会有

\lim_{n \to \infty} e^{\alpha X_n} I(\tau > n) = 0

，且

\tau > n

的时候，有

X_n > 0, 0 \le e^{\alpha X_n I(\tau > n)} \le 1

。所以根据控制收敛定理（见《实分析》的相关内容（https://zhuanlan.zhihu.com/p/36921064）），我们有

\lim_{n \to \infty} E(e^{\alpha X_n} I(\tau >n)) = E(\lim_{n \to \infty} e^{\alpha X_n} I(\tau > n)) = 0

这就得到了最终的结论

P(\tau < \infty) = e^{-\frac {2\mu}{\sigma^2} x}

。

好的，到此为止，《随机过程》的这一系列，就正式告一段落了。

学弱猹的精品小屋

知乎学弱猹，厦门大学计算数学系16级本科，教育部“拔尖计划”成员，从事互联网数据算法相关工作。乐于数学，编程类知识分享，阅读量300w+

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

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

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

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

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

登录后参与评论

0 条评论

热度