马尔可夫链

本页讨论离散时间、有限状态的马尔可夫过程，即离散时间马尔可夫链（也有连续时间马尔可夫链）。假设有一个有限的状态集合 $S = \{s_1, s_2, \ldots, s_n\}$，进一步假设时间齐次，即一步转移概率不依赖 $t$，其转移概率矩阵为 $P$，其中 $P_{ij} = P(X_{t+1} = s_j | X_t = s_i)$ 表示从状态 $s_i$ 转移到状态 $s_j$ 的概率。

平稳分布

在某些条件下，马尔可夫链会趋向于一个平稳分布（stationary distribution），即存在一个概率分布 $\pi$，使得：

$$\pi P = \pi$$

这表示若初始分布就是 $\pi$，则以后每一步的分布都是 $\pi$，不需要等待长时间；它本身不保证任意初始分布都趋近于 $\pi$。

计算与收敛条件

采用行概率向量：$P_{ij}\ge0$、$\sum_jP_{ij}=1$，初始分布 $\mu_0$ 在第 $n$ 步为 $\mu_n=\mu_0P^n$。平稳分布还须满足 $\pi_i\ge0$、$\sum_i\pi_i=1$。有限状态链至少有一个平稳分布；不可约时唯一；再加非周期性，才保证对任意初始分布 $\mu_0P^n\to\pi$。

例如 $P=\begin{bmatrix}0.8&0.2\\0.3&0.7\end{bmatrix}$，解 $\pi P=\pi$ 得 $\pi=(0.6,0.4)$。若从状态 1 出发，第 $n$ 步状态 1 的概率 $q_n$ 满足 $q_{n+1}=0.3+0.5q_n$，所以 $q_n=0.6+0.4(0.5)^n\to0.6$。

反例 $P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ 不可约且唯一平稳分布为 $(1/2,1/2)$，但从状态 1 出发分布每步交替，不收敛。$P=I$ 则每个概率分布都平稳，显示可约时唯一性也会失败。多步矩阵的含义见多步转移概率的确定。