马尔科夫链(Markov Chain)

说到马尔可夫链，在机器学习界真是无人不知，无人不晓。谷歌用于确定搜索结果顺序的算法，称为PageRank，就是一种马尔可夫链。在卷积网络出现之前，HMM马尔可夫模型也是语音处理的常用方法。到底什么才是马尔可夫链，之前看了几个介绍特别生动，这里总结一下：

马尔可夫链

马尔科夫链是指数学中具有马尔科夫性质的离散事件随机过程。在其每一步中，系统根据概率分布可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。

下图中有两种状态：A和B。如果我们在A，接下来可以过渡到B或留在A。如果我们在B，可以过渡到A或者留在B。在这张图中，从任意状态到任意状态的转移概率是0.5。

盗个图~~

真正的建模工作者不会总是就画一张马尔科夫链图。 相反，他们会使用“转移矩阵”来计算转移概率。状态空间中的每个状态都会出现在表格中的一列或者一行中。矩阵中的每个单元格都告诉你从行状态转换到列状态的概率。因此，在矩阵中，单元格做的工作和图中的箭头所示是一样。在状态转移矩阵中，行和列都是可能的所有状态，对应位置就是已知行状态，转移到列状态的概率。

还是盗图~~

如果状态空间添加了一个状态，我们将添加一行和一列，向每个现有的列和行添加一个单元格。 这意味着当我们向马尔可夫链添加状态时，单元格的数量会呈二次方增长。因此，转换矩阵就起到了很大的作用（除非你想把法尔科夫链图画的跟丛林一样）。

状态转移矩阵

从上面可以看出，整个马尔可夫链中的核心就是状态转移矩阵。以股市模型为例，假设初始状态为，然后算之后的状态。

def markov():
    init_array = np.array([0.1, 0.2, 0.7])
    transfer_matrix = np.array([[0.9, 0.075, 0.025],
                               [0.15, 0.8, 0.05],
                               [0.25, 0.25, 0.5]])
    restmp = init_array
    for i in range(25):
        res = np.dot(restmp, transfer_matrix)
        print i, "\t", res
        restmp = res

markov()

输出结果：

0   [ 0.295   0.3425  0.3625]
1   [ 0.4075   0.38675  0.20575]
2   [ 0.4762  0.3914  0.1324]
3   [ 0.52039   0.381935  0.097675]
4   [ 0.55006   0.368996  0.080944]
5   [ 0.5706394  0.3566873  0.0726733]
6   [ 0.58524688  0.34631612  0.068437  ]
7   [ 0.59577886  0.33805566  0.06616548]
8   [ 0.60345069  0.33166931  0.06487999]
9   [ 0.60907602  0.32681425  0.06410973]
10  [ 0.61321799  0.32315953  0.06362248]
11  [ 0.61627574  0.3204246   0.06329967]
12  [ 0.61853677  0.31838527  0.06307796]
13  [ 0.62021037  0.31686797  0.06292166]
14  [ 0.62144995  0.31574057  0.06280949]
15  [ 0.62236841  0.31490357  0.06272802]
16  [ 0.62304911  0.31428249  0.0626684 ]
17  [ 0.62355367  0.31382178  0.06262455]
18  [ 0.62392771  0.31348008  0.06259221]
19  [ 0.624205   0.3132267  0.0625683]
20  [ 0.62441058  0.31303881  0.06255061]
21  [ 0.624563    0.31289949  0.06253751]
22  [ 0.624676   0.3127962  0.0625278]
23  [ 0.62475978  0.31271961  0.06252061]
24  [ 0.6248219   0.31266282  0.06251528]

从第18次开始，状态就开始收敛至。
如果我们换一个初始状态，比如，继续运行上面的代码，只是将init_array变一下，最后结果为：

0   [ 0.35  0.38  0.27]
1   [ 0.4395   0.39775  0.16275]
2   [ 0.4959   0.39185  0.11225]
3   [ 0.53315   0.378735  0.088115]
4   [ 0.558674  0.365003  0.076323]
5   [ 0.5766378  0.3529837  0.0703785]
6   [ 0.5895162   0.34322942  0.06725438]
7   [ 0.59886259  0.33561085  0.06552657]
8   [ 0.6056996   0.32978501  0.06451539]
9   [ 0.61072624  0.32538433  0.06388944]
10  [ 0.61443362  0.32208429  0.06348209]
11  [ 0.61717343  0.31962047  0.0632061 ]
12  [ 0.61920068  0.31778591  0.06301341]
13  [ 0.62070185  0.31642213  0.06287602]
14  [ 0.62181399  0.31540935  0.06277666]
15  [ 0.62263816  0.31465769  0.06270415]
16  [ 0.62324903  0.31410005  0.06265091]
17  [ 0.62370187  0.31368645  0.06261168]
18  [ 0.62403757  0.31337972  0.06258271]
19  [ 0.62428645  0.31315227  0.06256128]
20  [ 0.62447096  0.31298362  0.06254542]
21  [ 0.62460776  0.31285857  0.06253366]
22  [ 0.62470919  0.31276586  0.06252495]
23  [ 0.62478439  0.31269711  0.0625185 ]
24  [ 0.62484014  0.31264614  0.06251372]

到第18次的时候，又收敛到了!这个转移矩阵就厉害了。不管我们的初始状态是什么样子的，只要状态转移矩阵不发生变化，当时，最终状态始终会收敛到一个固定值。

马尔可夫链细致平稳条件

首先，马尔科夫链要能收敛，需要满足以下条件：

1. 可能的状态数是有限的。
2. 状态间的转移概率需要固定不变。
3. 从任意状态能够转变到任意状态。
4. 不能是简单的循环，例如全是从x到y再从y到x。

由前面的例子我们不难看出，当与的n次幂相乘以后，发现得到的向量都会收敛到一个稳定值，而且此稳定值与初始向量 无关！那么所有的转移矩阵都有这种现象嘛？或者说满足什么样的条件的转移矩阵会有这种现象？

细致平衡条件（Detailed Balance Condition）：给定一个马尔科夫链，分布 和概率转移矩阵，如果下面等式成立:

则此马尔科夫链具有一个平稳分布（Stationary Distribution)。

参考链接：
小白都能看懂的马尔可夫链详解
13张动图助你彻底看懂马尔科夫链、PCA和条件概率!