# 马尔可夫链

## 形式化定义

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

### 变种

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

• m阶马尔可夫链（或记忆为m的马尔可夫链），其中m有限，为满足
{\displaystyle {\begin{aligned}{}&\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{aligned}}}

## 瞬态演变

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

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

${\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,}$

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

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

n步转移概率满足查普曼-科尔莫戈罗夫等式，对任意k使得0 < k < n

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

${\displaystyle \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)}$

## 性质

### 可还原性

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

${\displaystyle 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}}$

${\displaystyle 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}}$

### 周期性

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

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

## 有限状态空间

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

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

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

${\displaystyle \pi ={\frac {e}{\sum _{i}{e_{i}}}}}$

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

${\displaystyle \lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\pi ^{*}}$,

## 可反转马尔可夫链

{\displaystyle {\begin{aligned}\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{aligned}}}

${\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}.\,}$

${\displaystyle \sum _{i}\pi _{i}p_{ij}=\pi _{j}\,}$

## 参考文献

### 引用

1. ^ Norris, James R. Markov chains. Cambridge University Press. 1998 [2015-03-19]. （原始内容存档于2021-05-06）.
2. ^ Prasad, NR; RC Ender; ST Reilly; G Nesgos. Allocation of resources on a minimized cost basis. 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes. 1974, 13: 402–3. doi:10.1109/CDC.1974.270470. （原始内容存档于2015-02-12）.
3. Hamilton, James  . A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica (Econometrica, Vol. 57, No. 2). 1989, 57 (2): 357–84. JSTOR 1912559. doi:10.2307/1912559.

### 来源

• 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 978-0-89871-296-4. （See Chapter 7.）
• J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 978-0-471-52369-7.