马尔可夫链（Markov Chain）

一、核心定义与马尔可夫性（无记忆性）

1. 基本概念

马尔可夫链是离散时间、离散状态的马尔可夫随机过程，随机变量序列 $X_0,X_1,X_2,\dots,X_n$ ，每个 $X_n$ 代表第 $n$ 时刻系统所处状态。

2. 核心性质：马尔可夫无记忆性

未来状态只由当前状态决定，和过去所有历史状态无关：

P(X_{n+1}=j \mid X_n=i,\,X_{n-1},\dots,X_0) = P(X_{n+1}=j \mid X_n=i)

通俗理解：已知现在，过去不影响将来。

二、三大核心组成要素

状态空间 $S$ 系统所有可能取值的有限/可数集合， $S=\{s_1,s_2,\dots,s_k\}$ 。例：软件可靠性两状态 $S=\{正常,失效\}$ 。
一步转移概率 $p_{ij}$ 从状态 $i$ 经过1步到达状态 $j$ 的概率：
$p_{ij}=P(X_{n+1}=j \mid X_n=i)$ 满足归一性： $\displaystyle \sum_{j\in S} p_{ij}=1$ 。
转移概率矩阵 $\boldsymbol{P}$ 把所有 $p_{ij}$ 按行列组成方阵，行=当前状态，列=下一状态：
$\boldsymbol{P}= \begin{bmatrix} p_{11} & p_{12} & \dots & p_{1k}\\ p_{21} & p_{22} & \dots & p_{2k}\\ \vdots & \vdots & \ddots & \vdots\\ p_{k1} & p_{k2} & \dots & p_{kk} \end{bmatrix}$

三、关键衍生概念

1. 初始分布

$\boldsymbol{\pi}_0 = [\pi_{01},\pi_{02},\dots,\pi_{0k}]$ ，表示第0时刻系统处于各状态的概率。

2. n步转移矩阵

$\boldsymbol{P}^{(n)}=\boldsymbol{P}^n$ ，代表经过 $n$ 步从i到j的概率。 n时刻状态分布： $\boldsymbol{\pi}_n = \boldsymbol{\pi}_0 \cdot \boldsymbol{P}^n$ 。

3. 齐次马尔可夫链

转移概率 $p_{ij}$ 不随时间 $n$ 变化（绝大多数工程使用齐次链）。

四、状态分类（齐次有限马尔可夫链）

常返态：离开后一定会再次返回；
瞬态（非常返态）：离开后有概率永不回来；
吸收态： $p_{ii}=1$ ，一旦进入就永远停留在该状态（如系统彻底崩溃无法修复）；
周期态/非周期态：状态返回间隔是否存在固定周期。

五、稳态分布（平稳分布）

当步数足够大，状态分布不再随时间变化，满足：

\boldsymbol{\pi} = \boldsymbol{\pi}\cdot \boldsymbol{P},\quad \sum \pi_i=1

稳态概率代表系统长期运行下停留在各状态的平均概率，常用于计算系统可用度、长期失效概率。

六、软件可靠性场景举例（两状态马尔可夫链）

状态： $S_0$ （正常）、 $S_1$ （失效）

$p_{01}$ ：正常→失效概率
$p_{10}$ ：失效→修复概率
$p_{00}=1-p_{01},\ p_{11}=1-p_{10}$

转移矩阵：

\boldsymbol{P}= \begin{bmatrix} 1-p_{01} & p_{01}\\ p_{10} & 1-p_{10} \end{bmatrix}

求解稳态

\boldsymbol{\pi}=[\pi_0,\pi_1]

，

\pi_0

就是系统稳态可用度。

七、优缺点

优点

数学成熟，计算简单，适合建模失效、修复、多状态系统；
可求瞬态概率、长期稳态可用度、MTTF；
扩展到连续时间马尔可夫链（CTMC）可适配连续运行时间场景。

缺点

强无记忆假设，真实系统失效存在历史相关性，带来误差；
状态数量多则矩阵维度爆炸，计算量大；
齐次假设要求转移概率恒定，实际故障率会随使用时间变化。

八、总结

马尔可夫链是离散时间、离散状态的随机序列，核心是马尔可夫无记忆性：下一状态仅依赖当前状态，与历史无关。组成：状态空间、一步转移概率矩阵、初始分布；核心计算：n步转移矩阵、稳态平稳分布；工程用途：软件可靠性、双机热备可用性、故障修复系统建模。

注意：本文归作者所有，未经作者允许，不得转载