轉移矩陣

Template:NoteTA Template:Distinguish 在数学中，随机矩阵（stochastic matrix）是用来描述一个马尔可夫链的转变的矩阵，亦称为概率矩阵（probability matrix）、转移矩阵（transition matrix）、替代矩阵（substitution matrix）、马尔可夫矩阵（Markov matrix）或转移概率矩阵（transition probability matrix）。它的每一项都是一个表示概率的非负实数。它适用于概率论、统计学和线性代数，也在计算机科学和群体遗传学中使用。 有几种不同的定义和类型随机矩阵：

• 右随机矩阵（right stochastic matrix）是实方阵，其中每一-{zh-cn:行;zh-hk:行;zh-mo:行;zh-sg:行;zh-tw:列}-求和为1。
• 左随机矩阵（left stochastic matrix）是实方阵，其中每一-{zh-cn:列;zh-hk:列;zh-mo:列;zh-sg:列;zh-tw:行}-求和为1。
• 双随机矩阵（doubly stochastic matrix）是非负实数方阵，每个行和列求和均为1。

同理，可以定义随机向量（也称为概率向量）为元素为非负实数且和为1的向量。因此，右随机矩阵的每一-{zh-cn:行;zh-hk:行;zh-mo:行;zh-sg:行;zh-tw:列}-（或左随机矩阵的每一-{zh-cn:列;zh-hk:列;zh-mo:列;zh-sg:列;zh-tw:行}-）都是一个随机向量。

在英语数学文献中的惯例是用概率的-{zh-cn:行向量;zh-hk:行向量;zh-mo:行向量;zh-sg:行向量;zh-tw:列向量}-和概率的右随机矩阵，而不用-{zh-cn:列向量;zh-hk:列向量;zh-mo:列向量;zh-sg:列向量;zh-tw:行向量}-和左随机矩阵，本文遵循此惯例。

定义和性质

随机矩阵描述了在一个有限状态空间 S 上的马尔可夫链 ${𝑿}_t$。

如果在一个时间步长内从 $i$ 到$j$移动的概率为 $\mathrm{Pr}(j|i)=P_{i,j}$ ，随机矩阵 $P$ 的第 $i$ -{zh-cn:行;zh-hk:行;zh-mo:行;zh-sg:行;zh-tw:列}-，第 $j$ -{zh-cn:列;zh-hk:列;zh-mo:列;zh-sg:列;zh-tw:行}-元素由 $P_{i,j}$ 给出，例如，

$P=\left[\begin{array}{cccccc}{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}\\ ⋮& ⋮& \ddots & ⋮& \ddots & ⋮\\ P_{i,1}& P_{i,2}& \dots & P_{i,j}& \dots & P_{i,S}\\ ⋮& ⋮& \ddots & ⋮& \ddots & ⋮\\ P_{S,1}& P_{S,2}& \dots & P_{S,j}& \dots & P_{S,S}\end{array}\right].$

由于从状态 $i$ 到下一状态的概率总和必须是 1，这个矩阵是一个右随机矩阵，于是

$\sum _j{P}_{i,j}=1$

从 $i$ 到 $j$ 分两步转变的概率由然后由给定的 $P$ 的平方矩阵的 $(i,j)$ 号元素给出：

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

一般地，在由矩阵$P$给出的有限马尔可夫链上从任何状态转移到另一个状态的 k 步转移概率为 $P^k$。

初始分布为一个-{zh-cn:行向量;zh-hk:行向量;zh-mo:行向量;zh-sg:行向量;zh-tw:列向量}-。

平稳概率向量 $\mathit{\pi }$ 定义为不随转移矩阵的运用而变化的一个向量；也就是说，它定义为概率矩阵的左特征向量，其特征值为1：

$\mathit{\pi }P=\mathit{\pi }$

Template:Link-en保证了每个随机矩阵都具有这样的向量，而特征值的最大绝对值始终为1。在一般情况下，可能有多个这样的向量。然而，对于具有严格正项的矩阵，该向量是唯一的，并可以观察到对任意 $i$ 我们都有以下极限而求出，

$\underset{k\to \mathrm{\infty }}{\lim }{\left(P^k\right)}_{i,j}={\mathit{\pi }}_j$ ，

其中 ${\mathit{\pi }}_j$ 是-{zh-cn:行;zh-hk:行;zh-mo:行;zh-sg:行;zh-tw:列}-向量 $\mathit{\pi }$ 的第 $j$ 个元素。在其他方面，这表示处在状态 $j$ 下的长期概率与初始状态 $i$ 是独立的。这两种计算得到相同的稳定向量是遍历定理的一种形式，在各种各样的耗散动力系统广泛成立：该系统随着时间演变到定态。

直观地看，随机矩阵表示一个马尔可夫链；对概率分布应用随机矩阵，就是将原始分布的概率质量进行重新分布，同时保持其总质量。如果反复应用此过程，分布就会收敛为马尔可夫链的平稳分布。

應用

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

性質

設$𝐀$、$𝐁$為二個n×n階轉移矩陣，則以下亦為轉移矩陣:

• $𝐀𝐁$
• ${𝐀}^2$
• $\frac{1}{2}(𝐀+𝐁)$

范例：猫和老鼠

假设你有一个计时器和五个相邻的格子排成一行，零时刻有一只猫在第一个格子中，而一只老鼠在第五个格子中。在计时器增加的时候猫和老鼠都会随机跳到一个相邻的格子中。例如，如果猫在第二个格子，老鼠在第四个，在计时器增加后，猫会出现在第一个格子且老鼠会出现在第五个格子的概率为1/4。如果猫在第一个格子而老鼠在第五个，那么计时器增加后，猫会出现在第二个格子且老鼠会出现在第四个的概率为1。当它们处于同一个格子的时候，猫会吃掉老鼠，游戏结束。随机变量 K 给出了老鼠仍留在游戏中的时间步长。

表示这个包含五种位置组合 (猫,鼠) 的状态的游戏的马尔可夫链为：

• 状态 1：(1,3)
• 状态 2：(1,5)
• 状态 3：(2,4)
• 状态 4：(3,5)
• 状态 5：游戏结束：(2,2), (3,3) & (4,4)

我们使用一个随机矩阵来表示这个系统的转移概率（这个矩阵中的行和列用上面提到的可能状态来索引），

$P=\left[\begin{array}{ccccc}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\end{array}\right]$

长期平均

无论初始状态是什么，猫最终都会抓到老鼠（概率为1），且极限为稳态 π = (0,0,0,0,1)。要计算随机变量 Y 的长期平均或期望值。对每种状态 S_j 和时间 t_k，都有 Y_j,k·P(S=S_j,t=t_k) 的贡献。生存与否可以视作一个二值变量，Y=1 代表生存状态而 Y=0 代表终止状态。Y=0 的状态不对长期平均有贡献。

位相型表示

老鼠的生存函数。老鼠至少在第一个时间步长存活。

由于状态 5 是一个吸收态，吸收对时间的分布为Template:Le。假设系统从状态 2 开始，表示为向量 $[0,1,0,0,0]$。老鼠死亡后的状态不会对生存平均产生影响，所以状态五可以忽略。初始状态和转移矩阵可以化简为，

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

以及，

$T=\left[\begin{array}{cccc}0& 0& 1/2& 0\\ 0& 0& 1& 0\\ 1/4& 1/4& 0& 1/4\\ 0& 0& 1/2& 0\end{array}\right]$；而 $(I-T{)}^{-1}1=\left[\begin{array}{c}2.75\\ 4.5\\ 3.5\\ 2.75\end{array}\right],$

其中 $I$ 为单位矩阵，$\mathrm{𝟏}$ 表示全为1的-{zh-cn:列;zh-hk:列;zh-mo:列;zh-sg:列;zh-tw:列}-矩阵，进行状态的相加。

由于每个状态都占据一个时间步长，老鼠生存时间的期望就是在所有生存状态和时间步长中占据的概率之和，

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

其高阶矩为

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

参见

• Muirhead's inequality
• Template:Link-en
• 密度矩陣
• Template:Link-en
• Discrete phase-type distribution
• Template:Link-en
• Models of DNA evolution
• Template:Link-en，随机矩阵在连续状态空间的等价形式

参考文献

• G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling, 1st edition. Chapter 2: PH Distributions; ASA SIAM, 1999.