本文译自A Brief Introduction to Markovs Chains
马尔可夫链是马尔可夫蒙特卡洛方法（MCMC）的关键部分。在 MCMC 方法中，马可科夫链被用来生成符合目标分布的随机变量。为了更好地理解什么是马可科夫链，以及它是如何按照特定分布进行取样的，下面的文章介绍并通过代码实现了几个基本的概念。
马尔可夫链是一个按序列（时间序列）运行的随机过程，在状态空间中（所有可能的状态构成的空间），从一个状态转移到另一个状态：
\(x^{(0)}\rightarrow x^{(1)}\rightarrow x^{(2)} ...\rightarrow x^{(t)}\rightarrow ...\)
一个马尔可夫链由三个元素定义：
1. 一个状态空间 \(x\)，这是一个集合，包含了所有可能取到的状态。
2. 一个转移算子 \(p(x^{(t+1)}|x^{(t)})\)，定义了从一个状态\(x^{(t)}\)转移到另一个状态\(x^{(t+1)}\)的概率。
3. 一个初始状态分布\(\pi^{0}\) ，定义了在\(t=0\)时，我们取得状态空间中任意一个可能的状态的相应概率。
马尔可夫链从初始状态开始，这个初始状态是按照概率分布\(\pi^{(0)}\) 来抽样得到的，然后按照转移算子 \(p(x^{(t+1)}|x^{(t)})\) 从一个状态转移到另一个状态，依次抽样得到一串序列。
马尔可夫链是无记忆性的，因为它下一个状态的概率仅仅取决于当前的状态，和前面所有状态都无关：
\(p(x^{(t+1)}|x^{(t)},x^{(t-1)}, ...x^{(0)}) = p(x^{(t+1)}|x^{(t)})\)
（这种无记忆的特性正式名称是马尔可夫性质）
如果马尔可夫链的转移算子在转移过程中始终保持不变，那么这个马尔可夫过程就叫做“齐次马尔可夫过程”（time homogenous）。齐次马尔可夫过程的一个非常好的性质是：当马尔可夫链运行了很长时间后，\(t\rightarrow \infty\)，这链将会到达一个平衡状态，也叫做平稳分布（stationary distribution）：
\(p(x^{(t+1)}|x^{(t)}) = p(x^{(t)}|x^{(t-1)})\)
我们后面将会看到马尔可夫链的平稳分布对取样的重要性，它是马尔可夫蒙特卡洛方法的核心。
如果马尔可夫链的状态空间是有限的离散值，而且它是齐次的，那么转移算子可以被定义为一个矩阵 \(P\)，\(P\) 的元素被定义为：
\(P_{i,j}=p(x^{(t+1)}=j|x^{(t)}=i)\)
它的意思是：如果当前的状态是第 i 个状态，那么，它下一个状态转移到状态 j 的概率是 \(P_{i,j}\)。矩阵 \(P\) 的每一行代表状态空间的一个条件概率分布，表示，在已知当前状态为 i 的情况下，下一个状态可以取状态空间中任何值，它们分别对应的概率。
我们接下来看一个有限维空间马尔可夫链的简单例子：
Example: Predicting the weather with a finite state-space Markov chain
假如加州大学伯克利分校的天气有三种：晴天，雾天和雨天（这用来模拟状态空间的三个离散的值）。这里的天气状态十分稳定，所以伯克利的天气预报员可以轻松地根据当前的天气来预测下周的天气，按照下面的规则：
如果今天是晴天，我们有
\(\bullet\) 下周有很大可能是晴天
\(\bullet\) \(p(X^{(week)}=sunny|X^{(today)}=sunny) = 0.8\)
\(\bullet\) 下周有很小的可能下雨
\(\bullet\) \(p(X^{(week)}=rainy|X^{(today)}=sunny) = 0.05\)
\(\bullet\) 下周有一定的可能起雾
\(\bullet\) \(p(X^{(week)}=foggy|X^{(today)}=sunny) = 0.15\)
如果今天是雾天，我们有
\(\bullet\) 下周有一定可能是晴天
\(\bullet\) \(p(X^{(week)}=sunny|X^{(today)}=foggy) = 0.4\)
\(\bullet\) 下周有一定的可能起雾
\(\bullet\) \(p(X^{(week)}=foggy|X^{(today)}=foggy) = 0.5\)
\(\bullet\) 下周有较小的可能下雨
\(\bullet\) \(p(X^{(week)}=rainy|X^{(today)}=foggy) = 0.1\)
如果今天是雨天，我们有
\(\bullet\) 下周不太可能是晴天
\(\bullet\) \(p(X^{(week)}=sunny|X^{(today)}=rainy) = 0.1\)
\(\bullet\) 下周有一定的可能起雾
\(\bullet\) \(p(X^{(week)}=foggy|X^{(today)}=rainy) = 0.3\)
\(\bullet\) 下周很有可能继续下雨
\(\bullet\) \(p(X^{(week)}=rainy|X^{(today)}=foggy) = 0.6\)
所有上面的这些转移规则可以用一个 3*3 的转移矩阵来表示：
A Brief Introduction to Markovs Chains
原文：http://www.cnblogs.com/yinxiangnan-charles/p/5017266.html