線性代數/主題：馬爾可夫鏈/解決方案

解決方案

對於這些問題，請使用計算機。例如，您可以調整下面給出的 Octave 指令碼。

問題 1

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

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

答案

使用此檔案coin.m

   # Octave 函式，用於馬爾可夫硬幣遊戲。p 是下降的機率。    function w = coin(p,v)    q = 1-p;    A=[1,p,0,0,0,0;    0,0,p,0,0,0;    0,q,0,p,0,0;    0,0,q,0,p,0;    0,0,0,q,0,0;    0,0,0,0,q,1];    w = A * v;    endfunction
此 Octave 會話產生了此處給出的輸出。
  octave:1> v0=[0;0;0;1;0;0]    v0 =    0    0    0    1    0    0    octave:2> p=.5    p = 0.50000    octave:3> v1=coin(p,v0)    v1 =    0.00000    0.00000    0.50000    0.00000    0.50000    0.00000    octave:4> v2=coin(p,v1)    v2 =    0.00000    0.25000    0.00000    0.50000    0.00000    0.25000
這繼續進行了太多步，無法在此列出。
  octave:26> v24=coin(p,v23)    v24 =    0.39600    0.00276    0.00000    0.00447    0.00000    0.59676
使用這些公式
${\begin{aligned}{2}p_{1}(n+1)&=0.5\cdot p_{2}(n)&\qquad p_{2}(n+1)&=0.5\cdot p_{1}(n)+0.5\cdot p_{3}(n)\\p_{3}(n+1)&=0.5\cdot p_{2}(n)+0.5\cdot p_{4}(n)&\qquad p_{5}(n+1)&=0.5\cdot p_{4}(n)\end{aligned}}$
以及這些初始條件
${\begin{pmatrix}p_{0}(0)\\p_{1}(0)\\p_{2}(0)\\p_{3}(0)\\p_{4}(0)\\p_{5}(0)\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\1\\0\\0\end{pmatrix}}$
我們將透過歸納法證明，當 $n$ 為奇數時， $p_{1}(n)=p_{3}(n)=0$ ；當 $n$ 為偶數時， $p_{2}(n)=p_{4}(n)=0$ 。首先要注意，根據初始條件，這在 $n=0$ 的基本情況下是成立的。對於歸納步驟，假設它在 $n=0$ ， $n=1$ ，...， $n=k$ 這些情況下是成立的，並考慮 $n=k+1$ 的情況。如果 $k+1$ 為奇數，則這兩個
${\begin{array}{rl}p_{1}(k+1)&=0.5\cdot p_{2}(k)=0.5\cdot 0=0\\p_{3}(k+1)&=0.5\cdot p_{2}(k)+0.5\cdot p_{4}(k)=0.5\cdot 0+0.5\cdot 0=0\end{array}}$
源於歸納假設 $p_{2}(k)=p_{4}(k)=0$ ，因為 $k$ 為偶數。 $k+1$ 為偶數的情況類似。

我們可以使用例如

n=100

。這個 Octave 會話
octave:1> B=[1,.5,0,0,0,0; > 0,0,.5,0,0,0; > 0,.5,0,.5,0,0; > 0,0,.5,0,.5,0; > 0,0,0,.5,0,0; > 0,0,0,0,.5,1]; octave:2> B100=B**100 B100 = 1.00000 0.80000 0.60000 0.40000 0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.20000 0.40000 0.60000 0.80000 1.00000 octave:3> B100*[0;1;0;0;0;0] octave:4> B100*[0;1;0;0;0;0] octave:5> B100*[0;0;0;1;0;0] octave:6> B100*[0;1;0;0;0;0]

產生這些輸出。

起始狀態為:	$1	$2	$3	$4
$s_{0}(100)$	0.80000	0.60000	0.40000	0.20000
$s_{1}(100)$	0.00000	0.00000	0.00000	0.00000
$s_{2}(100)$	0.00000	0.00000	0.00000	0.00000
$s_{3}(100)$	0.00000	0.00000	0.00000	0.00000
$s_{4}(100)$	0.00000	0.00000	0.00000	0.00000
$s_{5}(100)$	0.20000	0.40000	0.60000	0.80000

問題 2

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

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

(Feller 1968, p. 424)

答案

從這些方程式
${\begin{array}{*{6}{rc}r}(1/6)s_{1}(n)&+&0s_{2}(n)&+&0s_{3}(n)&+&0s_{4}(n)&+&0s_{5}(n)&+&0s_{6}(n)&=&s_{1}(n+1)\\(1/6)s_{1}(n)&+&(2/6)s_{2}(n)&+&0s_{3}(n)&+&0s_{4}(n)&+&0s_{5}(n)&+&0s_{6}(n)&=&s_{2}(n+1)\\(1/6)s_{1}(n)&+&(1/6)s_{2}(n)&+&(3/6)s_{3}(n)&+&0s_{4}(n)&+&0s_{5}(n)&+&0s_{6}(n)&=&s_{3}(n+1)\\(1/6)s_{1}(n)&+&(1/6)s_{2}(n)&+&(1/6)s_{3}(n)&+&(4/6)s_{4}(n)&+&0s_{5}(n)&+&0s_{6}(n)&=&s_{4}(n+1)\\(1/6)s_{1}(n)&+&(1/6)s_{2}(n)&+&(1/6)s_{3}(n)&+&(1/6)s_{4}(n)&+&(5/6)s_{5}(n)&+&0s_{6}(n)&=&s_{5}(n+1)\\(1/6)s_{1}(n)&+&(1/6)s_{2}(n)&+&(1/6)s_{3}(n)&+&(1/6)s_{4}(n)&+&(1/6)s_{5}(n)&+&(6/6)s_{6}(n)&=&s_{6}(n+1)\end{array}}$
我們得到這個轉移矩陣。
${\begin{pmatrix}1/6&0&0&0&0&0\\1/6&2/6&0&0&0&0\\1/6&1/6&3/6&0&0&0\\1/6&1/6&1/6&4/6&0&0\\1/6&1/6&1/6&1/6&5/6&0\\1/6&1/6&1/6&1/6&1/6&6/6\end{pmatrix}}$

這是 Octave 會話，輸出已編輯並壓縮到表末尾。
octave:1> F=[1/6, 0, 0, 0, 0, 0; > 1/6, 2/6, 0, 0, 0, 0; > 1/6, 1/6, 3/6, 0, 0, 0; > 1/6, 1/6, 1/6, 4/6, 0, 0; > 1/6, 1/6, 1/6, 1/6, 5/6, 0; > 1/6, 1/6, 1/6, 1/6, 1/6, 6/6]; octave:2> v0=[1;0;0;0;0;0] octave:3> v1=F*v0 octave:4> v2=F*v1 octave:5> v3=F*v2 octave:6> v4=F*v3 octave:7> v5=F*v4

這些是結果。

	1	2	3	4	5
1	0.16667	0.027778	0.0046296	0.00077160	0.00012860
0	0.16667	0.083333	0.0324074	0.01157407	0.00398663
0	0.16667	0.138889	0.0879630	0.05015432	0.02713477
0	0.16667	0.194444	0.1712963	0.13503086	0.10043724
0	0.16667	0.250000	0.2824074	0.28472222	0.27019033
0	0.16667	0.305556	0.4212963	0.51774691	0.59812243

問題 3

人們對美國企業是否正在從東北部和中北部地區遷移到南部和西部地區一直很感興趣，這是由於更溫暖的氣候、更低的工資以及工會化程度較低造成的。以下是電力和電子裝置大型企業的過渡矩陣（Kelton 1983，第 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$ 的分佈。系統是否已穩定到平衡狀態？

答案

看起來合理的假設是，雖然公司的當前位置應該強烈地影響它下一次的位置（例如，它是否會留下來），但之前階段的位置應該幾乎沒有影響。也就是說，雖然公司可能會因為當前位置而搬遷或留下來，但它不太可能因為之前的位置而搬遷或留下來。
這段 Octave 會話已編輯，並在最後將輸出整理在一個表格中。
octave:1> M=[.787,0,0,.111,.102; > 0,.966,.034,0,0; > 0,.063,.937,0,0; > 0,0,.074,.612,.314; > .021,.009,.005,.010,.954] M = 0.78700 0.00000 0.00000 0.11100 0.10200 0.00000 0.96600 0.03400 0.00000 0.00000 0.00000 0.06300 0.93700 0.00000 0.00000 0.00000 0.00000 0.07400 0.61200 0.31400 0.02100 0.00900 0.00500 0.01000 0.95400 octave:2> v0=[.025;.025;.025;.025;.900] octave:3> v1=M*v0 octave:4> v2=M*v1 octave:5> v3=M*v2 octave:6> v4=M*v3
總結如下表所示。
${\begin{array}{c|cccc}{\vec {p}}_{0}&{\vec {p}}_{1}&{\vec {p}}_{2}&{\vec {p}}_{3}&{\vec {p}}_{4}\\\hline {\begin{pmatrix}0.025000\\0.025000\\0.025000\\0.025000\\0.900000\end{pmatrix}}&{\begin{pmatrix}0.114250\\0.025000\\0.025000\\0.299750\\0.859725\end{pmatrix}}&{\begin{pmatrix}0.210879\\0.025000\\0.025000\\0.455251\\0.825924\end{pmatrix}}&{\begin{pmatrix}0.300739\\0.025000\\0.025000\\0.539804\\0.797263\end{pmatrix}}&{\begin{pmatrix}0.377920\\0.025000\\0.025000\\0.582550\\0.772652\end{pmatrix}}\end{array}}$
這是上一項中 Octave 會話的延續。
octave:7> p0=[.0000;.6522;.3478;.0000;.0000] octave:8> p1=M*p0 octave:9> p2=M*p1 octave:10> p3=M*p2 octave:11> p4=M*p3

總結如下。
${\begin{array}{c|cccc}{\vec {p}}_{0}&{\vec {p}}_{1}&{\vec {p}}_{2}&{\vec {p}}_{3}&{\vec {p}}_{4}\\\hline {\begin{pmatrix}0.00000\\0.65220\\0.34780\\0.00000\\0.00000\end{pmatrix}}&{\begin{pmatrix}0.00000\\0.64185\\0.36698\\0.02574\\0.00761\end{pmatrix}}&{\begin{pmatrix}0.0036329\\0.6325047\\0.3842942\\0.0452966\\0.0151277\end{pmatrix}}&{\begin{pmatrix}0.0094301\\0.6240656\\0.3999315\\0.0609094\\0.0225751\end{pmatrix}}&{\begin{pmatrix}0.016485\\0.616445\\0.414052\\0.073960\\0.029960\end{pmatrix}}\end{array}}$
這部分內容與前面的 Octave 會話類似。
octave:12> M50=M**50 M50 = 0.03992 0.33666 0.20318 0.02198 0.37332 0.00000 0.65162 0.34838 0.00000 0.00000 0.00000 0.64553 0.35447 0.00000 0.00000 0.03384 0.38235 0.22511 0.01864 0.31652 0.04003 0.33316 0.20029 0.02204 0.37437 octave:13> p50=M50*p0 p50 = 0.29024 0.54615 0.54430 0.32766 0.28695 octave:14> p51=M*p50 p51 = 0.29406 0.54609 0.54442 0.33091 0.29076
這接近於穩態。

問題 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$ 的閾值，使得學習者幾乎可以肯定在五步之內完成學習？

答案

以下是相關的方程組。
${\begin{array}{*{5}{rc}r}(1-2p)\cdot s_{U}(n)&+&p\cdot t_{A}(n)&+&p\cdot t_{B}(n)&&&&&=&s_{U}(n+1)\\p\cdot s_{U}(n)&+&(1-2p)\cdot t_{A}(n)&&&&&&&=&t_{A}(n+1)\\p\cdot s_{U}(n)&&&+&(1-2p)\cdot t_{B}(n)&&&&&=&t_{B}(n+1)\\&&p\cdot t_{A}(n)&&&+&s_{A}(n)&&&=&s_{A}(n+1)\\&&&&p\cdot t_{B}(n)&&&+&s_{B}(n)&=&s_{B}(n+1)\end{array}}$
因此，我們得到以下結果。
${\begin{pmatrix}1-2p&p&p&0&0\\p&1-2p&0&0&0\\p&0&1-2p&0&0\\0&p&0&1&0\\0&0&p&0&1\end{pmatrix}}{\begin{pmatrix}s_{U}(n)\\t_{A}(n)\\t_{B}(n)\\s_{A}(n)\\s_{B}(n)\end{pmatrix}}={\begin{pmatrix}s_{U}(n+1)\\t_{A}(n+1)\\t_{B}(n+1)\\s_{A}(n+1)\\s_{B}(n+1)\end{pmatrix}}$
以下是 Octave 程式碼，已去除輸出內容。
octave:1> T=[.5,.25,.25,0,0; > .25,.5,0,0,0; > .25,0,.5,0,0; > 0,.25,0,1,0; > 0,0,.25,0,1] T = 0.50000 0.25000 0.25000 0.00000 0.00000 0.25000 0.50000 0.00000 0.00000 0.00000 0.25000 0.00000 0.50000 0.00000 0.00000 0.00000 0.25000 0.00000 1.00000 0.00000 0.00000 0.00000 0.25000 0.00000 1.00000 octave:2> p0=[1;0;0;0;0] octave:3> p1=T*p0 octave:4> p2=T*p1 octave:5> p3=T*p2 octave:6> p4=T*p3 octave:7> p5=T*p4
以下是輸出。結束於 $s_{A}$ 的機率約為 $0.23$ .
${\begin{array}{cc|ccccc}&{\vec {p}}_{0}&{\vec {p}}_{1}&{\vec {p}}_{2}&{\vec {p}}_{3}&{\vec {p}}_{4}&{\vec {p}}_{5}\\\hline {\begin{array}{c}s_{U}\\t_{A}\\t_{B}\\s_{A}\\s_{B}\end{array}}&{\begin{array}{c}1\\0\\0\\0\\0\end{array}}&{\begin{array}{c}0.50000\\0.25000\\0.25000\\0.00000\\0.00000\end{array}}&{\begin{array}{c}0.375000\\0.250000\\0.250000\\0.062500\\0.062500\end{array}}&{\begin{array}{c}0.31250\\0.21875\\0.21875\\0.12500\\0.12500\end{array}}&{\begin{array}{c}0.26562\\0.18750\\0.18750\\0.17969\\0.17969\end{array}}&{\begin{array}{c}0.22656\\0.16016\\0.16016\\0.22656\\0.22656\end{array}}\end{array}}$
使用此檔案作為learn.m
# Octave 指令碼檔案用於學習模型。 function w = learn(p) T = [1-2*p,p, p, 0, 0; p, 1-2*p,0, 0, 0; p, 0, 1-2*p,0, 0; 0, p, 0, 1, 0; 0, 0, p, 0, 1]; T5 = T**5; p5 = T5*[1;0;0;0;0]; w = p5(4); endfunction
發出命令octave:1> learn(.20)產生ans = 0.17664.
此 Octave 會話
octave:1> x=(.01:.01:.50)'; octave:2> y=(.01:.01:.50)'; octave:3> for i=.01:.01:.50 > y(100*i)=learn(i); > endfor octave:4> z=[x, y]; octave:5> gplot z
產生此圖。沒有閾值 - 曲線沒有急劇上升的機率。

問題 5

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

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

答案

從這些方程式
${\begin{array}{*{2}{rc}r}0.90\cdot p_{T}(n)&+&0.01\cdot p_{C}(n)&=&p_{T}(n+1)\\0.10\cdot p_{T}(n)&+&0.99\cdot p_{C}(n)&=&p_{C}(n+1)\end{array}}$
我們得到這個矩陣。
${\begin{pmatrix}0.90&0.01\\0.10&0.99\end{pmatrix}}{\begin{pmatrix}p_{T}(n)\\p_{C}(n)\end{pmatrix}}={\begin{pmatrix}p_{T}(n+1)\\p_{C}(n+1)\end{pmatrix}}$
這是 Octave 的結果。
${\begin{array}{c|ccccc}n=0&1&2&3&4&5\\\hline {\begin{array}{c}0.30000\\0.70000\end{array}}&{\begin{array}{c}0.27700\\0.72300\end{array}}&{\begin{array}{c}0.25653\\0.74347\end{array}}&{\begin{array}{c}0.23831\\0.76169\end{array}}&{\begin{array}{c}0.22210\\0.77790\end{array}}&{\begin{array}{c}0.20767\\0.79233\end{array}}\end{array}}$ ${\begin{array}{|ccccc}6&7&8&9&10\\\hline {\begin{array}{c}0.19482\\0.80518\end{array}}&{\begin{array}{c}0.18339\\0.81661\end{array}}&{\begin{array}{c}0.17322\\0.82678\end{array}}&{\begin{array}{c}0.16417\\0.83583\end{array}}&{\begin{array}{c}0.15611\\0.84389\end{array}}\end{array}}$
這是 $s_{T}=0.2$ 結果。
${\begin{array}{c|ccccc}n=0&1&2&3&4&5\\\hline {\begin{array}{c}0.20000\\0.80000\end{array}}&{\begin{array}{c}0.18800\\0.81200\end{array}}&{\begin{array}{c}0.17732\\0.82268\end{array}}&{\begin{array}{c}0.16781\\0.83219\end{array}}&{\begin{array}{c}0.15936\\0.84064\end{array}}&{\begin{array}{c}0.15183\\0.84817\end{array}}\end{array}}$ ${\begin{array}{|ccccc}6&7&8&9&10\\\hline {\begin{array}{c}0.14513\\0.85487\end{array}}&{\begin{array}{c}0.13916\\0.86084\end{array}}&{\begin{array}{c}0.13385\\0.86615\end{array}}&{\begin{array}{c}0.12913\\0.87087\end{array}}&{\begin{array}{c}0.12493\\0.87507\end{array}}\end{array}}$
雖然機率向量開始 $0.1$ 不同，但它們最終只相差 $0.032$ 。所以它們很相似。

問題 6

對於世界系列應用程式，使用計算機為 $p=0.55$ 和 $p=0.6$ 生成七個向量。

即使國家聯盟球隊每場比賽獲勝的機率只有 $0.45$ 或 $0.40$ ，它們贏得冠軍的機率是多少？
繪製機率 $p$ 與美國聯盟球隊贏得冠軍的機率之間的關係圖。是否存在一個閾值——一個 $p$ ，超過這個閾值，實力較強的球隊基本上就能夠確保獲勝？

(下面包含一些示例程式碼。)

答案

這些是 $p=.55$ 向量，

	$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	0
1-0	0	0.55000	0	0	0	0	0	0	0
0-1	0	0.45000	0	0	0	0	0	0	0
2-0	0	0	0.30250	0	0	0	0	0	0
1-1	0	0	0.49500	0	0	0	0	0	0
0-2	0	0	0.20250	0	0	0	0	0	0
3-0	0	0	0	0.16638	0	0	0	0	0
2-1	0	0	0	0.40837	0	0	0	0	0
1-2	0	0	0	0.33412	0	0	0	0	0
0-3	0	0	0	0.09112	0	0	0	0	0
4-0	0	0	0	0	0.09151	0.09151	0.09151	0.09151	0.09151
3-1	0	0	0	0	0.29948	0	0	0	0
2-2	0	0	0	0	0.36754	0	0	0	0
1-3	0	0	0	0	0.20047	0	0	0	0
0-4	0	0	0	0	0.04101	0.04101	0.04101	0.04101	0.04101
4-1	0	0	0	0	0	0.16471	0.16471	0.16471	0.16471
3-2	0	0	0	0	0	0.33691	0	0	0
2-3	0	0	0	0	0	0.27565	0	0	0
1-4	0	0	0	0	0	0.09021	0.09021	0.09021	0.09021
4-2	0	0	0	0	0	0	0.18530	0.18530	0.18530
3-3	0	0	0	0	0	0	0.30322	0.30322	0
2-4	0	0	0	0	0	0	0.12404	0.12404	0.12404
4-3	0	0	0	0	0	0	0	0	0.16677
3-4	0	0	0	0	0	0	0	0	0.13645

而這些是 $p=.60$ 向量。

	$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.60000	0	0	0	0	0	0
0-1	0	0.40000	0	0	0	0	0	0
2-0	0	0	0.36000	0	0	0	0	0
1-1	0	0	0.48000	0	0	0	0	0
0-2	0	0	0.16000	0	0	0	0	0
3-0	0	0	0	0.21600	0	0	0	0
2-1	0	0	0	0.43200	0	0	0	0
1-2	0	0	0	0.28800	0	0	0	0
0-3	0	0	0	0.06400	0	0	0	0
4-0	0	0	0	0	0.12960	0.12960	0.12960	0.12960
3-1	0	0	0	0	0.34560	0	0	0
2-2	0	0	0	0	0.34560	0	0	0
1-3	0	0	0	0	0.15360	0	0	0
0-4	0	0	0	0	0.02560	0.02560	0.02560	0.02560
4-1	0	0	0	0	0	0.20736	0.20736	0.20736
3-2	0	0	0	0	0	0.34560	0	0
2-3	0	0	0	0	0	0.23040	0	0
1-4	0	0	0	0	0	0.06144	0.06144	0.06144
4-2	0	0	0	0	0	0	0.20736	0.20736
3-3	0	0	0	0	0	0	0.27648	0
2-4	0	0	0	0	0	0	0.09216	0.09216
4-3	0	0	0	0	0	0	0	0.16589
3-4	0	0	0	0	0	0	0	0.11059

來自計算機程式碼部分的指令碼可以輕鬆地進行調整。
# 用於計算世界大賽結果的機率的 Octave 指令碼檔案。 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 v7 = (A**7) * v; w = v7(11)+v7(16)+v7(20)+v7(23) endfunction
使用此指令碼，當美聯獲得 $p=0.55$ 贏得每場比賽的機率時，他們贏得先贏四場系列賽的機率為 $0.60829$ 。當他們贏得任何一場比賽的機率為 $p=0.6$ 時，他們贏得系列賽的機率為 $0.71021$ 。
此 Octave 會話
octave:1> 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]; octave:2> x=(.01:.01:.99)'; octave:3> y=(.01:.01:.99)'; octave:4> for i=.01:.01:.99 > y(100*i)=markov(i,v0); > endfor octave:5> z=[x, y]; octave:6> gplot z
產生了這張圖。憑肉眼觀察，如果 $p>0.7$ ，那麼這支隊伍就幾乎可以確定贏得系列賽了。

問題 7

一個 **馬爾科夫矩陣** 的每個條目都為正，並且每一列的總和為 $1$ 。

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

答案

它們必須滿足這個條件，因為狀態轉移的總機率（包括回到相同狀態）為 100%。
參見第三項的答案。
我們將做 $2\!\times \!2$ 的情況；更大的情況只是符號問題。此乘積
${\begin{pmatrix}a_{1,1}&a_{1,2}\\a_{2,1}&a_{2,2}\end{pmatrix}}{\begin{pmatrix}b_{1,1}&b_{1,2}\\b_{2,1}&b_{2,2}\end{pmatrix}}={\begin{pmatrix}a_{1,1}b_{1,1}+a_{1,2}b_{2,1}&a_{1,1}b_{1,2}+a_{1,2}b_{2,2}\\a_{2,1}b_{1,1}+a_{2,2}b_{2,1}&a_{2,1}b_{1,2}+a_{2,2}b_{2,2}\\\end{pmatrix}}$
具有以下兩個列和
$(a_{1,1}b_{1,1}+a_{1,2}b_{2,1})+(a_{2,1}b_{1,1}+a_{2,2}b_{2,1})=(a_{1,1}+a_{2,1})\cdot b_{1,1}+(a_{1,2}+a_{2,2})\cdot b_{2,1}=1\cdot b_{1,1}+1\cdot b_{2,1}=1$
以及
$(a_{1,1}b_{1,2}+a_{1,2}b_{2,2})+(a_{2,1}b_{1,2}+a_{2,2}b_{2,2})=(a_{1,1}+a_{2,1})\cdot b_{1,2}+(a_{1,2}+a_{2,2})\cdot b_{2,2}=1\cdot b_{1,2}+1\cdot b_{2,2}=1$
如所要求的。

計算機程式碼

該指令碼 *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.
Kelton, Christina M.L. (1983), Trends on the Relocation of U.S. Manufacturing, Wiley.
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