马尔科夫链

• Markov Chain, MC

离散时间马尔科夫链

• Discrete-Time MC, DTMC

定义

状态空间 $S$：一个有限或者可数无限的集合，表示系统可能处于的所有状态

时间索引 $t$：离散的时间值，通常表示为 $t=0,1,2,\cdots$

随机过程 $X$：在时间 $t$ 时系统所处的状态

马尔可夫性质：系统的未来状态只依赖于当前状态，而与过去状态无关

$$P(X_{t+1}=j|X_t=i,X_{t-1}=i_{t-1},\cdots ,X_0=i_0)=P(X_{t+1}=j|X_t=i)$$

齐次性：转移概率不随时间变化

• Homogeneity

$$P(X_{t+1}=j|X_t=i)=P_{ij}$$

转移概率矩阵

大小：$\left|S\right|\times \left|S\right|$，其中 $\left|S\right|$ 是状态空间的维度

含义：元素 $P_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率

性质：

• $0\le P_{ij}\le 1$（概率的非负性）
• ${\sum }_{j\in S}{P}_{ij}=1$（每行的和为1）

n步转移概率：从状态 $i$ 经过 $n$ 步转移到状态 $j$ 的概率，记为 $P_{ij}^{\left(n\right)}$

• $P^{\left(n\right)}=P^n$
• Chapman-Kolmogorov 方程：$P_{ij}^{\left(n+m\right)}={\sum }_{k\in S}{P}_{ik}^{\left(n\right)}{P}_{kj}^{\left(m\right)}$
  • 从 $i$ 到 $j$ 经过 $n+m$ 步，可以看作先经过 $n$ 步到中间状态 $k$，再从 $k$ 经过 $m$ 步到 $j$，然后对所有可能的中间状态 $k$ 求和

初始分布和状态分布

初始分布 ${\pi }^{\left(0\right)}$：一个行向量，表示在时间 $t=0$ 时系统处于每个状态的概率

$${\pi }^{\left(0\right)}=\left({\pi }_1^{\left(0\right)},{\pi }_2^{\left(0\right)},\cdots \right)$$

• 其中 ${\pi }_i^{\left(0\right)}=P(X_0=i)$

n步之后的状态分布 ${\pi }^{\left(n\right)}$：

$${\pi }^{\left(n\right)}={\pi }^{\left(0\right)}{P}^n$$

稳态分布

• Stationary Distribution
• 平衡分布（Equilibrium Distribution）

如果一个 DTMC 是不可约 (irreducible)（任何状态都可以到达任何其他状态）和非周期 (aperiodic)（从任何状态回到自身所需的时间步长没有公约数），那么它会收敛到一个唯一的稳态分布 $\pi$，满足：

$$\pi P=\pi$$

且 ${\sum }_{i\in S}{\pi }_i=1$

例子：天气模型

假设天气只有两种状态：晴朗 (S) 和下雨 (R)。

转移概率矩阵为：

$$P=\left(\begin{array}{cc}{P}_{SS}& P_{SR}\\ P_{RS}& P_{\mathbb{R}}\end{array}\right)=\left(\begin{array}{cc}0.9& 0.1\\ 0.3& 0.7\end{array}\right)$$

这意味着：

• 如果今天晴朗，明天有 90% 的概率晴朗，10% 的概率下雨
• 如果今天下雨，明天有 30% 的概率晴朗，70% 的概率下雨

稳态分布 $\pi =\left({\pi }_S,{\pi }_R\right)$ 满足：

$$\begin{array}{rl}{\pi }_S\cdot 0.9+{\pi }_R\cdot 0.3& ={\pi }_S\\ {\pi }_S\cdot 0.3+{\pi }_R\cdot 0.7& ={\pi }_R\\ {\pi }_S+{\pi }_R& =1\end{array}$$

解方程组可得 ${\pi }_S=0.75$，${\pi }_R=0.25$。这意味着长期来看，有 75% 的时间是晴朗的，25% 的时间是下雨的。

连续时间马尔科夫链

• Continuous-Time MC, CTMC

定义

状态空间 $S$：一个有限或者可数无限的集合，表示系统可能处于的所有状态

时间索引 $t$：连续的时间值，通常为 $t\ge 0$

随机过程 $X$：在时间 $t$ 时系统所处的状态

马尔可夫性质：系统的未来状态只依赖于当前状态，而与过去状态无关

$$P(X_{t+s}=j|X_t=i,X_u\mathrm{for}u<t)=P(X_{t+s}=j|X_t=i)$$

齐次性：转移概率不随时间变化

• Homogeneity

$$P(X_{t+s}=j|X_t=i)=P_{ij}(s)$$

其中 $P_{ij}(s)$ 是从状态 $i$ 经过时间 $s$ 转移到状态 $j$ 的概率

状态停留时间

CTMC 的核心特点是系统在每个状态中停留的时间是随机的，并且服从指数分布

如果系统进入状态 $i$，它会停留一段时间 $T_i$​，其中 $T_i\sim \mathrm{Exp}({\lambda }_i)$

• ${\lambda }_i$ 时从状态 $i$ 离开的总速率（或生成速率）
• 系统离开状态 $i$ 转移到状态 $j$ 的概率为 $p_{ij}=\frac{Q_{ij}}{{\lambda }_i}$（对于 $j\ne i$）

瞬时转移速率矩阵

• Generator Matrix

大小：$\left|S\right|\times \left|S\right|$，其中 $\left|S\right|$ 是状态空间的维度

非对角元素 $Q_{ij}$（$i\ne j$）：表示从状态 $i$ 转移到状态 $j$ 的速率

• $Q_{ij}>0$
• 在极小的时间间隔 $\Delta t$ 内，从状态 $i$ 转移到状态 $j$ 的概率近似为 $Q_{ij}\Delta t$

对角线元素​ $Q_{ii}$：表示从状态 $i$ 离开的总速率的负值

• $Q_{ii}=-{\sum }_{j\ne i}{Q}_{ij}<0$
• ${\lambda }_i=-Q_{ii}$ 表示从状态 $i$ 离开的总速率

性质：${\sum }_{j\in S}{Q}_{ij}=0$（每行的和为0）

与 DTMC 的关系：可以近似认为 $P_{ij}(\Delta t)\approx {\delta }_{ij}+Q_{ij}\Delta t$，其中 ${\delta }_{ij}$ 是 Kronecker delta（当 $i=j$ 时为 1，否则为 0）

转移概率函数

$P_{ij}(t)$ 表示在时间 $t$ 从状态 $i$ 转移到状态 $j$ 的概率

Kolmogorov 微分方程：

• 向前方程（Forward Equations）：$\frac{\mathrm{d}P(t)}{\mathrm{d}t}=P(t)Q$
  • 初始条件 $P(0)=I$（单位矩阵）
• 向后方程（Backward Equations）：$\frac{\mathrm{d}P(t)}{\mathrm{d}t}=QP(t)$
  • 初始条件 $P(0)=I$

这些方程的解是：

$$P(t)=e^{Qt}=I+Qt+\frac{(Qt{)}^2}{2!}+\frac{(Qt{)}^3}{3!}+\cdots$$

这是一个矩阵指数函数

初始分布和状态分布

初始分布 $\pi (0)$：一个行向量，表示在时间 $t=0$ 时系统处于每个状态的概率

时间 $t$ 时的状态分布 $\pi (t)$：

$$\pi (t)=\pi (0)P(t)=\pi (0)e^{Qt}$$

或者通过微分方程：

$$\frac{\mathrm{d}\pi (t)}{\mathrm{d}t}=\pi (t)Q$$

稳态分布

• Stationary Distribution
• 平衡分布（Equilibrium Distribution）

如果一个 CTMC 是不可约的，那么它会收敛到一个唯一的稳态分布 $\pi$，满足：

$$\pi Q=0$$

且 ${\sum }_{i\in S}{\pi }_i=1$

例子：单服务台排队系统 (M/M/1 队列)

假设有一个服务台，顾客以泊松过程到达（到达速率 $\lambda$），服务时间服从指数分布（服务速率 $\mu$），状态 $n$ 表示系统中排队的顾客数量

• 从状态 $n$ 到状态 $n+1$（新顾客到达）的速率是 $\lambda$：$Q_{n,n+1}=\lambda$
• 从状态 $n$ 到状态 $n+1$（顾客被服务完成离开）的速率是 $\mu$：$Q_{n,n-1}=\mu$
• 从状态 $n$ 保持到状态 $n$ 的速率是 $-(\lambda +\mu )$：$Q_{n,n}=-\left(\lambda +\mu \right)$
• 从状态 $0$ 离开的速率是 $0$（没有顾客离开）：$Q_{0,0}=-\lambda$
• 其他 $Q_{ij}=0$

稳态分布 $\pi =({\pi }_0,{\pi }_1,{\pi }_2,\cdots )$ 满足 $\pi Q=0$

对于 M/M/1 队列，稳态分布是几何分布：

$${\pi }_n=(1-\rho ){\rho }^n$$

其中 $\rho =\frac{\lambda }{\mu }$ 是系统利用率

离散与连续的联系

均质化：

• Uniformization

CTMC 可以通过均匀化技术转化为 DTMC

选择一个足够大的速率 $v$（大于所有状态的离开速率 $\lambda$），然后构造一个 DTMC，在每个时间步，系统要么保持当前状态，要么以速率 $Q_{ij}$ 转移到状态 $j$（或者以概率 $1-\frac{{\lambda }_i}{v}$ 保持在当前状态）

这个 DTMC 的一步转移概率矩阵 $P^{\prime }$ 为：

$$P^{\prime }=\{\begin{array}{ll}\frac{Q_{ij}}{v}& \mathrm{if}i\ne j\\ 1+\frac{Q_{ii}}{v}& \mathrm{if}i=j\end{array}$$

然后，CTMC 的 $P(t)$ 可以表示为：

$$P(t)=\sum _{k=0}^{\infty }{e}^{-vt}\frac{(vt{)}^k}{k!}(P^{\prime }{)}^k$$

这表明 CTMC 的状态在时间 $t$ 的分布可以看作是 DTMC 经过泊松分布次数的步骤后的状态分布

极限关系：

DTMC 可以看作是 CTMC 在非常小的时间间隔 $\Delta t$ 内的近似

如果 $P_{ij}$ 是 DTMC 的转移概率，那么可以定义 $Q_{ij}=\frac{P_{ij}-{\delta }_{ij}}{\Delta t}$

当 $\Delta t\to 0$ 时，这个 $Q$ 矩阵就趋近于 CTMC 的瞬时转移速率矩阵

隐马尔可夫模型

蒙特卡洛马尔可夫链