随机过程

随机过程：一个随机过程${X_t},t\in T$是随机变量的一个集合，也即对每个$t\in T$，$X_t$是随机变量

随机过程中的$t$往往解释为时间，此时可将$X_t$视作过程在时间$t$的状态，即$X_t=i$表示过程在时刻$t$处于状态$i$

当T为可数集时，相应的随机过程称为离散时间过程，当$T$为一个实数区间时，则称为连续时间过程

随机过程的状态空间定义为随机变量$X_t$的所有可能取值

马尔可夫链

令${X_n},n=0,1,2,…$是状态空间中包含有限个或可数个可能值的随机过程

若对任意$i,j$都有一个固定概率$P{ij}$，使得过程当前时刻在状态$i$而下一时刻在状态$j$，则该随机过程称为马尔可夫链(Markov Chain)，若$P{ij}$与时间无关，则称为时间齐次马尔可夫链，以下讨论的都是齐次的马链

形式化的，对于任意$n\geq 0$，有

通俗的说，对于一个马尔可夫链，给定过去的状态$X0,X_1,…,X{n-1}$和当前状态$Xn$，未来状态$X{n+1}$条件独立于过去的状态，只依赖于当前状态

记$P$为转移概率$P_{ij}$的矩阵，即有

定义$P^n_{ij}$表示处于状态$i$的过程在$n$次转移后处于状态$j$的概率，即

我们可以用C-K方程来计算$P^n_{ij}$

若将$P^{(n)}$记为$n$步转移概率$P^n_{ij}$的矩阵，则不难根据C-K方程得出

不可约性

状态可达：若对某个$n\geq 0$有$P_{ij}^n>0$，则称状态$j$是从状态$i$可达的

互相可达的两个状态$i,j$称为互通的，记为$i\leftrightarrow j$，其满足以下几个性质

  • 对状态空间中一切状态$i$，有$i \leftrightarrow i$
  • 若$i\leftrightarrow j$，则$j\leftrightarrow i$
  • 若$i\leftrightarrow j$且$j\leftrightarrow k$，则$i\leftrightarrow k$

不可约性：根据两个状态是否互通可以对马尔可夫链的状态空间划分等价类（即互通的两个状态在同一等价类），若马尔可夫链只有一个等价类，则称其为不可约的

通俗的说，不可约的马尔可夫链中任意两个状态互相可达

常返态与暂态

记$f_i$表示开始在状态$i$的过程未来再次进入状态$i$的概率，则有如下定义

常返态：若$f_i=1$，则称状态$i$为循环态(Recurrent State)或常返态
瞬态：若$f_i<1$，则称为瞬态(Transient State)或暂态

常返态和暂态的判定有如下定理

对于状态$i$，若$\sum{n=1}^{\infty}P{ii}^n=\infty$，则为常返态，若$\sum{n=1}^{\infty}P{ii}^n<\infty$，则为暂态

简单证明：

对于开始在状态$i$的过程，若状态$i$是常返态，那么再次进入状态$i$的次数为无穷
若状态$i$是暂态，那么恰好再次进入状态$i$ $n$次的概率为$f_i^{n-1}(1-f_i)$，即次数服从几何分布，期望为$\frac{1}{1-f_i}$

因此状态$i$是常返态当且仅当开始在状态$i$的过程处于状态$i$的期望次数是无穷的

令$In=\begin{cases}1, \quad X_n=i\ 0, \quad X_n\neq i\end{cases}$，则$\sum{n=0}^{\infty}I_n$表示过程处于状态$i$的次数

得证

根据这个定理可以有如下推论

若状态$i$是常返态，且$i\leftrightarrow j$，则状态$j$也是常返态

根据这个推论，显然若状态$i$是暂态，则状态$j$也是暂态，进一步地我们可以得出

  • 有限状态马尔可夫链不可能都是暂态
  • 有限不可约马尔可夫链的状态都是常返态

若状态$j$是常返的，我们记$m_j$表示从$j$开始的马尔可夫链再次返回$j$的期望转移次数，则常返态又分为

正常返：若$m_j<\infty$，则称状态$j$是正常返的
零常返：若$m_j=\infty$，则称状态$j$是零常返的

周期性与遍历性

周期性：若马尔可夫链中状态$i$是正常返的，且只能在$d>1$的倍数步回访状态$i$，则称状态$i$为周期的
遍历性：若马尔可夫链中状态$i$是正常返的且非周期，则称状态$i$具有遍历性

若马尔可夫链是不可约的，且某个状态是遍历的，则马尔可夫链所有状态都是遍历的，称其为遍历链

平稳分布与极限分布

平稳分布：指马尔可夫链在长时间内处于各个状态$j$的概率分布
极限分布：若时间趋于无穷时，马尔可夫链中各个状态的出现概率逐渐收敛于某一分布，则称为极限分布

我们可以用几个例子来区别这两个概念

阶层迁移模型：假设社会分为三个阶层，并将一个家庭中各代的阶层转移视为马尔可夫链，即一个孩子的阶层只依赖于其父母的阶层。转移的概率由矩阵$P$给出，例如如下的$P$表示一个中层家庭的下一代分别以0.05、0.7、0.25的概率成为高阶层、中层阶层、低阶层，其余类似

当转移足够多代之后，我们发现分布发生了收敛，即

这时$\pi_0=0.07,\pi_1=0.62,\pi_2=0.31$就是同时是平稳分布与平稳分布
它的含义是：长期来看，社会中分别有7%、62%、31%的人处于高阶层、中间阶层、低阶层

我们再看另一个模型：假设马尔可夫链只有两个状态，且$P{0,1}=P{1,0}=1$，即过程不断在状态0、1间跳动
显然状态0和1的平稳概率分布是$\pi_0=\pi_1=\frac{1}{2}$，但$P^n$并不收敛，即极限概率分布不存在

根据这两个例子，我们再来总结平稳分布和极限分布两个概念

平稳分布：若马尔可夫链的状态空间存在概率分布$\pi$满足如下方程组

则称$\pi$为马尔可夫链的平稳分布，进一步的，$\pi$是平稳分布的充要条件是$\pi$是该方程组的解

极限分布：若马尔可夫链的状态空间存在概率分布$\pi$满足

也即$\lim_{n\to \infty}P^n$收敛，则称$\pi$为马尔可夫链的极限分布，显然极限分布与初始分布无关

马尔可夫链的平稳分布可能唯一或无穷或不存在，例如下面的转移矩阵

可解得平稳分布满足$\pi_1+\pi_3=1,\pi_2=0$，显然有无穷多个解

遍历定理：若马尔可夫链是不可约的且正常返的，则方程$\mathbf{\pi}=\mathbf{\pi P}$存在唯一解，也即存在唯一的平稳分布。进一步的，若马尔可夫链是不可约的且遍历的，则极限分布总是存在，且与平稳分布相同

根据遍历定理可以得到推论：若方程$\mathbf{\pi}=\mathbf{\pi P}$无解，则马尔可夫链是暂态的或零常返的，此时一切$\pi_j=0$

随机游走模型

若马尔可夫链的状态空间由整数集${0,\pm1,\pm2,…}$组成，且满足

则称其为一维随机游走(Random Walk)，其中$0<p<1$，若$p=\frac{1}{2}$，则称为一维对称随机游走

一维随机游走可以想象成一个人在直线上行走，在每一时刻他以概率$p$向右走一步，或以概率$1-p$向左走一步

根据类似定义随机游走还可以很容易地拓展到更多维

显然随机游走模型是不可约的马尔可夫链，因此其状态要么全是常返态，要么全是暂态

可以证明，一维和二维的对称随机游走都是常返的，而更高维则不是

随机游走模型的应用非常广泛，例如物理学中布朗运动和扩散过程的简化模型、图像分割的随机游走分割算法、搜索引擎的PageRank算法等等

时间可逆的马尔可夫链

考虑一个具有转移概率$P_{ij}$和平稳概率$\pi_i$的平稳的遍历马尔可夫链，其中平稳指已经过长时间运行

我们沿时间逆向考察这个过程，即考察状态序列$Xn,X{n-1},X_{n-2},…$

该逆向过程仍是马尔可夫链，因为独立性是对称的，即若A独立于B，则B独立于A，所以逆向过程显然满足$X{m-1}$独立于$X{m+1},X_{m+2},…$，只依赖于$X_m$

记该逆向马尔可夫链的转移概率为$Q_{ij}$，则有

若对任意$i,j$均有$Q{ij}=P{ij}$，即$\pijP{ji}=\piiP{ij}$，则称该马尔可夫链为时间可逆的，该方程称为细致平稳方程

满足细致平稳方程$xjP{ji}=xiP{ij}$的解就是马尔可夫链的平稳分布，即解$x_i=\pi_i$，因为该方程对$i$求和可得

即平稳分布的定义式。这说明可逆马尔可夫链一定有唯一的平稳分布