線性代數/主題：馬爾可夫鏈

線性代數
← 主題：線性對映的幾何	主題：馬爾可夫鏈	主題：正交矩陣 →

這是一個簡單的遊戲：玩家每次擲硬幣下注一美元，遊戲結束的條件是玩家要麼輸光了錢，要麼賺到了五美元。如果玩家一開始有3美元，遊戲至少進行五次的機率是多少？二十五次呢？

在任何時刻，玩家要麼有0美元，要麼有1美元，……，要麼有5美元。我們稱玩家處於狀態 $s_{0}$ ， $s_{1}$ ，……，或者 $s_{5}$ 。遊戲就是從一個狀態移動到另一個狀態。例如，現在處於狀態 $s_{3}$ 的玩家，在下一次擲硬幣時有 $0.5$ 的機率移動到狀態 $s_{2}$ ，以及 $0.5$ 的機率移動到 $s_{4}$ 。邊界狀態略有不同；一旦處於狀態 $s_{0}$ 或者狀態 $s_{5}$ ，玩家就永遠不會離開。

令 $p_{i}(n)$ 表示玩家在第 $n$ 次擲硬幣後處於狀態 $s_{i}$ 的機率。那麼，例如，我們有玩家在第 $n+1$ 次擲硬幣後處於狀態 $s_{0}$ 的機率為 $p_{0}(n+1)=p_{0}(n)+0.5\cdot p_{1}(n)$ 。這個矩陣方程總結了這一點。

{\begin{pmatrix}1&0.5&0&0&0&0\\0.5&0&0.5&0&0&0\\0&0.5&0&0.5&0&0\\0&0&0.5&0&0.5&0\\0&0&0&0.5&0&0.5\\0&0&0&0&0.5&1\end{pmatrix}}{\begin{pmatrix}p_{0}(n)\\p_{1}(n)\\p_{2}(n)\\p_{3}(n)\\p_{4}(n)\\p_{5}(n)\end{pmatrix}}={\begin{pmatrix}p_{0}(n+1)\\p_{1}(n+1)\\p_{2}(n+1)\\p_{3}(n+1)\\p_{4}(n+1)\\p_{5}(n+1)\end{pmatrix}}

在玩家初始擁有三美元的條件下，計算結果如下。

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$\cdots$	$n=24$
${\begin{pmatrix}0\\0\\0\\1\\0\\0\end{pmatrix}}$	${\begin{pmatrix}0\\0\\0.5\\0\\0.5\\0\end{pmatrix}}$	${\begin{pmatrix}0\\0.25\\0\\0.5\\0\\0.25\end{pmatrix}}$	${\begin{pmatrix}0.125\\0\\0.375\\0\\0.25\\0.25\end{pmatrix}}$	${\begin{pmatrix}0.125\\0.1875\\0\\0.3125\\0\\0.375\end{pmatrix}}$	$\cdots$	${\begin{pmatrix}0.39600\\0.00276\\0\\0.00447\\0\\0.59676\end{pmatrix}}$

正如這個計算探索所表明的，這個遊戲不太可能持續很久，玩家很快就會結束在 $s_{0}$ 狀態或 $s_{5}$ 狀態。例如，在第四次翻轉後，遊戲已經結束的機率為 $0.50$ 。 (因為進入任何一個邊界狀態的玩家都不會離開，所以它們被稱為吸收態。)

這個遊戲是馬爾可夫鏈的一個例子，以 20 世紀上半葉工作的 A.A. 馬爾可夫命名。每個 $p$ 向量都是機率向量，矩陣是轉移矩陣。馬爾可夫鏈模型的顯著特徵是無記憶性，即在固定轉移矩陣的情況下，下一個狀態只取決於當前狀態，而不依賴於任何先前的狀態。因此，例如，一個從 $s_{3}$ 狀態開始，先進入 $s_{2}$ 狀態，然後進入 $s_{1}$ 狀態，然後又進入 $s_{2}$ 狀態的玩家，此時進入 $s_{3}$ 狀態的機率，與一個從 $s_{3}$ 狀態開始，先進入 $s_{4}$ 狀態，然後進入 $s_{3}$ 狀態，然後進入 $s_{2}$ 狀態的玩家完全一樣。

以下來自社會學的馬爾可夫鏈。一項研究 (Macdonald & Ridge 1988，第 202 頁) 將英國的職業劃分為上層 (高管和專業人士)、中層 (主管和熟練體力勞動者) 和下層 (非熟練勞動者)。為了確定世代之間的流動性，大約兩千名男性被問到，“你目前處於哪個層級？當你 14 歲時，你父親處於哪個層級？”這個等式總結了結果。

{\begin{pmatrix}0.60&0.29&0.16\\0.26&0.37&0.27\\0.14&0.34&0.57\end{pmatrix}}{\begin{pmatrix}p_{U}(n)\\p_{M}(n)\\p_{L}(n)\end{pmatrix}}={\begin{pmatrix}p_{U}(n+1)\\p_{M}(n+1)\\p_{L}(n+1)\end{pmatrix}}

例如，一個下層工人階級孩子的長大後成為中產階級的機率為 $.27$ 。需要注意的是，馬爾可夫模型關於歷史的假設似乎是合理的——我們預計，雖然父母的職業會直接影響孩子的職業，但祖父母的職業不會有這種直接影響。在給定受訪者父親的初始分佈的情況下，該表列出了接下來五代的分佈。

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$
${\begin{pmatrix}0.12\\0.32\\0.56\end{pmatrix}}$	${\begin{pmatrix}0.23\\0.34\\0.42\end{pmatrix}}$	${\begin{pmatrix}0.29\\0.34\\0.37\end{pmatrix}}$	${\begin{pmatrix}0.31\\0.34\\0.35\end{pmatrix}}$	${\begin{pmatrix}0.32\\0.33\\0.34\end{pmatrix}}$	${\begin{pmatrix}0.33\\0.33\\0.34\end{pmatrix}}$

再來一個例子，來自一個非常重要的主題。美國棒球的世界大賽由贏得美國聯盟的球隊和贏得國家聯盟的球隊之間進行（我們遵循 [Brunner]，但也可以參見 [Woodside]）。第一支贏得四場比賽的球隊贏得系列賽。這意味著一個系列賽處於 24 個狀態之一：0-0（兩隊都還沒有贏球）、1-0（美國聯盟隊贏了一場，國家聯盟隊沒有贏球）等等。如果我們假設美國聯盟隊贏得每一場比賽的機率為 $p$ ，那麼我們有以下轉移矩陣。

{\begin{pmatrix}0&0&0&0&\ldots \\p&0&0&0&\ldots \\1-p&0&0&0&\ldots \\0&p&0&0&\ldots \\0&1-p&p&0&\ldots \\0&0&1-p&0&\ldots \\\vdots &\vdots &\vdots &\vdots \end{pmatrix}}{\begin{pmatrix}p_{\text{0-0}}(n)\\p_{\text{1-0}}(n)\\p_{\text{0-1}}(n)\\p_{\text{2-0}}(n)\\p_{\text{1-1}}(n)\\p_{\text{0-2}}(n)\\\vdots \end{pmatrix}}={\begin{pmatrix}p_{\text{0-0}}(n+1)\\p_{\text{1-0}}(n+1)\\p_{\text{0-1}}(n+1)\\p_{\text{2-0}}(n+1)\\p_{\text{1-1}}(n+1)\\p_{\text{0-2}}(n+1)\\\vdots \end{pmatrix}}

一個特別有趣的特例是 $p=0.50$ ; 該表列出了 $n=0$ 到 $n=7$ 向量的結果成分。（在計算機代數系統 Octave 中生成此表的程式碼位於練習之後。）

	$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$	$n=6$	$n=7$
0-0	1	0	0	0	0	0	0	0
1-0	0	0.5	0	0	0	0	0	0
0-1	0	0.5	0	0	0	0	0	0
2-0	0	0	0.25	0	0	0	0	0
1-1	0	0	0.5	0	0	0	0	0
0-2	0	0	0.25	0	0	0	0	0
3-0	0	0	0	0.125	0	0	0	0
2-1	0	0	0	0.325	0	0	0	0
1-2	0	0	0	0.325	0	0	0	0
0-3	0	0	0	0.125	0	0	0	0
4-0	0	0	0	0	0.0625	0.0625	0.0625	0.0625
3-1	0	0	0	0	0.25	0	0	0
2-2	0	0	0	0	0.375	0	0	0
1-3	0	0	0	0	0.25	0	0	0
0-4	0	0	0	0	0.0625	0.0625	0.0625	0.0625
4-1	0	0	0	0	0	0.125	0.125	0.125
3-2	0	0	0	0	0	0.3125	0	0
2-3	0	0	0	0	0	0.3125	0	0
1-4	0	0	0	0	0	0.125	0.125	0.125
4-2	0	0	0	0	0	0	0.15625	0.15625
3-3	0	0	0	0	0	0	0.3125	0
2-4	0	0	0	0	0	0	0.15625	0.15625
4-3	0	0	0	0	0	0	0	0.15625
3-4	0	0	0	0	0	0	0	0.15625

請注意，勢均力敵的球隊很可能會有很長的系列賽——系列賽至少進行六場比賽的機率為 $0.625$ 。

包含本主題的一個原因是馬爾可夫鏈是矩陣運算最廣泛的應用之一。另一個原因是它提供了一個矩陣使用的例子，在這個例子中，我們不考慮矩陣所代表的對映的意義。有關馬爾可夫鏈的更多資訊，可以參考許多資料，例如 (Kemeny & Snell 1960) 和 (Iosifescu 1980).

練習

使用計算機解決這些問題。例如，您可以修改下面給出的 Octave 指令碼。

問題 1

這些問題指的是拋硬幣遊戲。

檢查第一段末尾表格中的計算結果。
考慮向量表中的第二行。注意這一行有交替出現的 $0$ 's。當 $j$ 為奇數時， $p_{1}(j)$ 一定是 $0$ 嗎？證明它必須是，或者提供一個反例。
進行一個計算實驗，以估計玩家從一美元、兩美元和四美元開始，最終達到五美元的機率。

問題 2

我們考慮擲骰子，並說系統處於狀態 $s_{i}$ ，如果骰子上出現的最大數字是 $i$ 。

給出轉移矩陣。
從狀態 $s_{1}$ 開始系統，並執行五次投擲。最後得到的向量是什麼？

(Feller 1968, p. 424)

問題 3

人們一直很關注美國工業是否正在從東北部和中北部地區轉移到南部和西部，其動機是較溫暖的氣候、較低的工資和較少的工會化。以下是電力和電子裝置大型企業的轉移矩陣 (Kelton 1983, p. 43)

	NE	NC	S	W	Z
NE	0.787	0	0	0.111	0.102
NC	0	0.966	0.034	0	0
S	0	0.063	0.937	0	0
W	0	0	0.074	0.612	0.314
Z	0.021	0.009	0.005	0.010	0.954

例如，東北地區的一家公司明年有 $0.111$ 的機率位於西部地區。（Z 條目是“生死”狀態。例如，有 $0.102$ 的機率，東北部一家大型電力和電子裝置公司將在明年離開該系統：倒閉、搬遷到國外或轉為其他型別的公司。有 $0.021$ 的機率，一家處於國家制造商普查的公司將進入電子行業、新建立或從國外搬遷到東北部。最後，根據這項研究，有 $0.954$ 的機率，其他類別的公司將保持不變。

馬爾可夫模型假設缺乏歷史似乎合理嗎？
假設初始分佈是均勻的，除了在 $Z$ 處的值為 $0.9$ 。計算 $n=1$ 到 $n=4$ 的向量。
假設初始分佈是這個。

NE NC S W Z
0.0000 0.6522 0.3478 0.0000 0.0000

計算 $n=1$ 到 $n=4$ 的分佈。
找到 $n=50$ 和 $n=51$ 的分佈。系統是否已穩定到均衡狀態？

問題 4

該模型已建議用於某些型別的學習（Wickens 1982，第 41 頁）。學習者從一個不確定的狀態 $s_{U}$ 開始。最終學習者必須決定做出響應 $A$ （即，處於狀態 $s_{A}$ ）或響應 $B$ （最終進入 $s_{B}$ ）。但是，學習者不會直接從不確定狀態跳到確定 $A$ 是正確選擇（或 $B$ ）。相反，學習者會在一個“嘗試- $A$ "狀態或一個“嘗試- $B$ "狀態中花費一些時間，嘗試做出響應（這裡表示為 $t_{A}$ 和 $t_{B}$ ）。假設一旦學習者做出決定，該決定就是最終的，因此一旦 $s_{A}$ 或 $s_{B}$ 被進入，它將永遠不會離開。對於其他狀態變化，假設以機率 $p$ 在任一方向上進行轉換。

構建轉移矩陣。
取 $p=0.25$ 並將初始向量取為 $1$ 在 $s_{U}$ 。執行五步。最終到達 $s_{A}$ 的機率是多少？
對 $p=0.20$ 執行相同操作。
繪製圖表 $p$ 與最終到達 $s_{A}$ 的機率。是否有一個 $p$ 的閾值，使得學習者幾乎可以確定在不超過五步的情況下完成任務？

問題 5

某個城鎮位於某個國家（這是一個假設問題）。每年有 10% 的城鎮居民遷往該國其他地區。每年有 1% 的來自其他地區的人遷往該城鎮。假設有兩個狀態 $s_{T}$ ，住在城鎮裡，以及 $s_{C}$ ，住在其他地方。

構建轉移矩陣。
從初始分佈 $s_{T}=0.3$ 和 $s_{C}=0.7$ 開始，獲得前十年的結果。
對 $s_{T}=0.2$ 做同樣的操作。
兩種結果是否相同還是不同？

問題 6

對於世界大賽的應用，使用計算機為 $p=0.55$ 和 $p=0.6$ 生成七個向量。

即使美國聯盟球隊贏得任何一場比賽的機率僅為 $0.45$ 或 $0.40$ ，國家聯盟球隊贏得最終勝利的機率是多少？
繪製圖表 $p$ 與美國聯盟球隊贏得最終勝利的機率。是否有一個閾值——一個 $p$ ，使得實力更強的球隊幾乎可以確定獲勝？

（下面包含一些示例程式碼。）

問題 7

馬爾可夫矩陣的每個條目都是正數，並且每一列的總和為 $1$ .

檢查本主題中顯示的三個轉移矩陣是否滿足這兩個條件。任何轉移矩陣都必須滿足這兩個條件嗎？
觀察如果 $A{\vec {v}}_{0}={\vec {v}}_{1}$ 且 $A{\vec {v}}_{1}={\vec {v}}_{2}$ 則 $A^{2}$ 是從 ${\vec {v}}_{0}$ 到 ${\vec {v}}_{2}$ 的轉移矩陣。證明馬爾可夫矩陣的冪也是馬爾可夫矩陣。
透過證明兩個適當大小的馬爾可夫矩陣的乘積也是一個馬爾可夫矩陣來概括前一項。

解決方案

計算機程式碼

此指令碼 markov.m 用於計算機代數系統 Octave 用於生成世界系列結果表。（井號#將該行餘下部分標記為註釋。）

# Octave script file to compute chance of World Series outcomes.
function w = markov(p,v)
q = 1-p;
A=[0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-0
p,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-0
q,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-1_
0,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-0
0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-1
0,0,q,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-2__
0,0,0,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-0
0,0,0,q,p,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-1
0,0,0,0,q,p, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-2_
0,0,0,0,0,q, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-3
0,0,0,0,0,0, p,0,0,0,1,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 4-0
0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-1__
0,0,0,0,0,0, 0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-2
0,0,0,0,0,0, 0,0,q,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-3
0,0,0,0,0,0, 0,0,0,q,0,0, 0,0,1,0,0,0, 0,0,0,0,0,0;  # 0-4_
0,0,0,0,0,0, 0,0,0,0,0,p, 0,0,0,1,0,0, 0,0,0,0,0,0;  # 4-1
0,0,0,0,0,0, 0,0,0,0,0,q, p,0,0,0,0,0, 0,0,0,0,0,0;  # 3-2
0,0,0,0,0,0, 0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0;  # 2-3__
0,0,0,0,0,0, 0,0,0,0,0,0, 0,q,0,0,0,0, 1,0,0,0,0,0;  # 1-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,p,0, 0,1,0,0,0,0;  # 4-2
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,q,p, 0,0,0,0,0,0;  # 3-3_
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,q, 0,0,0,1,0,0;  # 2-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,p,0,1,0;  # 4-3
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,q,0,0,1]; # 3-4
w = A * v;
endfunction

然後 Octave 會話是這樣的。

> v0=[1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0]
> p=.5
> v1=markov(p,v0)
> v2=markov(p,v1)
...

翻譯到其他計算機代數系統應該很容易——所有的命令都類似於這些。

參考文獻

Feller, William (1968), An Introduction to Probability Theory and Its Applications, vol. 1 (3rd ed.), Wiley.
Iosifescu, Marius (1980), Finite Markov Processes and Their Applications, UMI Research Press.
Kelton, Christina M.L. (1983), Trends on the Relocation of U.S. Manufacturing, Wiley.
Kemeny, John G.; Snell, J. Laurie (1960), Finite Markove Chains, D.~Van Nostrand.
Macdonald, Kenneth; Ridge, John (1988), "Social Mobility", British Social Trends Since 1900, Macmillian.
Wickens, Thomas D. (1982), Models for Behavior, W.H. Freeman.

線性代數
← 主題：線性對映的幾何	主題：馬爾可夫鏈	主題：正交矩陣 →

NE	NC	S	W	Z
0.0000	0.6522	0.3478	0.0000	0.0000