04：Markov状态分类与渐进Markov链

Markov状态分类与渐进Markov链

1 状态分类

1.1 可到达

对于两个状态$i,j$，如果存在正整数$n\geq 1$，使得$P^{(n)}_{ij}>0$，则称从状态$i$可到达状态$j$。也就是说Markov链通过n步到达另一个状态的概率大于0。记作$i\rightarrow j$。

反之，如果对于$\forall n\geq 1$，都有$P_{ij}^{(n)}=0$，则从状态$i$不可到达状态$j$，记作$i\nrightarrow j$。

可到达可以传递。如果$i\rightarrow k$, $k\rightarrow j$，则$i\rightarrow j$

1.2 相通

如果状态$i$可到达状态$j$，状态$j$也能到达状态$i$，那么两个状态相通，记作$i\leftrightarrow j$。

状态相通具有传递性，如果$i\leftrightarrow k$, $k\leftrightarrow j$，则$i\leftrightarrow j$。

1.3 类与闭集

因为相通可以传递，所以只要几个状态相通，那么他们就全部两两相通。这些互相相通的状态我们将其归纳为一个类。此时状态空间就被划分为不同的类。同一类里面的状态都是相通的，不同类之间状态是不相通的。

取集合C是状态空间S的一个子集，如果C内任何一个状态都不能到达C以外的任何状态，则称C是一个闭集。所以，吸收态可以看作是只有一个状态构成的闭集。

2 可约与周期

Markov链的闭集只有整个状态空间S，就称其不可约。否则可约。这个定义等价于整个Markov链只有一个类，此时整个Markov链的所有状态都是相通的，那么这个时候闭集就只有整个状态空间S。

考虑一个这样的Markov链

graph LR
A[1]
B[2]
A --1--->B
B--1--->A

Markov链在运行过程中在状态1和状态2之间来回周期震荡。且满足

$$P_{11}^{(n)}= \begin{cases} 1\quad n是偶数 \\ 0\quad n是奇数 \end{cases}$$

因为Markov链总要用偶数次步数才能返回到原来那个状态。

一般来讲，用$d$代表步数，如果一个Markov链的状态，必须通过$d$的整数倍步($d>1$)才能返回原来的状态(上述例子中$d=2$)，那么就说这个状态是周期的。这可以看作Markov链在运行过程中总是经过某个步数周期后返回到原来那儿继续运行，周而复始。

对于Markov链，选其中一个状态$i$，记运行步数为$n$，我们要找到从$i$出发返回到原来状态$i$的步数$n$，由于Markov链可以存在多条路径返回，我们可构造集合$\{n;n\geq 1,P_{ii}^{(n)}>0\}$，如果集合非空，则找到这个步数集合里面的最大公约数，这个数就是这个状态$i$的周期，记为$d_i$。当$d_i=1$时称为无周期。

对于前面的例子，返回状态1的步数为$\{2, 4, 6,\dots\}$，最大公约数是2，所以周期是2。如果现在有个状态$i$，使得$P_{ii}^{(2)}>0$, $P_{ii}^{(3)}>0$，也就是可通过两步或三步返回，那么它就不是都通过$d$的整数倍步返回，2和3的最大公约数是1，那么这个状态就是无周期的。

同一类中各状态周期都是相同的

现在使用数学方法表达之前的定义。

• C是闭集，等价于$\forall i\in C$. $j\notin C$，有$P_{ij}^{(n)}=0$。即内部状态任意步数下都不可能转移到外部状态。
• C是闭集，等价于$\forall i\in C$, $\sum\limits_{j\in C}P_{ij}=1$，即只可能转移到内部状态。
• $i$为吸收态，等价于$P_{ii}=1$，一步转移只可能转移到自己。
• Markov链不可约，等价于任意两个状态相通，也等价于只有一个类

3 到达时间问题

3.1 首达时间（步数）

我们定义从状态$i$出发首次到达状态$j$的时间为首达时间。在数学上，可以这样表示

$$T_{ij}\overset{\rm def}{=}\min \{n:X_0=i,X_n=j,n\geq 1\}$$

这意味着我们找到了所有从$i$到$j$可能使用的步数，并找到所用的最小的步数，就是首次到达使用的步数。

显然，首达时间是一个随机变量。

3.2 经n步首达概率

我们定义从状态$i$出发，经n步首次到达状态$j$的概率是n步首达概率。在数学上表达为

$$f_{ij}^{(n)} \overset{\rm def}{=}P\{T_{ij}=n|X_0=i\}$$

也就是从0时刻开始，自状态$i$出发的条件下，经n步首次到达$j$的概率。

概率的计算是显然的

$$f_{ij}^{(n)}=P\{X_n=j, X_{n-1}\neq j, X_{n-2}\neq j,\dots, X_1\neq j|X_0=i\}$$

即从i开始，中间步数都没有进入状态$j$，刚好在n步时到达$j$

特殊情况下，

$$f_{ij}^{(1)}=P_{ij}=P\{X_1=j|X_0=i\}$$

也就是一步就从$i$转移到$j$了

$$f_{ij}^{(\infty)}=P\{X_m\neq j,\forall m\geq 1|X_0=i\}$$

也就是说0时刻从状态$i$开始，任意之后的步数都不会进入$j$，这也是为什么无穷步到达中$n=\infty$。

3.3 平均到达时间与平均返回时间

我们定义从状态$i$出发，到达状态$j$所需要的平均步数是平均到达时间，记为$\mu_{ij}$，用数学表达是

$$\mu_{ij}\overset{\rm def}{=}E\{T_{ij}|X_0=i\}$$

即利用n步首达概率来求期望，平均所有可能的首次到达时间。具体的计算可考虑离散随机变量的期望，

$$\sum_{n=1}^{\infty}nf_{ij}^{(n)}$$

如果$i=j$，那么就以为着是从$i$出发又返回到了$i$，这时$\mu_{ii}\overset{\rm def}{=}\mu_i$是状态$i$的平均返回时间

3.4 迟早到达概率

从状态$i$出发经过有限步转移后迟早到达状态$j$的概率称作迟早到达概率，数学形式为

$$f_{ij}=\sum_{1\leq n<\infty} f_{ij}^{(n)}$$

也就是对所有可能的首次到达概率进行求和，这就会产出迟早会到达的概率。

注意到这也等同于

$$f_{ij}=P\{T_{ij}<\infty\}$$

这意味着我们不需要无穷多步数来从$i$到达$j$，那么从语义上也就是迟早会从$i$到达$j$。

另外，概率$P\{T_{ij}=\infty\}\overset{\rm def}{=}f_{ij}^{(\infty)}=1-f_{ij}$,，它表示从$i$出发，不能经过有限次转移到达$j$的概率。

同样的，当$i=j$，即$f_{ii}$，它表达了从状态$i$出发，迟早会返回$i$的概率。那么$1-f_{ii}$就是从$i$出发，再也不返回$i$的概率。

一些性质与关系

• 对于$\forall i,j\in S$, $0\leq f_{ij}^{(n)}\leq P_{ij}^{(n)}\leq f_{ij}\leq 1$, 这个不等式首先告诉我们概率肯定是大于0小于1的，其次从$i$到$j$的n步转移概率大于其n步首次到达概率，而迟早到达的概率又大于n步转移概率。这是因为n步首次到达的概率实际上是n步转移概率的子集，因为我们只取了n步转移中首次到达的概率。

• 对于$\forall i,j\in S$，$f_{ij}>0\Leftrightarrow i\rightarrow j$，这是显然的，既然迟早从$i$到达$j$的概率大于0，那么$i$就能到达$j$

• 对于$\forall i,j\in S$, $f_{ij}>0, f_{ji}>0\Leftrightarrow i\leftrightarrow j$。能从$i$到$j$，也能从$j$到$i$，这就符合相通的定义

• 对于$\forall i,j\in S$, 设步数$1\leq n<\infty$，有

  $$P_{ij}^{(n)}=\sum_{l=1}^nf_{ij}^{(l)}P_{jj}^{(n-l)}$$

  求和项$f_{ij}^{(l)}P_{jj}^{(n-l)}$实际上是经$l$步首次从$i$到达$j$的概率乘以从$j$出发经$n-l$步回到$j$的概率。这代表着Markov链先首次从$i$到达了$j$，然后剩余的步数从$j$出发，最终又返回了$j$，那么实际上就是从$i$出发到达了$j$。而求和实际上就是在规定使用$n$步从$i$到$j$的情况下，考虑所有首次到达的概率，以及到了状态$j$后，剩余步数从$j$出发回到$j$的概率(因为我们要保证最终是从$i$出发到$j$)。

4 状态定义

接下来使用状态的性质来进行定义。

• 如果一个状态$i$，它一定会，或者说最终会回到自己，即$f_{ii}=1$，那么状态$i$就被称作是常返态(Recurrent)
• 如果一个状态$i$，可能不会回到自己，即$f_{ii}<1$，那么状态$i$就被称作是非常返态(Transient)。这意味着有概率$1-f_{ii}$会从$i$出发后再也回不来了。
• 对于一个常返态$i$，如果其平均可以通过有限步数返回，即$\mu_i<+\infty$，则称状态$i$是正常返(Positive Recurrent)的。如果其平均上需要无穷的步数返回，即$\mu_i=\infty$，那么状态$i$是零常返(Null Recurrent)的
• 如果一个状态非周期，且是正常返的，那么它被称作遍历态.

4.1 性质

（1）如果两个状态相通，例如$i\leftrightarrow j$，那么这两个状态将具有相同特性。这些特性包括常返，非常返，正常返，零常返，周期和非周期。如果是周期的它们的周期还是相同的。

这也被称作类的特性。相通即意味着同一类，那么相通特性相通也就意味着同一类的特性相同。

（2）状态判别

1. 对于状态$i$, 如果$\sum\limits_{n=0}^{\infty}P_{ii}^{(n)}=\frac{1}{1-f_{ii}}=\infty$, 那么状态$i$是常返态，此时$f_{ii}=1$
2. 对于状态$i$, 如果$\sum\limits_{n=0}^{\infty}P_{ii}^{(n)}=\frac{1}{1-f_{ii}}<\infty$, 那么状态$i$是非常返态，此时$f_{ii}<1$

（3）对于一个有限状态的Markov链，以下命题成立

1. 没有零常返状态
2. 必有正常返状态
3. 不可约有限Markov链只有正常返的状态
4. 一个不可约，非周期，有限状态的Markov链一定是遍历的(运行时可以历经所有状态)
5. 所有非常返状态组成的集合不可能是闭集。
6. 状态空间可以分解为$S=D\cup C_1\cup C_2\cup \cdots \cup C_k$, 其中每个$C_n$, $n\in [1, k]$都是正常返状态组成的有限不可约闭集，$D$是非常返态的集合。也就是说，一个状态空间可以分解成一个非常返态集合并上多个正常返态集合。

5 渐进分析

当Markov链长期运行，或者说其转移步数达到一个很大的数值，Markov链会展现出一些独特的性质，这些性质称作长时运行性质(Long-Run). 当运行时间特别长，达到无穷的时候，Markov链展现出的性质又叫做极限性质(Limiting)。渐进分析则探究Markov链的长时运行性质和极限性质。

5.1 平稳分布

当Markov链长期运行的时候，我们定义$\pi_j$是Markov链在状态$j$的时间占总运行时间的比例。例如100次运行中，20次在状态0，那么$\pi_0=1/5$

现在，我们给出它的一个等价的说法，$\pi_j$也是从状态$j$出发，向其他状态转移的次数的比例。例如100次转移当中，20次都是从状态$j$出发的。

从第一个定义我们知道它是总运行时间中，在某个状态$j$的时间的比例。而Markov链总要向下一个状态转移，那么在状态$j$的次数(时间)，也就成为了从状态$j$向其他状态转移的次数。

为了避免混淆，我们用$\pi_i$来表示从状态$i$出发，向其它状态转移的次数的比例。现在，$\pi_iP_{ij}$就表示了长时运行中，从状态$i$出发，转移到状态$j$的次数的比例。

那么以下的关系式就成立

$$\pi_j = \sum_i \pi_iP_{ij}$$

将所有可能的出发的状态相加，就得到了所有状态到状态$j$的次数的比例，也即在长时运行中Markov链在状态$j$的次数的比例。

现在我们把所有状态的$\pi_j$写成一个向量，$\boldsymbol{\pi}=[\pi_0,\pi_1,\dots]$

注意到

$$\begin{aligned} \pi_j &= \pi_0P_{0j}+\pi_1P_{1j}+\cdots \\ &=[\pi_0, \pi_1,\dots]\times \begin{bmatrix} P_{0j} \\ P_{1j} \\ \vdots \end{bmatrix}\\ &=\boldsymbol{\pi}\times \begin{bmatrix} P_{0j} \\ P_{1j} \\ \vdots \end{bmatrix} \end{aligned}$$

如果把左边的所有$\pi_j$也写成向量，就有

$$[\pi_0,\pi_1,\dots] = \boldsymbol{\pi}\times \begin{bmatrix} P_{00} & P_{01} & \cdots\\ P_{10} & P_{11} & \cdots \\ \vdots & \vdots \end{bmatrix}$$

即

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

我们就有了一个矩阵表达形式。现在我们看看向量$\boldsymbol{\pi}$，它的每一个元素代表了长时运行中在某个状态的时间的比例。这种比例类似于频数，当运行时间足够长，它就反映着处在某个状态的概率。向量$\boldsymbol{\pi}$因此被称为Markov链的平稳分布。

由关系式$\boldsymbol{\pi}=\boldsymbol{\pi}\times P$,我们可以递推地得到

$$\boldsymbol{\pi}=\boldsymbol{\pi}\times P=\boldsymbol{\pi}\times P\times P=\boldsymbol{\pi}\times P^2=\cdots=\boldsymbol{\pi}\times P^n$$

对于任意一个状态$j$，应该有

$$\sum_j \pi_j=1$$

对于任意一个状态$j$，还满足

$$\pi_j = \frac{1}{\mu_j}$$

其中$\mu_j$是状态$j$的平均返回时间

5.2 极限性质

假设Markov链的一步转移矩阵是

$$P= \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$$

可以得到

$$P^4= \begin{bmatrix} 0.5749 & 0.4251 \\ 0.5668 & 0.4332 \end{bmatrix}$$

如果再算四次幂

$$P^8= \begin{bmatrix} 0.571 & 0.429 \\ 0.571 & 0.429 \end{bmatrix}$$

随着转移次数增多，我们发现8次转移的概率和4次转移的概率几乎相同，所以概率正在发生收敛。同时，同列的概率是相同的，与行无关。这意味着转移概率$P_{ij}^n$在$n\rightarrow \infty$时收敛到某个值，并且与$i$无关，即与出发的状态无关。

这就是Markov链的极限性质，当步数n足够大，$P_{ij}^n$与初始状态$i$无关，成为了绝对概率分布。

如果Markov链有限，不可约，遍历，那么当n足够大时，还满足

$$\lim\limits_{n\rightarrow \infty} P\{X_n=j\}=P_{j}^{(\infty)}=\pi_j$$

即绝对概率分布的极限就是平稳分布。

6 吸收问题

现在考虑从一个状态$i$出发进入某个状态闭集$C_k$的概率$P\{C_k|i\}$

6.1 吸收概率

Markov链从一个状态$i$出发，在运行过程中进入某个闭集状态$C_k$被吸收的概率。

如果出发时的状态$i$本身就在$C_k$里面，那么$P\{C_k|i\}=1$，如果出发时的状态$i$在另一个闭集$C_m,m\neq k$，那么$P\{C_k|i\}=0$

现在考虑从非闭集$D$出发，闭集D满足$S=D\cup C_k$,由C-K方程，取一个中间状态$j$，由路径$i\rightarrow j\rightarrow k$有

$$P\{C_k|i\}=\sum_{j\in S}P_{ij}P\{C_k|j\}$$

拆开集合$S$, 得到

$$\begin{aligned} P\{C_k|i\}&=\sum_{j\in S}P_{ij}P\{C_k|j\}\\ &=\sum_{j\in D}P_{ij}P\{C_k|j\}+\sum_{j\in C_k}P_{ij}P\{C_k|j\}\\ \end{aligned}$$

注意到在$j\in C_k$里，$P\{C_k|j\}=1$, 则有

$$\begin{aligned} P\{C_k|i\}&=\sum_{j\in S}P_{ij}P\{C_k|j\}\\ &=\sum_{j\in D}P_{ij}P\{C_k|j\}+\sum_{j\in C_k}P_{ij}P\{C_k|j\}\\ &=\sum_{j\in D}P_{ij}P\{C_k|j\}+\sum_{j\in C_k}P_{ij} \end{aligned}$$

移动右边第一项得到

$$P\{C_k|i\}-\sum_{j\in D}P_{ij}P\{C_k|j\}=\sum_{j\in C_k}P_{ij}$$

通过解上述求出的线性方程组，可以得到概率$P\{C_k|i\}$，称这个概率是$C_k$的吸收概率。

6.2 吸收时间

Markov链从状态$i\in S$出发，进入一个闭集，或者说一个常返态类(常返态类一定是个闭集)经过的时间$T$称为吸收时间。

概率$P\{T=n|i\}$表示从状态$i$出发，经过$n$步刚好进入常返态类的概率。如果$P\{T<\infty|i\}$表示从$i$出发迟早进入常返态类的概率，那么其实可以对所有$n$步进入求和，有如下关系

$$\lim\limits_{N\rightarrow \infty}\sum_{n=0}^N P\{T=n|i\}=P\{T<\infty |i\}$$

此处极限是因为$T$不能直接等于$\infty$.

6.3 平均吸收时间

从某个状态$i\in D$出发，$D$是非闭集(非常返态)，进入闭集(常返态)所需的平均吸收时间也是很重要的。

同样，由C-K方程，考虑一个经$n+1$步刚好从$i$进入闭集的概率

$$P\{T=n+1|i\}=\sum_{j\in S}P_{ij}P\{T=n|j\}$$

两边同时乘以$n$并做恒等变换

$$\begin{aligned} &nP\{T=n+1|i\}=n\sum_{j\in S}P_{ij}P\{T=n|j\}\\ &(n+1)P\{T=n+1|i\}-P\{T=n+1|i\}=\sum_{j\in S}nP_{ij}P\{T=n|j\} \end{aligned}$$

注意到期望的计算是$E[x]=\sum xP(x)$，可看作概率乘变量求和。于是对上式两边同时对n求和，得到

$$\begin{aligned} &\sum_{n=0}^\infty (n+1)P\{T=n+1|i\}-\sum_{n=0}^{\infty}P\{T=n+1|i\} \\ &= \sum_{j\in S}P_{ij}\sum_{n=0}^\infty nP\{T=n|j\} \end{aligned}$$

由期望定义得到

$$E[T|i]-\sum_{n=1}^\infty P\{T=n|i\}=\sum_{j\in S}P_{ij}E[T|j]$$

如果中间状态$j$在我们要进入的闭集$C$里面，那么$E[T|j]=0$，因为我们不需要任何步数来进入闭集。

如果分解状态空间$S=D\cup C$，其中$D$是非闭集，$C$是闭集，那么方程进一步化为

$$E[T|i]-\sum_{n=1}^\infty P\{T=n|i\}=\sum_{j\in D}P_{ij}E[T|j]$$

可证明项$\sum\limits_{n=1}^\infty P\{T=n|i\}=1$, 那么

$$E[T|i]-\sum_{j\in D}E[T|j]P_{ij}=1$$

由上述方程可以计算出平均吸收时间$E[T|i]$.