马尔可夫链

马尔可夫链（Markov chain）是一类逐步转移状态的随机过程。给定当前状态后，下一步的条件分布不再需要更早的历史。这里讨论离散时间、有限状态和不随时间改变的转移规则。

一台机器明天是否可用

设每天固定时刻记录一台机器的状态： $A$ 表示可用， $B$ 表示维修中。构造一个教学模型：今天可用，明天仍可用的概率为0.9；今天维修中，明天恢复可用的概率为0.3。假设这些概率只由当前状态决定，并在观察期间保持不变。

转移矩阵写成 $P = (\begin{matrix} 0.9 & 0.1 \\ 0.3 & 0.7 \end{matrix}) .$ 本篇用行表示出发状态、列表示到达状态，状态顺序均为 $(A, B)$ 。例如 $P_{B A} = 0.3$ 。每行概率和为1，因为机器下一天总处于这两个状态之一。

可用A和维修B两个圆点，A到B概率零点一、B到A概率零点三，自环分别为零点九和零点七 — 箭头表示一次观测间隔中的转移，标签是条件概率。

这个例子中的“只看当前”是模型假设。如果故障概率还明显依赖机器年龄，或者修复概率依赖已维修天数，只记A或B可能不够。可以扩大状态，把年龄或维修阶段也记录进去。

条件独立，而不是每天互相独立

用 $X_{n}$ 表示第 $n$ 天状态。对概率为正的历史事件，马尔可夫性质写为 $P (X_{n + 1} = j ∣ X_{n} = i, X_{n - 1} = i_{n - 1}, \dots, X_{0} = i_{0}) = P (X_{n + 1} = j ∣ X_{n} = i) = P_{i j} .$ 它表示当前状态已经包含了预测下一步所需的历史信息，并不表示相邻状态独立。比如知道今天在A，明天在A的概率是0.9；知道今天在B，同一概率变成0.3。

给定初始分布 $p_{0}$ ，一条指定路径的概率可逐步相乘： $P (X_{0} = i_{0}, \dots, X_{n} = i_{n}) = p_{0} (i_{0}) \prod_{k = 0}^{n - 1} P_{i_{k} i_{k + 1}} .$ 若初始一定可用，路径 $A \to B \to A$ 的概率是 $0.1 \times 0.3 = 0.03$ ，而 $A \to A \to A$ 的概率是0.81。

两天后可用的概率怎样计算

从A出发，两天后到A有两条中间路线： $A \to A \to A$ 与 $A \to B \to A$ 。它们互斥，因此相加： $P (X_{2} = A ∣ X_{0} = A) = 0. 9^{2} + 0.1 \times 0.3 = 0.84.$ 这正是矩阵乘积 $P^{2}$ 的AA元素。一般地， $(P^{m + n})_{i j} = \sum_{k} (P^{m})_{i k} (P^{n})_{k j} .$ 求和是在第 $m$ 步的各种中间状态上使用全概率公式，矩阵乘法由此有了概率含义。

令行向量 $p_{n} = (a_{n}, 1 - a_{n})$ 表示第 $n$ 天的分布，则 $p_{n + 1} = p_{n} P, a_{n + 1} = 0.9 a_{n} + 0.3 (1 - a_{n}) = 0.3 + 0.6 a_{n} .$ 因此 $p_{n} = p_{0} P^{n}$ 。如果使用列向量来存概率，就要改用 $P^{𝖳}$ 左乘；这与线性代数里的列向量迁移约定可以互相转换。

长期比例为何是四分之三

不再随一步转移改变的概率分布 $π$ 称为平稳分布，满足 $π P = π, π_{i} \geq 0, \sum_{i} π_{i} = 1.$ 对本例，令可用概率为 $a_{*}$ ，方程为 $a_{*} = 0.3 + 0.6 a_{*}$ ，故 $a_{*} = 0.75$ 。减去这一平衡值： $a_{n + 1} - 0.75 = 0.6 (a_{n} - 0.75), a_{n} = 0.75 + (a_{0} - 0.75) 0. 6^{n} .$ 从可用状态出发， $a_{0} = 1$ ，前几项为1、0.9、0.84、0.804；从维修状态出发，前几项为0、0.3、0.48、0.588。两者逐步靠近0.75。

分别从可用概率一和零出发的两组离散点，按相同递推从两侧接近零点七五 — 这里收敛的是各时刻的概率分布；一台机器仍可能反复故障与修复。

平稳分布也可用流量检查：长期从A到B的概率流为 $0.75 \times 0.1 = 0.075$ ，从B到A为 $0.25 \times 0.3 = 0.075$ 。两者相等，分布便不积累改变。在更一般的链中，逐对流量相等是更强的可逆性条件，平稳分布本身只要求各状态总流入与总流出平衡。

有平稳分布，是否一定收敛

不一定。考虑确定性交替的转移矩阵 $Q = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) .$ $(1 / 2, 1 / 2)$ 是平稳分布，但从A开始，分布永远在 $(1, 0)$ 与 $(0, 1)$ 间交替，不能趋向平稳分布。

交替链中处于A的概率在一和零之间来回切换，水平线二分之一表示存在但从该初值不会趋近的平稳概率 — 平稳性是分布的一步不变性；收敛还取决于链的结构。

有限状态链总有至少一个平稳分布。如果不可约，即任意状态都能在某个步数以正概率到达任意另一状态，则平稳分布唯一且各项为正。再有非周期性，则从任意初始分布出发都趋向它。一个状态的周期是所有可能返回步数的最大公约数；在不可约链中各状态周期相同。机器模型有正的自环，且两个状态互通，所以满足这两项条件。MIT 马尔可夫链讲义讨论了相关结构。

若 $P$ 是单位矩阵，每个状态都保持不动，则任意初始分布都是平稳分布，唯一性也不存在。这与交替链的失败原因不同。

不只问明天，也可以问还要等多久

从A出发，记 $T$ 为第一次进入B所需的转移次数。按模型，每次仍在A时，下一步离开的概率恒为0.1，所以 $P (T = k) = 0. 9^{k - 1} 0.1, k = 1, 2, \dots .$ 这是几何分布。通过尾和公式， $E [T] = \sum_{n = 0}^{\infty} P (T > n) = \sum_{n = 0}^{\infty} 0. 9^{n} = 10.$ 这里计入发生故障的那一次转移，不能和“故障前完整留在A的转移次数”混用，后者少1。同理，从B开始到A的平均等待是 $1 / 0.3 = 10 / 3$ 次转移。平均可用段与维修段的长度之比也给出 $10 / (10 + 10 / 3) = 3 / 4$ 。

对于更多状态，首次到达某个目标集合的期望常可由首步分析求解：在非目标状态 $i$ ，先花一步，再按转移概率加权后续等待，得到 $m_{i} = 1 + \sum_{j} P_{i j} m_{j}$ ；目标状态取0。使用这个方程前，还要确认所讨论的到达期望有限。

历史与使用

安德烈·马尔可夫研究相互依赖的随机变量序列，推动了概率极限定理从独立变量走向具有依赖结构的情形。他还把两状态链用于文学文本中元音、辅音的序列分析，相关史料见圣安德鲁斯大学 MacTutor 传记。今天的机器状态、随机游走、排队与抽样方法都可使用类似框架。

从观测估计转移矩阵时，一种直接方法是用“从 $i$ 到 $j$ 的观测次数”除以“从 $i$ 出发的总次数”。数据少、时间规律变化、状态遗漏都会影响结果。得到一个每行和为1的矩阵，只说明概率格式正确，马尔可夫假设还需要结合问题检验。

来源与继续阅读

Hao Wu，MIT 18.445，Lecture 1：马尔可夫性质、矩阵演化与平稳分布。
MIT 6.436J，Lecture 21：Markov Chains I：有限状态链的结构与长期分析。
MacTutor：Andrei Andreyevich Markov：历史研究。
先修：概率、矩阵、随机过程；相关：差分方程模型、几何分布、图论。