轉移矩陣（Transition Matrix）

轉移矩陣（Transition Matrix）
國立臺南第一高級中學數學科林倉億老師

「轉移矩陣」的概念是由俄國數學家馬可夫 (Andrei Andreevich Markov, 1856~1922)在20世紀初時所提出，今日不管是在科學界、工程界還是商業界，都有很廣泛的應用，因此，我們又將「轉移矩陣」稱為「馬可夫矩陣」。讓我們從一個實際例子來了解什麼是「轉移矩陣」。

假設今天在郊區有個住宅區，居民每天可任意選擇自行開車上班，或搭乘大眾運輸工具上班。長期觀察此區的居民，發現當天開車上班的人中，有 \(\frac{4}{5}\) 的人隔天會繼續開車，另外的 \(\frac{1}{5}\) 會改搭大眾運輸工具；而當天搭乘大眾運輸工具的人中，有 \(\frac{2}{5}\) 的人隔天會繼續搭乘，但有  \(\frac{3}{5}\) 的人會改為自行開車。倘若我們是當地的交通主管官員，當看到這樣子的數據時，我們可以做出何種預測呢？預測正確，我們所做的決策才不會有問題。

首先，我們可以先調查今天開車與搭乘大眾運輸工具的人數比例，假設剛好各佔一半，然後將這些資料以表格的方式呈現：

接下來我們就一天一天算出開車與搭乘大眾運輸工具的人數比例：

明天開車的人：\(\frac{4}{5} \cdot \frac{1}{2} + \frac{3}{5} \cdot \frac{1}{2} = \frac{7}{{10}}\) ；
明天搭乘大眾運輸工具的人：\(\frac{1}{5} \cdot \frac{1}{2} + \frac{2}{5} \cdot \frac{1}{2} = \frac{3}{{10}}\)

後天開車的人：\(\frac{4}{5} \cdot \frac{7}{{10}} + \frac{3}{5} \cdot \frac{3}{{10}} = \frac{{37}}{{50}}\) ；
後天搭乘大眾運輸工具的人：\(\frac{1}{5} \cdot \frac{7}{{10}} + \frac{2}{5} \cdot \frac{3}{{10}} = \frac{{13}}{{50}}\)

\(\vdots\)

從上述的算式當中，我們可以發現，明天開車與搭乘大眾運輸工具的人數比例，

其實就是將兩個矩陣相乘的結果：

\(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{4}{5} \cdot \frac{1}{2} + \frac{3}{5} \cdot \frac{1}{2}}\\ {\frac{1}{5} \cdot \frac{1}{2} + \frac{2}{5} \cdot \frac{1}{2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{7}{{10}}}\\ {\frac{3}{{10}}} \end{array}} \right]\)，

而後天的人數比例，則是繼續乘以矩陣 \(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]\)，

即 \(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}} {\frac{7}{{10}}}\\ {\frac{3}{{10}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{4}{5} \cdot \frac{7}{{10}} + \frac{3}{5} \cdot \frac{3}{{10}}}\\ {\frac{1}{5} \cdot \frac{7}{{10}} + \frac{2}{5} \cdot \frac{3}{{10}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{{37}}{{50}}}\\ {\frac{{13}}{{50}}} \end{array}} \right]\)，

我們也可以將它寫成：

\(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right] \cdot \left( {\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]} \right) = {\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]^2} \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{{37}}{{50}}}\\ {\frac{{13}}{{50}}} \end{array}} \right]\)。

如此一來，要知道 \(n\) 天後的人數比例就很簡單了，就是 \({\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]^n} \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\)，

算出它就對了！當然啦，透過電腦計算是比較簡便的方法。

上述的例子中，我們發現要算下一天的比例，

就是將矩陣 \(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]\)（以下稱之為矩陣 \(M\) ）乘以前一天的比例，

因此，矩陣 \(M\) 就是決定人數比例如何轉移的關鍵，我們就稱矩陣 \(M\) 為「轉移矩陣」。

仔細觀察矩陣，會發現它有兩個重要的特徵：第一是矩陣 \(M\) 中的每個元都介於0與1之間；第二則是矩陣 \(M\) 中每行的各元之和都是1。這兩個特徵其實就是我們定義「轉移矩陣」的依據：

若 \(n\) 階方陣 \(M = {\left[ {{a_{i{\kern 1pt} j}}} \right]_{\;n \times n}}\) 滿足：

                                                        (1) 每個 \(a_{ij}\) 都滿足 \(0\leq a_{ij} \leq 1\) ；

                                                        (2) 每行的各元之和為1。

我們就稱 \(M\) 為「\(n\)階轉移矩陣」，簡稱為「轉移矩陣」。

例如，\(\left[ {\begin{array}{*{20}{c}} 0&1\\ 1&0 \end{array}} \right]\)、\(\left[ {\begin{array}{*{20}{c}} {0.2}&{0.4}&{0.3}\\ {0.3}&{0.1}&{0.7}\\ {0.5}&{0.5}&0 \end{array}} \right]\) 都是轉移矩陣。

回到文章一開始的例子，

並別忘了現在我們可是當地的交通主管官員，我們可是要作出預測、決策的。

從前兩天的計算數據看來，開車的人數比例是增加的：\(\frac{1}{2} \to \frac{7}{{10}} \to \frac{{37}}{{50}}\) ，

而開車的人中，有高達 \(\frac{4}{5}\) 的人會在隔天繼續開車，

而搭乘大眾運輸工具的人中，有超過一半的人會在隔天開車，

因此，我們可以合理推測，開車的人數比例在初期（一開始人數是各半的）是會持續地增加。

身為交通主管官員，我們當然要去想想，有沒有可能在長期之後，比例會趨近定值？

如果我們利用 \({\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]^n} \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\) 多乘幾次，

就會發現開車的人數比例會越來越接近 \(\frac{3}{4}\) ，那 \(\frac{3}{4}\) 會不會就是最終的比例呢？讓我們算算看！

若某一天開車的人數比例是 \(x\)，隔天也還是 \(x\) 不變，則我們就可以列出下面的等式：

\(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}} x\\ {1 – x} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} x\\ {1 – x} \end{array}} \right]\;\;\)

\(\Rightarrow \;\;\left[ {\begin{array}{*{20}{c}} {\frac{3}{5} + \frac{1}{5}x}\\ {\frac{2}{5} – \frac{1}{5}x} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} x\\ {1 – x} \end{array}} \right]\;\; \Rightarrow \;\;\frac{3}{5} + \frac{1}{5}x = x\;\; \Rightarrow \;\;x = \frac{3}{4}\)

的確，當開車人數比例到達 \(\frac{3}{4}\) 後，這比例就不會再變化了，

也就是當 \(n\) 越來越大的時候， \({\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]^n} \cdot \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\) 就會越來越趨近 \(\left[ {\begin{array}{*{20}{c}} {\frac{3}{4}}\\ {\frac{3}{4}} \end{array}} \right]\)  ，

這時，我們就將 \(\left[ {\begin{array}{*{20}{c}} {\frac{3}{4}}\\ {\frac{3}{4}} \end{array}} \right]\) 稱為矩陣 \(\left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]\) 的「穩定狀態」。

請讀者特別留意，在上述求穩定狀態的算式中，並沒有用到一開始的比例 \(\left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\) ，

也就是說，穩定狀態其實是與初始的狀態是無關的！

換句話說，

不管我們今天調查出來的比例是 \(\left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\) 還是\(\left[ {\begin{array}{*{20}{c}} {\frac{9}{10}}\\ {\frac{1}{10}} \end{array}} \right]\) ，到最後都是會趨進於的 \(\left[ {\begin{array}{{c}} {\frac{3}{4}}\\ {\frac{3}{4}} \end{array}} \right]\) ！

由上述的分析計算中，我們可以預測出該住宅區的人中，未來將有 \(\frac{3}{4}\) 的人選擇自行開車上班，也就是說，未來的交通狀況會呈現惡化的情況，塞車會越來越頻繁且嚴重。身為交通主管官員的我們，面對這未來很可能出現的民怨，顯然有兩個預防措施可供決策，一是及早將道路拓寬，或是多蓋幾條替代道路；二就是提供獎勵，讓居民搭乘大眾運輸工具的意願上升。該選擇哪一個措施比較好呢？這不是個容易回答的問題，因為它是政治問題，不是數學問題！

而在此，我們不談政治，我們要多談一點數學，多了解轉移矩陣的穩定狀態。請讀者接下來參閱〈轉移矩陣的穩定狀態與Google搜尋引擎〉一文。