[markov系列1]從馬爾可夫鏈看矩陣的乘法

在高中階段，矩陣和矩陣乘法的教學往往不被重視. 在絕大多數高中生眼裡，把一些數字排列成行列然後用圓括弧括起來就是矩陣，把矩陣靜態的理解為一種存儲數字的方式，而把矩陣的運算看作是一種數字運算的批處理，對矩陣乘法僅僅停留在規則記憶的層面上，其應用情境也大多侷限在表示線性方程組或諸如小明、小紅、小王買鉛筆、鋼筆、圓珠筆的問題上. 那麼今天橘子老君將從一道老鼠版Maze Runer的趣味問題入手，帶你看一看矩陣的真正實力.

問題

如下圖所示的迷宮共有9個格子，相鄰格子有門相通，9號格子就是迷宮出口. 整個迷宮將會在5分鐘後坍塌. 1號格子有一隻老鼠，這隻老鼠以每分鐘一格的速度在迷宮裡亂竄（它通過各扇門的機會均等）。求此老鼠在迷宮坍塌之前逃生的概率。如果這隻老鼠速度提高一倍，則老鼠在迷宮坍塌之前逃生的概率能增加多少？

以上是2018年上海應用數學知識競賽的一道初賽試題，橘子老君將會講解如何用矩陣乘法來解決這個問題.

簡化版問題

首先，我們不妨先把問題簡化為一個4個格子的迷宮，老鼠仍以每分鐘一格的速度在迷宮裡亂竄，4號格子是迷宮的出口.

由通過各扇門的機會均等，可得格子之間轉移的概率如圖（由於4號格子是出口，所以老鼠到達四號格子後不會向其他格子轉移），

那麼，老鼠經過一次移動，1分鐘後在1-4號的格子的概率分別為、、、 .

我們不妨用向量表示分鐘後老鼠在1-4號的格子的概率，故 .

如上圖，通過列舉每一條路徑，當老鼠經過兩次移動，我們發現老鼠可能落在1號或4號格子.

考慮落在1號格子的情況，其對應有兩條路徑，和 .

那麼根據老鼠每次的移動相互獨立和加法原理，我們得到老鼠落在1號格子的概率為 .

同理可得落在4號格子的概率也為，故 .

如上圖，進一步列舉3分鐘後的每一條路徑，考慮落在3號的格子的情況，對應的路徑有兩條和 . 通過分析格子間的轉移概率不難得到，要使老鼠3分鐘後落在3號格子，則2分鐘後老鼠必須在1號格子. 故我們接下來將嘗試寫出相鄰兩分鐘在不同格子概率的遞推關係.

一般地，不妨用 $v_n^{(i)}$ 表示分鐘老鼠落在號格子的概率，則有

由以上遞推關係，我們可以通過編程由計算機來完成計算：

#!/usr/bin/env python3

n = 5 # 計算到n分鐘後的情況
v = (1, 0, 0, 0) # 0分鐘後的情況
i = 0 # 當前計算到i分鐘後
while i < n:
v = (
0.5 * v[1] + 0.5 * v[2],
0.5 * v[0],
0.5 * v[0],
0.5 * v[1] + 0.5 * v[2] + v[3]
)
i = i + 1
print(v + str(i) + : + str(v))

Output:

v1: (0.0, 0.5, 0.5, 0.0) v2: (0.5, 0.0, 0.0, 0.5) v3: (0.0, 0.25, 0.25, 0.5) v4: (0.25, 0.0, 0.0, 0.75) v5: (0.0, 0.125, 0.125, 0.75)

由上述結果，我們看到，老鼠在五分鐘後逃出的概率為 . 如果老鼠的移動速度翻倍那無非就是移動的次數從5次變為10次，得到逃出的概率為 .

更一般地，我們可以用 $a_{ij}$ 表示老鼠從號格子向號格子移動的概率，那麼

即

故由矩陣乘法的定義，遞推關係式可以寫成：

馬爾可夫鏈：一些定義

至此我們得到了解決此問題的矩陣形式,我們把此類在不同狀態間隨機移動的數學模型稱為馬爾可夫鏈. 老鼠在隨機移動的過程中可能落在4個格子內，即存在4個狀態. 而每做一次移動，其狀態即發生轉移. 為了討論更一般的情況，我們不妨設有種狀態.

我們把經過次轉移後處於各個狀態的概率所組成的向量 $mathrm{x}_n$ 稱為狀態向量. $mathrm{x}_0$ 稱為初始狀態向量，即

其中表示經過次轉移後處於狀態的概率.

我們把各個狀態之間轉移的概率所組成的方陣，稱為轉移矩陣. 即

其中 $p_{ij}$ 是從狀態轉移到狀態的概率[^1].

[^1]: 注意這裡第行第列的元素是從狀態轉移到狀態的概率.

那麼同上文中的推導，我們可以得到相鄰兩個狀態向量的關係，

根據矩陣乘法的性質，不難推得 $mathrm{x_{n}}=P^n mathrm{x_0}$ .

簡化版問題的矩陣解法

在上文簡化版問題中，

故

下面我們用計算機來完成矩陣乘法計算：

#!/usr/bin/env python3

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

Output:

x1: [[0. ] [0.5] [0.5] [0. ]] x2: [[0.5] [0. ] [0. ] [0.5]] x3: [[0. ] [0.25] [0.25] [0.5 ]] x4: [[0.25] [0. ] [0. ] [0.75]] x5: [[0. ] [0.125] [0.125] [0.75 ]]