轉移矩陣

在數學中，隨機矩陣（stochastic matrix）是用來描述一個馬爾可夫鏈的轉變的矩陣，亦稱為機率矩陣（probability matrix）、轉移矩陣（transition matrix）、替代矩陣（substitution matrix）、馬爾可夫矩陣（Markov matrix）或轉移機率矩陣（transition probability matrix）。它的每一項都是一個表示機率的非負實數。它適用於機率論、統計學和線性代數，也在電腦科學和群體遺傳學中使用。

有幾種不同的定義和類型隨機矩陣：

- 右隨機矩陣（right stochastic matrix）是實方陣，其中每一列求和為1。
- 左隨機矩陣（left stochastic matrix）是實方陣，其中每一行求和為1。
- 雙隨機矩陣（doubly stochastic matrix）是非負實數方陣，每個行和列求和均為1。

同理，可以定義隨機向量（也稱為機率向量）為元素為非負實數且和為1的向量。因此，右隨機矩陣的每一列（或左隨機矩陣的每一行）都是一個隨機向量。

在英語數學文獻中的慣例是用機率的列向量和機率的右隨機矩陣，而不用行向量和左隨機矩陣，本文遵循此慣例。

## 定義和性質

隨機矩陣描述了在一個有限狀態空間 S 上的馬爾可夫鏈 $\boldsymbol{X}_{t}$。

如果在一個時間步長內從 $i$ 到$j$移動的機率為 $\operatorname{Pr}(j|i)=P_{i,j}$，隨機矩陣 $P$ 的第 $i$ 列，第 $j$ 行元素由 $P_{i,j}$ 給出，例如。

$$P=\left[\begin{matrix} P_{1,1}&P_{1,2}&\dots&P_{1,j}&\dots&P_{1,S}\\ P_{2,1}&P_{2,2}&\dots&P_{2,j}&\dots&P_{2,S}\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\ P_{i,1}&P_{i,2}&\dots&P_{i,j}&\dots&P_{i,S}\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\ P_{S,1}&P_{S,2}&\dots&P_{S,j}&\dots&P_{S,S}\\ \end{matrix}\right].$$

由於從狀態 $i$ 到下一狀態的機率總和必須是 1，這個矩陣是一個右隨機矩陣，於是

$$\sum_j P_{i,j}=1 \,$$

從 $i$ 到 $j$ 分兩步轉變的機率由然後由給定的 $P$ 的平方矩陣的 $(i,j)$ 號元素給出：

$$\left(P ^{2}\right)_{i,j}$$

一般地，在由矩陣$P$給出的有限馬爾可夫鏈上從任何狀態轉移到另一個狀態的 k 步轉移機率為 $P^k$。

初始分布為一個列向量。

平穩機率向量 $\boldsymbol{\pi}$ 定義為不隨轉移矩陣的運用而變化的一個向量；也就是說，它定義為機率矩陣的左特徵向量，其特徵值為1：

$$\boldsymbol{\pi}P=\boldsymbol{\pi}$$

佩龍一弗羅賓尼斯定理保證了每個隨機矩陣都具有這樣的向量，而特徵值的最大絕對值始終為1。在一般情況下，可能有多個這樣的向量。然而，對於具有嚴格正項的矩陣，該向量是唯一的，並可以觀察到對任意 $i$ 我們都有以下極限而求出。

$\lim_{k\rightarrow\infty}\left(P^k \right)_{i,j}=\boldsymbol{\pi}_j$。

其中 $\boldsymbol{\pi}_{j}$ 是列向量 $\boldsymbol{\pi}$ 的第 $j$ 個元素。在其他方面，這表示處在狀態 $j$ 下的長期機率與初始狀態 $i$ 是獨立的。這兩種計算得到相同的穩定向量是遍歷定理的一種形式，在各種各樣的耗散動力系統廣泛成立：該系統隨著時間演變到定態。

直觀地看，隨機矩陣表示一個馬爾可夫鏈；對機率分布應用隨機矩陣，就是將原始分布的機率質量進行重新分布，同時保持其總質量。如果反覆應用此過程，分布就會收斂為馬爾可夫鏈的平穩分布。

## 應用

轉移矩陣可用以表示機率(或變化比率)，而矩陣相乘的結果可用以預測未來事件發生的機率。

## 性質

設$\mathbf{A}$、$\mathbf{B}$為二個n×n階轉移矩陣，則以下亦為轉移矩陣:

- $$\mathbf{AB}$$
- $$\mathbf{A}^2$$
- $$\frac{1}{2}(\mathbf{A}+\mathbf{B})$$

## 範例：貓和老鼠

假設你有一個計時器和五個相鄰的格子排成一行，零時刻有一隻貓在第一個格子中，而一隻老鼠在第五個格子中。在計時器增加的時候貓和老鼠都會隨機跳到一個相鄰的格子中。例如，如果貓在第二個格子，老鼠在第四個，在計時器增加後，貓會出現在第一個格子且老鼠會出現在第五個格子的機率為1/4。如果貓在第一個格子而老鼠在第五個，那麼計時器增加後，貓會出現在第二個格子且老鼠會出現在第四個的機率為1。當它們處於同一個格子的時候，貓會吃掉老鼠，遊戲結束。隨機變量 K 給出了老鼠仍留在遊戲中的時間步長。

表示這個包含五種位置組合 (貓,鼠) 的狀態的遊戲的馬爾可夫鏈為：

- 狀態 1：(1,3)
- 狀態 2：(1,5)
- 狀態 3：(2,4)
- 狀態 4：(3,5)
- 狀態 5：遊戲結束：(2,2), (3,3) & (4,4)

我們使用一個隨機矩陣來表示這個系統的轉移機率（這個矩陣中的行和列用上面提到的可能狀態來索引）。

$$P = \begin{bmatrix} <pre> 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 1/4 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 </pre> \end{bmatrix}$$

### 長期平均

無論初始狀態是什麼，貓最終都會抓到老鼠（機率為1），且極限為穩態 π = (0,0,0,0,1)。要計算隨機變量 Y 的長期平均或期望值。對每種狀態 Sj 和時間 tk，都有 Yj,k·P(S=Sj,t=tk) 的貢獻。生存與否可以視作一個二值變量，Y=1 代表生存狀態而 Y=0 代表終止狀態。Y=0 的狀態不對長期平均有貢獻。

### 位相型表示

<image>

由於狀態 5 是一個吸收態，吸收對時間的分布為離散位相型分布。假設系統從狀態 2 開始，表示為向量 $[0,1,0,0,0]$。老鼠死亡後的狀態不會對生存平均產生影響，所以狀態五可以忽略。初始狀態和轉移矩陣可以化簡為。

$$\boldsymbol{\tau}=[0,1,0,0]$$

以及。

$T=\begin{bmatrix} <pre> 0 & 0 & 1/2 & 0\\ 0 & 0 & 1 & 0\\ 1/4 & 1/4 & 0 & 1/4\\ 0 & 0 & 1/2 & 0 </pre> \end{bmatrix}$；而 $(I-T)^{-1}\boldsymbol{1} =\begin{bmatrix}2.75 \\ 4.5 \\ 3.5 \\ 2.75\end{bmatrix}\,,$

其中 $I$ 為單位矩陣，$\mathbf{1}$ 表示全為1的列矩陣，進行狀態的相加。

由於每個狀態都占據一個時間步長，老鼠生存時間的期望就是在所有生存狀態和時間步長中占據的機率之和。

$$E[K]=\boldsymbol{\tau}(I+T+T^2+\cdots)\boldsymbol{1}=\boldsymbol{\tau}(I-T)^{-1}\boldsymbol{1}=4.5$$

其高階矩為

$$E[K(K-1)\dots(K-n+1)]=n!\boldsymbol{\tau}(I-{T})^{-n}{T}^{n-1}\mathbf{1}\ $$

## 參見

- Muirhead's inequality
- 佩龍一弗羅賓尼斯定理
- 密度矩陣
- 雙隨機矩陣
- Discrete phase-type distribution
- 機率自動機
- Models of DNA evolution
- 馬爾可夫核，隨機矩陣在連續狀態空間的等價形式