马尔可夫与平稳分布

1. 前置

• 随机过程

2. 定义

设 $(\Omega ,\mathcal{F},P)$ 为概率空间，$(E,\mathcal{E})$ 为状态空间（可测空间），$T$ 为全序集（通常代表时间参数集，如 ${\mathbb{R}}_{+}$ 或 $\mathbb{N}$）。

若对任意的 $t\in T$，$X_t$ 均为从 $(\Omega ,\mathcal{F})$ 到 $(E,\mathcal{E})$ 的随机变量，则称映射族 $X=\{X_t:t\in T\}$ 为随机过程（Stochastic Process）。

• 对任意 $t\in T$，定义由该过程在 $t$ 时刻及之前所生成的 $\sigma$-代数（称为自然信息流）为：
  ${\mathcal{F}}_t^X:=\sigma (X_s:s\in T,s\le t)\subseteq \mathcal{F}$

• 若随机过程 $\{X_t:t\in T\}$ 满足：对任意的 $s,t\in T$ 且 $s<t$，以及任意的 $\mathcal{E}$-可测有界函数 $f:E\to \mathbb{R}$，下述条件期望等式均成立：
  $E[f(X_t)\mid {\mathcal{F}}_s^X]=E[f(X_t)\mid X_s]\text{P-a.s.}$
  则称 $\{X_t:t\in T\}$ 为马尔可夫过程（Markov Process）。
  特别地，若考虑状态的测度分布，上述定义等价于：对任意的 $s,t\in T(s<t)$ 以及任意的可测集 $B\in \mathcal{E}$，均有：
  $P(X_t\in B\mid {\mathcal{F}}_s^X)=P(X_t\in B\mid X_s)\text{P-a.s.}$

• 当指标集（时间）退化为离散时间集 $T=\mathbb{N}=\{0,1,2,\dots \}$ 马尔可夫过程特化为离散时间马尔可夫链（DTMC）。
• 当状态空间 $E$ 为有限集（不妨设 $E=\{1,2,\dots ,K\}$，此时 $\mathcal{E}$ 自然为其幂集 $\mathcal{P}(E)$）, DTMC 特化为有限状态马尔可夫链（Finite-State DTMC, FSDTMC）。
• 称一个DTMC满足时齐性（Time-Homogeneity），即系统的状态转移规律不随时间的推移而改变，若存在一个矩阵 $Q=(Q_{ij}{)}_{K\times K}$，使得对任意的 $n\in \mathbb{N}$ 以及任意状态 $i,j\in E$，只要 $P(X_n=i)>0$，均满足：
  $P(X_{n+1}=j\mid X_n=i)=P(X_1=j\mid X_0=i):=Q_{ij}$
  矩阵 $Q$ 称为该链的单步转移概率矩阵（One-Step Transition Probability Matrix）。矩阵 $Q$ 必须是一个行随机矩阵（Row Stochastic Matrix），即满足以下两个性质：
  1. 非负性：$Q_{ij}\ge 0,\forall i,j\in E$ （概率非负）
  2. 行和规一性：${\sum }_{j=1}^K{Q}_{ij}=1,\forall i\in E$, 即 $Q1=1$

默认所有向量均为列向量；$1=(1,\dots ,1{)}^{\top }\in {\mathbb{R}}^K$。

下面只讨论FSDTMC

设一个FSDTMC的状态空间为 $E=\{1,2,\dots ,K\}$，其单步转移概率矩阵为 $Q=(Q_{ij}{)}_{K\times K}$。若存在一个定义在 $E$ 上的概率分布（表现为一个列向量 $\pi =({\pi }_1,{\pi }_2,\dots ,{\pi }_K{)}^{\top }$），满足以下两个条件：

• 概率规范性：${\pi }_i\ge 0(\forall i\in E)$ 且 $1^{\top }\pi =1$
• 平稳性方程（Stationary Equation）：$Q^{\top }\pi =\pi$

则称 $\pi$ 为该马尔可夫链的平稳分布。

• 如果状态空间中的任意两个状态 $i,j$ 都可以互相到达（即对任意 $i,j\in E$，存在 $n\ge 1$ 使得 $(Q^n{)}_{ij}>0$），则称该链是不可约的。
• 设 $X=\{X_n{\}}_{n\in \mathbb{N}}$ 为一个 FSDTMC，转移矩阵为 $Q$。

对于状态 $i\in E$，定义其周期为：

$$d(i)=\gcd \{n\ge 1:(Q^n{)}_{ii}>0\}$$

即所有“从状态 $i$ 出发并恰好在 $n$ 步后回到 $i$”的可能步数的最大公约数。

• 若 $d(i)=1$，则称状态 $i$ 为非周期。
• 若 $d(i)>1$，则称状态 $i$ 为周期性状态。

对于不可约马尔可夫链，所有状态具有相同的周期，因此可以定义整个链的周期：

$$d:=d(i)(\forall i\in E)$$

若 $d=1$，则称该链为非周期链。

3. 性质

1. FSDTMC的平稳分布存在
2. (未证明)若FSDTMC是不可约的，则其平稳分布唯一
3. (未证明)若 FSDTMC 既是不可约的，又是非周期的（每个状态的周期均为 1）,则无论初始概率分布 ${\nu }_0$ 是什么，系统在长期的演化后都必然收敛到唯一的平稳分布 $\pi$：
   ${\lim }_{n\to \infty }(Q^{\top }{)}^n{\nu }_0=\pi$

4. 证明

4.1. FSDTMC的平稳分布存在

基于 $Q$ 的左特征谱。设有限状态时齐马尔可夫链的单步转移概率矩阵为 $Q\in {\mathbb{R}}^{K\times K}$。由于 $Q$ 为行随机矩阵，其满足非负性 $Q\ge 0$ 以及行和规一性 $Q1=1$。

第一步：证明 $\lambda =1$ 是 $Q^{\top }$ 的特征值

根据线性代数性质，矩阵与其转置矩阵拥有完全相同的特征多项式，即 $\det (\lambda \mathbf{I}-Q)=\det (\lambda \mathbf{I}-Q^{\top })$，故 $Q$ 与 $Q^{\top }$ 的特征值集合完全相同。由行和规一性条件：
$Q1=1\cdot 1$
可知 $1$ 是 $Q$ 对应于特征值 $\lambda =1$ 的一个右特征向量。因此，$\lambda =1$ 亦必然是 $Q^{\top }$ 的特征值。即存在非零列向量 $\mathbf{v}\in {\mathbb{R}}^K$ 满足：

$Q^{\top }\mathbf{v}=\mathbf{v}$

第二步：构造全非负的特征向量

对于任意列向量 $\mathbf{x}\in {\mathbb{R}}^K$，定义其绝对值向量为 $|\mathbf{x}|:={\left(\begin{array}{c}|x_1|,|x_2|,\dots ,|x_K|\end{array}\right)}^{\top }$。对于 $Q^{\top }\mathbf{v}=\mathbf{v}$ 的第 $j$ 个分量，由三角不等式及 $Q$ 的非负性 ($Q_{ij}=|Q_{ij}|$) 可得：

$|v_j|=\left|{\sum }_{i=1}^K{Q}_{ij}{v}_i\right|\le {\sum }_{i=1}^K{Q}_{ij}|v_i|$

将其重写为矩阵形式不等式：

$|\mathbf{v}|\le Q^{\top }|\mathbf{v}|$

保持不等号方向对其两边同时左乘转置向量 $1^{\top }$（等价于对向量各分量求和）：

$1^{\top }|\mathbf{v}|\le 1^{\top }\left(Q^{\top }|\mathbf{v}|\right)=\left(1^{\top }{Q}^{\top }\right)|\mathbf{v}|$

利用行随机矩阵性质 $1^{\top }{Q}^{\top }=(Q1{)}^{\top }=1^{\top }$，上式右侧化简为 $1^{\top }|\mathbf{v}|$。由此得到：

$1^{\top }|\mathbf{v}|\le 1^{\top }|\mathbf{v}|$

这要求原本的分量不等式必须全部严格取到等号，即：

$|\mathbf{v}|=Q^{\top }|\mathbf{v}|$

此时，我们直接令 ${\mathbf{v}}^{+}=|\mathbf{v}|$。显然 ${\mathbf{v}}^{+}$ 是一个非零（因为 $\mathbf{v}\ne 0$）、各项元素均非负的列向量，且由上式可知它满足：

$Q^{\top }{\mathbf{v}}^{+}={\mathbf{v}}^{+}$

第三步：概率规范化

由于 ${\mathbf{v}}^{+}\ge 0$ 且 ${\mathbf{v}}^{+}\ne 0$，其分量之和（${\ell }_1$-范数）必定为正实数：
$S=1^{\top }{\mathbf{v}}^{+}={\sum }_{i=1}^K{v}_i^{+}>0$

此时，我们定义列向量 $\pi$ 为：
$\pi =\frac{1}{S}{\mathbf{v}}^{+}$

由构造过程易证 $\pi$ 满足平稳分布的全部定义条件：

非负性：${\pi }_i=\frac{v_i^{+}}{S}\ge 0,\forall i\in \{1,2,\dots ,K\}$

规范性：$1^{\top }\pi =\frac{1}{S}{1}^{\top }{\mathbf{v}}^{+}=\frac{S}{S}=1$

平稳性方程：$Q^{\top }\pi =Q^{\top }\left(\frac{1}{S}{\mathbf{v}}^{+}\right)=\frac{1}{S}{Q}^{\top }{\mathbf{v}}^{+}=\frac{1}{S}{\mathbf{v}}^{+}=\pi$ $\square$