概率统计随机过程之马尔可夫过程转移矩阵（随机矩阵）

Oct 30, 2020 · 概率统计随机过程 ·

分享到:

概率统计随机过程之转移矩阵（随机矩阵）

注：本文说的随机矩阵是转移矩阵，英文叫stochastic matrix不是random matrix。

极限行为和不变概率（稳态）
状态分类
周期性与非周期
可约与不可约
不可约非周期链→遍历链
可约性、非常返态和周期的影响
随机矩阵的主特征1的简单证明
从线性代数的角度看马尔可夫矩阵

极限行为和不变概率（稳态）

有转移矩阵$P$，但经过$N→ ∞$后，是否存在一个收敛的极限矩阵 \[\Pi=\lim_{n→ ∞}P^n\] 如果能有一个更好的性质： >极限矩阵每一行都是一样的。

那么对于任一个概率向量$\vec v$(每一项非负且和为1)，都有： \[\vec \pi=\vec v\lim_{n→ ∞}P^n\] 则$\vec \pi$为不变概率分布或稳态概率分布。这个时候，$\Pi$的值应该是 \[\Pi=\lim_{n→ ∞}P^n=\begin{bmatrix} \vec \pi\\ \vec \pi\\ \vdots\\ \vec \pi \end{bmatrix}\] 因为向量左乘是行线性组合，$\vec \pi$之间的任何线性组合都是$\vec \pi$.

那么什么样的矩阵能有稳态分布吧?

主特征值为1，且为单重（1）
能选出一个非负的左特征向量（2）

随机矩阵的主特征值为1这点可以证明见章节随机矩阵的主特征1的简单证明。但是主特征值为单重和非负左特征向量需要更高等的数学技巧。我们用Perron–Frobenius theorem先给出一部分符合两点要求的矩阵。

Perron–Frobenius theorem给出了一系列符合这两点的矩阵：

定理1：Perron–Frobenius theorem：所有元素均为正实数的正矩阵的基本性质的重要定理.该定理断言:若矩阵$A>0，ρ(A)为A$的谱半径，则:

$ρ(A)$为$A$的正特征值,其对应的一个特征向量为正特征向量。

对于$A$的任意其他特征值，都有$|λ|<ρ(A)$

$ρ(A)是A$的单重特征值。

尽管Perron–Frobenius theorem给出了一系列矩阵，但是却不能覆盖所有具有适当极限性质的随机矩阵。因为随机矩阵的要求是非负，而不是全是正数。尽管随机矩阵$P$的元素不全是正数，但是我们注意到，$P^n$可能是全正的。而且根据矩阵的特征值分解，$P^n$的特征值为$P$特征值的n次方，且特征向量不变。而$P$主特征值1的任意次方都是1，所以只要$P^n$满足了Perron–Frobenius theorem，那么$P$也满足。

鉴于此，我们给出以下结论：

结论1：如果$P$是一个随机矩阵，且对于某一n，$P^n$的所有元素都是正数，则$P$满足条件（1）（2）。

状态分类

那么到底什么样的矩阵，当$n$充分大时，$P^n$的元素全都是正的呢？答案是遍历的随机矩阵。遍历的随机矩阵是不可约、非周期的矩阵。几个不能符合（1）（2）的矩阵包括：可约的，随机矩阵不收敛（周期性），有非常返态的（因为非常返态导致矩阵可约）。

下面对几个概念进行介绍。

周期性与非周期

一种直观情况：如果有正整数$d,d>1$，只有当$n=d,2d,3d,…$时，有$p(n)_{ij}>0$，则状态i为周期性的状态，周期为$d$。

周期性所说不直观的定义：若集合$\{n: n≥1, p_{ii}> 0\}$非空，则称它的最大公约数，$d=d(i)$为状态$i$的周期。若$d>1$，称$i$是周期的;若$d=1$,称 $i$是非周期的。（引用：《应用随机过程（张波）》，第5章）

我当初也纳闷，定义中取公约数和周期没啥关系，然而，这才是更加完善的周期。见下图（《应用随机过程（张波）》，图5-3）

马尔可夫链周期性由状态1出发返回状态1的步长为$T=\{4,6,8,10,12,...\}$，很直观的感受到，4步之后就是两步两步的间隔了。

定义周期：方案一是取4，但是会丢失了$\{6,10,14...\}$这些步长；方案二就是取公约数2，就可以防止$\{6,10,14...\}$步长的丢失，弊端也许就是不如$\{d,2d,3d...\}$这种结构来得直观。（有点像$y=ax+b，a$是周期）。

补充：当马尔可夫链中任意一个状态都为周期性的状态时，则称马尔可夫链是周期的。但非周期性的马尔可夫链才是我们想要的，它是构成遍历的马尔可夫链的必要条件，遍历的马尔可夫有很多好的性质。

定理2：如果状态$i$和$j$互通，那么$d(i)=d(j)$（互通类中各状态周期相等。）

非周期定义：如果链从所有任意起点返回到自己所需要的步数集的最大公约数为1，则说明此链是非周期的，即所有状态不是定期返回的且所有返回的间隔的最大公约数为1。但是并不是说，返回自己的状态只需要一步，而是说，对于某个步数$M$，所有步数n，满足$n≥M$，都能够返回原状态。

如何判别一个状态是非周期的？

若此状态带有自环，则必为非周期的（虽然非周期的状态不一定有自环）

若此状态与一个非周期的状态互通，则必为非周期的。（定理2应用）

以上只是两个充分条件。

可约与不可约

互通：如果马尔可夫链里某状态$i$经过$n$步到达状态$j$的概率$>0$且相反的，状态$j$经过$n$步到$i$的概率也$>0$，即说明这俩状态是互通的. 如果对所有$n$上面都不成立，则证明$i,j$不通。

可约的（reducible），意思就是在状态集中至少存在一个状态$i$到状态$j$是不通的！注意有可能$j$到$i$是通的，互通是一个相互的概念。$i→j$同时$j→i$才是互通。可约就是存在不互通的状态。

不可约（irreducible），意思是马尔可夫链链从状态空间里一个位置经过有限步跳转到任何一个位置的概率大于0，即说的是马氏链里任何两个状态都是互通的。

不可约非周期链→遍历链

现在我们来证明一个非周期、不可约的转移矩阵满足结论（1），即 >如果$P$是非周期、不可约的转移矩阵(遍历的)，那么存在$M>0,\forall n≥M$，有$P^n$>0(每一个元素大于0)。$\Leftrightarrow$存在稳态概率$\vec\pi$的条件。

证明：

取任意$i,j$，由于矩阵$P$不可约，所以$i,j$属于同一个连通类。因此存在一个数，记为$m_{ij}$，使得$p_{m_{ij}}(i,j)>0$，即$i$通过$m_{ij}$次转移后到达$j$。

此外，由于$P$是非周期的，因此存在一个$M_i$，使得所有$n≥M_i$，有$p_n(i,i)>0$（非周期的性质）。因此对所有的n≥M_i$，有 $$p_{n+m_{ij}}(i,j)≥p_n(i,i)p_{m_{ij}}(i,j)>0$$ 令$M$为所有$i,j$组合中$M_i+m_{ij}$的最大值（现在讨论有限状态马氏链，因此最大值存在），则对于所有$n≥M$，以及任意的$i,j$都有 \[p_{n}(i,j)>0.\] 因此，由$i,j$的任意性可知：存在$n$，使得$P^n$中每一项大于0。

如果我们用更加数学的语言描述，将其归纳成定理：

定理3：如果$P$是非周期、不可约的马尔可夫链转移矩阵，则存在一个唯一一个不变（稳态）概率向量$\vec\pi$，满足 \[\vec\pi P=\vec\pi(这不是特征向量的转置吗？)\] 如果$\phi_0$为任一初始概率向量，则有 \[\lim_{n→ ∞}\phi_0P^n=\vec\pi\]

这也给我们求不变概率提示了一个更简单的方法，求转置矩阵$P^T$特征值为1时的特征向量，并要求次特征向量1-范数为1。（矩阵的特征值在转置变换中不改变，转置矩阵与原矩阵是相似的。）

可约性、非常返态和周期的影响

可约性：可以当成几个不可约的子矩阵处理。

非常返态：初始概率会对最终稳态概率有影响。

周期：绝对值为1的特征值不只1个，周期是几，就有几个不同的绝对值为1的复根。同样，周期是多少，就有多少个不同的状态组，每个状态组都有其极限值。有平均稳态，是各个状态组极限稳态概率的平均数。

随机矩阵的主特征1的简单证明

按照定义$A*[1,1,1,...1,1,1]^T$得到一个列向量。

而$A$是一个随机矩阵(这里以行的和为1为例)，即$A$的每一行和为1，$A*[1,1,1,...1,1,1]^T$的每一个元素按照定义展开，正好是A的每一行的和，即是1，所以

$A*[1,1,1,...1,1,1]^T=[1,1,1,...1,1,1]^T$。按照特征值的定义，即得到一个特征值为1。

然后你还要证明1是最大的特征值。

矩阵的1范数是1（行和范数），而根据范数不等式，任何范数都大于等于谱半径（=最大特征值），所以该矩阵的最大特征值不大于1，而，已知有一个特征值为1，所以最大特征值就是1。

（其实严谨点还需要证明这个最大特征值即谱半径的重数为1）

严谨证明请看：Perron–Frobenius theorem

从线性代数的角度看马尔可夫矩阵

如果我们从线性代数的角度看马尔可夫矩阵，会有一个整体的视角，获得更直观的认识。

我们如果通过特征基来表示马尔可夫矩阵$A$，有： \[ Av=c_1\lambda_1 x_1+c_2\lambda_2 x_2+\dotsb+c_n\lambda_n x_n\\ v=c_1x_1+c_2x_2+\dotsb+c_nx_n \] 其中，$\lambda_i$是矩阵$A$的特征值，且我们将其按从大到小顺序排好，向量$x_i$是对应的特征矩阵，我们将任意向量$v$用特征基表示，其系数为$c_i$。

那么，初始状态向量经过$k$个周期的马尔可夫矩阵为： \[v_k=A^kv=c_1\lambda_1^k x_1+c_2\lambda_2^k x_2+\dotsb+c_n\lambda_n^k x_n\] 如果想让$v_k$趋于稳态，那么特征值的$|\lambda_i|$都必须小于等于1，否则矩阵就会发散。

我们再看行列式$\det(A-I)$，由于$A$的每一列和为1，当对角元素减1后，列和必然为0，因此$A-I$的行向量是线性相关的，即$A-I$是奇异矩阵，所以$\det(A-I)=0$，这使得1是$A$的一个特征值。

设特征值$\lambda_1\sim\lambda_i$为1，剩下的小于1，那么当$k\rightarrow ∞$时，有$\lambda_1^k,\dotsb,\lambda_i^k=1,\lambda_{i+1},\dotsb,\lambda_n\rightarrow 0$，此时 \[ v_k=A^kv=c_1 x_1+c_2 x_2+\dotsb+c_ix_i \] 即为稳态。