# 马尔可夫链

## 正式定义

Xi 的可能值构成的可数集 S 叫做该链的“状态空间”。

### 变种

• 具有连续索引。
• 时齐马尔可夫链（或静态马尔可夫链）是对于所有 n
$\Pr(X_{n+1}=x\mid X_n=y) = \Pr(X_n=x\mid X_{n-1}=y)\,$

• m 阶马尔可夫链（或记忆为 m 的马尔可夫链）， 其中 m 有限，为满足
\begin{align} {} &\Pr(X_n=x_n\mid X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots , X_1=x_1) \\ = &\Pr(X_n=x_n\mid X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m}) \text{ for }n > m \end{align}

## 瞬态演变

n 步从状态 i 到状态 j 的概率为

$p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,$

$p_{ij} = \Pr(X_1=j\mid X_0=i). \,$

$p_{ij}^{(n)} = \Pr(X_{k+n}=j \mid X_{k}=i) \,$

$p_{ij} = \Pr(X_{k+1}=j \mid X_k=i). \,$

n步转移概率满足Chapman-Kolmogorov等式，对任意 k 使得 0 < k < n

$p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}$

$\Pr(X_{n}=j) = \sum_{r \in S} p_{rj} \Pr(X_{n-1}=r) = \sum_{r \in S} p_{rj}^{(n)} \Pr(X_0=r).$

## 性质

### 可还原性

$P(X_{n+1}| X_n)\,$

$P(X_{n+2}|X_n) = \int P(X_{n+2},X_{n+1}|X_n)\,dX_{n+1} = \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1}$

$P(X_{n+3}|X_n) = \int P(X_{n+3}|X_{n+2}) \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1} \, dX_{n+2}$

### 周期性

$P(X_{n+1}) = \int P(X_{n+1}|X_n)\,P(X_n)\,dX_n$

$\pi(X) = \int P(X|Y)\,\pi(Y)\,dY$

## 可反转马尔可夫链

\begin{align} \Pr(X_{n}=i\mid X_{n+1}=j) & = \frac{\Pr(X_n = i, X_{n+1} = j)}{\Pr(X_{n+1} = j)} \\ & = \frac{\Pr(X_{n} = i)\Pr(X_{n+1} = j\mid X_n=i)}{\Pr(X_{n+1} = j)}. \end{align}

$\pi_i p_{ij} = \pi_j p_{ji}.\,$

$\sum_i \pi_i p_{ij} = \pi_j\,$

## 有限状态空间中的马尔可夫链

$p_{ij} = \Pr(X_{n+1}=j\mid X_n=i). \,$

### 平稳分布与特征向量和单纯形的关系

$\pi\mathbf{P} = \pi.\,$

$\pi=\frac{e}{\sum_i{e_i}}$

### 有限状态空间内的时齐马尔可夫链

$\lim_{k\rightarrow\infty}\mathbf{P}^k=\pi^*$,

## 注释

1. ^ Norris, James R.. Markov chains. Cambridge University Press. 1998.

## 参考文献

• A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135-156, 1906.
• A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
• Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 7.)
• J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.