[markov系列2]馬爾可夫鏈中的期望問題

在《從馬爾可夫鏈看矩陣的乘法》一文中，我們通過一道老鼠在迷宮中隨機遊走的問題介紹了馬爾可夫鏈，從而更好地理解了矩陣的乘法. 本文將帶大家解決橘子老君文末留下的第一個問題：
若迷宮不會坍塌，則老鼠平均需要經過幾分鐘才能逃出迷宮？我們首先從期望的定義出發，把問題轉化為一個無窮數列求和的問題，並用統計模擬方法驗證了結果. 而後我們給出了一個更簡潔的方法，把問題轉化為一個線性方程組求解的問題.

問題回顧

仍以4格問題為例，老鼠目前在1號格子，以每分鐘一格的速度在迷宮裡亂竄，4號格子是迷宮的出口，若迷宮不會坍塌，則老鼠平均需要經過幾分鐘才能逃出迷宮？

用 $mathrm{x}_n$ 表示經過次轉移後的狀態向量(處於各個狀態的概率所組成的向量)，之前我們得到

隨機變數及其期望

我們關注的是老鼠到達4號格子(出口)所需的平均轉移次數，故把到達4號格子所需的轉移次數看作隨機變數 [^1]，即求隨機變數的期望 [^2].

[^1]: 用數值來表達隨機試驗結果的變數. 詳見維基百科.

[^2]: 隨機變數取值的加權平均，權重為該取值的概率. 詳見維基百科.

而根據隨機變數期望的定義可得，

狀態轉移矩陣的修正

$mathrm{x}_n^{(4)}$ 表示的是經過次轉移，老鼠落在4號格子(已逃出)的概率.

但需要注意 $x_n^{(4)} eq P(X=n)$ ，因為 $x_n^{(4)}$ 累計計算了前次轉移到達4號格子的概率.

為了方便，我們不妨新增一個狀態5（已逃出），如圖落在狀態4（4號格子）及狀態5的老鼠，經過一次轉移後 $100\%$ 落在狀態5.

故狀態轉移等式修正為

此時 $x_n^{(4)}$ 表示的即經過次轉移後老鼠第一次落在4號格子的概率，即 .

無窮數列的求和

#!/usr/bin/env python3

import numpy as np
n = 15 # 計算到n次轉移後的情況
i = 0 # 當前進行到i次轉移
x = np.array([
[1],
[0],
[0],
[0],
[0]]) # 當前的狀態向量
P = np.array([
[0, 0.5, 0.5, 0, 0],
[0.5, 0, 0, 0, 0],
[0.5, 0, 0, 0, 0],
[0, 0.5, 0.5, 0, 0],
[0, 0, 0, 1, 1]
]) # 轉移矩陣
while i < n:
x = P.dot(x) # x=P*x
i = i+1
print(P(x=+str(i)+): +str(x[3])) # 輸出P(x=i)

如上修改之前的程序後，我們得到計算結果如下：

P(x=1): [0.] P(x=2): [0.5] P(x=3): [0.] P(x=4): [0.25] P(x=5): [0.] P(x=6): [0.125] P(x=7): [0.] P(x=8): [0.0625] P(x=9): [0.] P(x=10): [0.03125] P(x=11): [0.] P(x=12): [0.015625] P(x=13): [0.] P(x=14): [0.0078125] P(x=15): [0.]

通過觀察[^4]我們發現，奇數次到達4號格子的概率為，偶數次到達4號格子的概率成等比數列，故

[^4]: 事實上我們可以計算轉移矩陣的次方，即得到各元素關於的表達式. 其計算方法請參考任一本《線性代數》的教材.

沒錯就是高中數列求和的常見題型，一個等差數列一個等比數列分別相乘再相加，用錯位相減法進行求和即可.

兩式相減得，

解得

如果你學習過微積分，那麼由洛必達法則[^3]，我們可以得到

[^3]: 對於分子分母極限都為零或都為無窮大時，可以分別求導再求極限. 詳見維基百科.

如果你沒有學習過微積分，那麼也很容易理解 $limlimits_{n oinfty}dfrac{2+n}{2^{n-1}}=0$ . 雖然當時，有和都趨於，但的增長趨勢要遠大於 .

因此 $limlimits_{n oinfty}S=4$ ，即 . 即平均4次轉移後，老鼠即到達4號格子.

蒙特卡羅統計模擬法

下面我們利用蒙特卡羅統計模擬法[^5]，來檢驗我們得到的結果.

[^5]: 一種藉助計算機生成隨機數來進行多次實驗，根據結果統計來估計理論值的方法, 詳見維基百科

以下程序即進行了10萬次實驗模擬，每次實驗都是狀態1出發，進行若干次隨機轉移直到到達狀態4結束，最終通過對實驗結果記錄的統計，得到平均轉移次數.

#!/usr/bin/env python3 import numpy as np from random import choices from statistics import mean

class State(object):

def __init__(self,state_id):
self.transition_matrix = np.array([
[0, 0.5, 0.5, 0],
[0.5, 0, 0, 0],
[0.5, 0, 0, 0],
[0, 0.5, 0.5, 1],
]) # 轉移矩陣
self.state_id = state_id # 狀態ID：狀態1的ID為0

def move(self):
candidates = range(0, 4) # 轉移目標
weights = self.transition_matrix[:, self.state_id] # 轉移概率
result = choices(candidates, weights) # 產生隨機轉移結果
return State(result[0])

if __name__ == __main__:
e = 100000 # 試驗次數
r = [] # 試驗結果
for i in range(0,e):
cur_state = State(0) # 初始狀態: 狀態1
count = 0 # 轉移次數
while cur_state.state_id != 3:
cur_state = cur_state.move()
count += 1
r.append(count) # 記錄結果
print(mean(r)) # 輸出均值

所得結果如下，

4.0062

一種更簡潔、一般的解法

在這個問題中，我們要求的就是從狀態1到狀態4所需要的平均轉移次數.

那我們不妨設表示從狀態到狀態4的平均轉移次數， $p_{ij}$ 表示從狀態轉移到狀態的概率. 則有

如圖以為例，要考慮狀態1到狀態4的轉移次數期望，不妨先考慮從狀態1出發的第一次轉移. 其有0.5的概率到達狀態2，有0.5的概率到達狀態3，而從狀態2、3到達狀態4又平均需要、次轉移，故我們可以得到

這裡+1是因為從狀態1出發到達狀態2、3耗費了一次轉移.

即得到線性方程組，

不難解得， .

一般地，我們設 $E_{ji}$ 是狀態到狀態的轉移次數期望，則有

其中顯然有 $E_{jj}$ .

所得線性方程組的矩陣形式為

而一般的線性方程組的求解方法，這裡就不具體展開了，有興趣的讀者可以在任一本線性代數的教材中找到相關內容.

後記

回顧這個問題，除了之前引進的關於馬爾可夫鏈問題的一些定義，其他所涉及到知識點如隨機變數的期望、矩陣乘法（線性方程組的矩陣表示）、數列極限、數列求和（錯位相減法）等都屬於高中範疇. 橘子老君認為這個問題是在高中階段開展數學項目化學習的絕佳素材，還有什麼比綜合運用自己的所學的數學知識來解決一個兼顧趣味性與挑戰性的問題更吸引人呢?

橘子老君實在不清楚近幾年上海高考命題方向弱化矩陣、概率統計、程序框圖的意圖是什麼. 也許這塊內容相對獨立而難度要求不高，作為考試試題沒有什麼區分度. 但這就直接導致這塊內容在教學上不受到重視，我想這與上海領先全國把矩陣引入高中教材的初衷是相悖的.

新課程改革天天喊著關注核心素養，一線大批優秀的老師和學生們卻依舊孜孜不倦地從茫茫題海中汲取養分. 不過橘子老君相信，隨著技術的發展，應試的「效率」會越來越高，未來考生們在中檔題上的差距會越來越小. 只要難題夠難夠新，資質平庸的學生，通過刷題獲得優勢的性價比會越來越低. 也許靠超前學習、大量刷題能夠幫助一個資質平庸的學生在高一、高二階段陳題堆砌的校內考試中獲得明顯優勢，但這種優勢絕不會保持到高考. 只有學生、家長、老師、學校重新回歸理性，新課程改革才能得以順利推進，放下題海纔有時間和精力去關注學科核心素養的養成，去關注那些對學生影響更加長遠的東西.

而橘子老君也會繼續堅持及時把平時自己看到的有價值的東西整理出來與大家分享.

導入自橘子老君的博客.

更多適閤中學生的趣味科普文章，關注微信公眾號：橘子數學