马尔科夫链

马尔可夫链（Markov Chain, MC）是概率论和数理统计中具有马尔可夫性质（Markov property）且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process。

适用于连续指数集的马尔可夫链被称为马尔可夫过程（Markov process），但有时也被视为马尔可夫链的子集，即连续时间马尔可夫链（Continuous-Time MC, CTMC），与离散时间马尔可夫链（Discrete-Time MC, DTMC）相对应，因此马尔可夫链是一个较为宽泛的概念。

马尔可夫链可通过转移矩阵和转移图定义，除马尔可夫性外，马尔可夫链可能具有不可约性、重现性、周期性和遍历性。

一个不可约和正重现的马尔可夫链是严格平稳的马尔可夫链，拥有唯一的平稳分布。遍历马尔可夫链（ergodic MC）的极限分布收敛于其平稳分布。

马尔可夫链可被应用于蒙特卡罗方法中，形成马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC），也被用于动力系统、化学反应、排队论、市场行为和信息检索的数学建模。此外作为结构最简单的马尔可夫模型（Markov model），一些机器学习算法，例如隐马尔可夫模型（Hidden Markov Model, HMM）、马尔可夫随机场（Markov Random Field, MRF）和马尔可夫决策过程（Markov decision process, MDP）以马尔可夫链为理论基础。

马尔可夫链的命名来自俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков）以纪念其首次提出马尔可夫链和对其收敛性质所做的研究。

概念

在机器学习算法中，马尔可夫链(Markov chain)是个很重要的概念。

马尔可夫链（Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain），因俄国数学家安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。

该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。

在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的（无论之前漫步路径是如何的）。

快速入门

数学表达

马克科夫链是一个随机系统，必须满足两个条件：

（1）系统任意时刻可以用有限个可能状态之一来描述

（2）系统无后效性，即某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响无后效性(附录有详细描述)

条件1-概率向量(状态向量)

条件2-转移概率矩阵

简单例子

有一个大的汽车租赁公司，有三家门店，你租的时候可以选择任何一个门店，还的时候也可以选择任何一家门店，从不同门店借出和归还的概率如下表:

归还\借出	1	2	3
1	0.5	0.3	0.3
2	0.2	0.1	0.6
3	0.3	0.6	0.1

问题: 一辆车出2号门店借出，公司前三次应该从哪家店找最快捷?

那么初始状态 X(0)=(0,1,0), 转移矩阵 P为：

要求：每一行之和为1。

  [plaintext]
1
2
3
| 0.5	| 0.2	| 0.3 |
| 0.3	| 0.1	| 0.6 |
| 0.3	| 0.6	| 0.1 |

基础知识

接下来要做的其实就是矩阵乘法，这里直接使用其中的

java 实现的矩阵乘法

测试代码

我们测试 30 次

  [java]
1
2
3
4
5
6
7
8
9
10
11
12
double[] arrayOne = {0, 1, 0};

double[][] arrayTwo = {
        {0.5, 0.2, 0.3},
        {0.3, 0.1, 0.6},
        {0.3, 0.6, 0.1}
};

for(int i = 0; i < 30; i++) {
    arrayOne = dot(arrayOne, arrayTwo);
    System.out.println(i + ", " + Arrays.toString(arrayOne));
}

输出日志

  [plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0, [0.3, 0.1, 0.6]
1, [0.36, 0.43, 0.21]
2, [0.372, 0.241, 0.387]
3, [0.37439999999999996, 0.3307, 0.2949]
4, [0.37487999999999994, 0.28489, 0.34023]
5, [0.374976, 0.30760299999999996, 0.31742099999999995]
6, [0.3749952, 0.2962081, 0.32879669999999994]
7, [0.37499903999999995, 0.30189786999999996, 0.3231030899999999]
8, [0.3749998079999999, 0.2990514489999999, 0.32594874299999993]
9, [0.37499996159999993, 0.30047435229999997, 0.3245256860999999]
10, [0.3749999923199999, 0.2997628392099999, 0.32523716846999995]
11, [0.3749999984639999, 0.30011858346699993, 0.3248814180689999]
12, [0.37499999969279985, 0.2999407088808999, 0.32505929142629986]
13, [0.37499999993855987, 0.30002964568242985, 0.3249703543790099]
14, [0.37499999998771183, 0.2999851771833609, 0.32501482282892685]
15, [0.37499999999754224, 0.30000741141323456, 0.32499258858922275]
16, [0.37499999999950834, 0.2999962942943656, 0.3250037057061257]
17, [0.3749999999999015, 0.3000018528530136, 0.32499814714708436]
18, [0.3749999999999802, 0.2999990735735323, 0.32500092642648704]
19, [0.3749999999999959, 0.3000004632132415, 0.32499953678676213]
20, [0.37499999999999906, 0.2999997683933806, 0.32500023160661984]
21, [0.37499999999999967, 0.30000011580330976, 0.32499988419669007]
22, [0.3749999999999998, 0.29999994209834496, 0.32500005790165476]
23, [0.3749999999999998, 0.3000000289508273, 0.3249999710491724]
24, [0.3749999999999998, 0.2999999855245861, 0.32500001447541355]
25, [0.3749999999999998, 0.3000000072377067, 0.3249999927622929]
26, [0.3749999999999998, 0.2999999963811464, 0.3250000036188532]
27, [0.3749999999999997, 0.3000000018094265, 0.32499999819057307]
28, [0.3749999999999997, 0.2999999990952864, 0.32500000090471315]
29, [0.3749999999999997, 0.3000000004523565, 0.3249999995476431]

其实 i=22 的时候，基本概率已经收敛于 [0.375, 0.30, 0.325]，差异基本上只是浮点的计算问题。

初始状态无关性

其实后面回提到，不管我们的初始状态是什么样子的，只要状态转移矩阵不发生变化，当 n→∞ 时，最终状态始终会收敛到一个固定值。

我们来先验证下：

我们调整下初始状态为：double[] arrayOne = {1, 0, 0};，再次测试：

  [plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0, [0.5, 0.2, 0.3]
1, [0.4, 0.3, 0.30000000000000004]
2, [0.38000000000000006, 0.29000000000000004, 0.33]
3, [0.376, 0.30300000000000005, 0.32100000000000006]
4, [0.37520000000000003, 0.29810000000000003, 0.32670000000000005]
5, [0.37504000000000004, 0.30087, 0.32409]
6, [0.37500800000000006, 0.299549, 0.32544300000000004]
7, [0.37500160000000005, 0.30022230000000005, 0.32477610000000007]
8, [0.37500032000000005, 0.29988821000000004, 0.32511147]
9, [0.375000064, 0.30005576700000003, 0.32494416900000006]
10, [0.37500001280000006, 0.29997209090000004, 0.3250278963]
11, [0.3750000025600001, 0.30001394943000004, 0.3249860480100001]
12, [0.3750000005120001, 0.29999302426100005, 0.32500697522700006]
13, [0.37500000010240003, 0.3000034876647001, 0.32499651223290005]
14, [0.37500000002048, 0.29999825612669007, 0.3250017438528301]
15, [0.37500000000409606, 0.30000087192846303, 0.3249991280674411]
16, [0.37500000000081923, 0.2999995640341302, 0.3250004359650508]
17, [0.3750000000001639, 0.30000021798260734, 0.32499978201722896]
18, [0.37500000000003286, 0.2999998910086309, 0.32500010899133647]
19, [0.3750000000000066, 0.3000000544956716, 0.324999945504322]
20, [0.3750000000000014, 0.29999997275216167, 0.3250000272478371]
21, [0.37500000000000033, 0.3000000136239187, 0.3249999863760811]
22, [0.3750000000000001, 0.2999999931880406, 0.3250000068119594]
23, [0.37500000000000006, 0.3000000034059797, 0.32499999659402035]
24, [0.37500000000000006, 0.2999999982970102, 0.32500000170298987]
25, [0.37500000000000006, 0.3000000008514949, 0.3249999991485051]
26, [0.37500000000000006, 0.29999999957425255, 0.3250000004257475]
27, [0.37500000000000006, 0.30000000021287376, 0.3249999997871263]
28, [0.37500000000000006, 0.29999999989356313, 0.32500000010643687]
29, [0.375, 0.3000000000532185, 0.3249999999467816]

计算结果还是收敛于 [0.375, 0.30, 0.325]

马尔科夫链基本特性

核心思想

马尔科夫链的概念在很多地方都被提及过，它的核心思想是某一时刻状态转移的概率只依赖于它的前一个状态。

我们用数学定义来描述，则假设我们的序列状态是…X(t−2), X(t−1), X(t), X(t+1),…，那么我们的在时刻X(t+1)的状态的条件概率仅仅依赖于时刻X(t)，即：

状态转移矩阵

既然某一时刻状态转移的概率只依赖于它的前一个状态，那么我们只要能求出系统中任意两个状态之间的转换概率，这个马尔科夫链的模型就定了。

状态转移情况如下图所示

则状态转移矩阵可以表示为

此时，我们给定一个初始状态，然后经过该状态转移矩阵的转换，最终会收敛到一个稳定的状态，具体如马尔科夫链定理所示

核心定理

由于马尔科夫链能收敛到平稳分布，于是有了一个想法：如果我们能构造一个转移矩阵为P的马氏链，使得该马氏链的平稳分布恰好是p(x), 那么我们从任何一个初始状态x0出发沿着马氏链转移, 得到一个转移序列 x0, x1, x2,⋯xn, xn+1⋯，如果马氏链在第n步已经收敛了，于是我们就得到了 π(x) 的样本xn, xn+1⋯（也就是从第n步收敛时开始，之后的x都服从同一个平稳分布，我们可以将这个分布设定为我们的目标采样分布）。

细致平稳定理

从上面可以看出马尔科夫链的平稳分布收敛主要依赖于状态转移矩阵，所以关键是如何构建状态转移矩阵，使得最终的平稳分布是我们所要的分布。

想做到这一点主要依赖于细致平稳定理

ps: 数学符号手写非常优美，但是计算机输入还是有点不太友好（不同地方显示不同，虽然有 LaTex 等语法），此处暂时用截图代替。

马尔可夫模型（Markov model）

马尔可夫链或马尔可夫过程不是唯一以马尔可夫性质为基础建立的随机过程，事实上，隐马尔可夫模型、马尔可夫决策过程、马尔可夫随机场等随机过程/随机模型都具有马尔可夫性质并被统称为马尔可夫模型。

这里对马尔可夫模型的其它成员做简要介绍：

1. 隐马尔可夫模型（Hidden Markov Model, HMM）

HMM是一个状态空间不完全可见，即包含隐藏状态（hidden status）的马尔可夫链，HMM中可见的部分被称为输出状态（emission state），与隐藏状态有关，但不足以形成完全的对应关系。

以语音识别（speech recognition）为例，需要识别的语句是不可见的隐藏状态，接收的语音或音频是和语句有关的输出状态，此时HMM常见的应用是基于马尔可夫性质从语音输入推出其对应的语句，即从输出状态反解隐藏状态。

2. 马尔可夫决策过程（Markov decision process, MDP）

MDP是在状态空间的基础上引入了“动作”的马尔可夫链，即马尔可夫链的转移概率不仅与当前状态有关，也与当前动作有关。

MDP包含一组交互对象，即智能体（agent）和环境，并定义了5个模型要素：状态（state）、动作（action）、策略（policy）、奖励（reward）和回报（return），其中策略是状态到动作的映射，回报是奖励随时间步的折现或积累。

在MDP的演化中，智能体对环境的初始状态进行感知，按策略实施动作，环境受动作影响进入新的状态并反馈给智能体一个奖励。

智能体接收“奖励”并采取新的策略，与环境持续交互。MDP是强化学习（reinforcement learning）的数学模型之一，被用于模拟智能体可实现的随机性策略与回报。

MDP的推广之一是部分可观察马尔可夫决策过程（partially observable Markov decision process, POMDP），即考虑了HMM中隐藏状态和输出状态的MDP。

3. 马尔可夫随机场（Markov Random Field, MRF）

MRF是马尔可夫链由一维指数集向高维空间的推广。

MRF的马尔可夫性质表现为其任意一个随机变量的状态仅由其所有邻接随机变量的状态决定。

类比马尔可夫链中的有限维分布，MRF中随机变量的联合概率分布是所有包含该随机变量的团（cliques）的乘积。mn
MRF最常见的例子是伊辛模型（Ising model）。

哈里斯链（Harris chain）

哈里斯链是马尔可夫链从可数状态空间向连续状态空间的推广，给定可测空间上的平稳马尔可夫链，若对可测空间的任意子集和子集的返回时间

一个经典的马尔科夫链实例

用一句话来概括马尔科夫链的话，那就是某一时刻状态转移的概率只依赖于它的前一个状态。

举个简单的例子，假如每天的天气是一个状态的话，那个今天是不是晴天只依赖于昨天的天气，而和前天的天气没有任何关系。

这么说可能有些不严谨，但是这样做可以大大简化模型的复杂度，因此马尔科夫链在很多时间序列模型中得到广泛的应用，比如循环神经网络RNN，隐式马尔科夫模型HMM等。

数学公式

假设状态序列为 …x_(t-2), x_(t-1), x_(t), x_(t+1), x_(t+2) ….

由马尔科夫链定义可知，时刻 x_(t+1) 的状态只与 x_(t) 有关

用数学公式来描述就是：

  [plaintext]
1
P(x_t+1 | ..., x_t-2, x_t-1, x_t) = P(x_t+1 | x_t)

既然某一时刻状态转移的概率只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔科夫链的模型就定了。

具体例子

看一个具体的例子。

这个马尔科夫链是表示股市模型的，共有三种状态：牛市（Bull market）, 熊市（Bear market）和横盘（Stagnant market）。

每一个状态都以一定的概率转化到下一个状态。

比如，牛市以0.025的概率转化到横盘的状态。

这个状态概率转化图可以以矩阵的形式表示。

如果我们定义矩阵阵P某一位置P(i, j)的值为P(j	i)，即从状态i变为状态j的概率。

另外定义牛市、熊市、横盘的状态分别为0、1、2，这样我们得到了马尔科夫链模型的状态转移矩阵为：

  [plaintext]
1
2
3
0.9     0.075   0.025 
0.15    0.8     0.0.5
0.25    0.25    0.5

当这个状态转移矩阵P确定以后，整个股市模型就已经确定！

状态转移矩阵

从上面的例子不难看出来，整个马尔可夫链模型的核心是状态转移矩阵P。

那这个矩阵P有一些什么有意思的地方呢？

接下来再看一下。

以股市模型为例，假设初始状态为 t_0 = [0.1, 0.2, 0.7]

  [py]
1
2
3
4
5
6
7
8
9
10
11
12
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()

np.dot() 执行了矩阵的乘法。

输出的结果：

  [plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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次开始，状态就开始收敛至 24 [ 0.6248219 0.31266282 0.06251528]。

最终数字上略有不同，只是计算机浮点数运算造成的罢了。

如果我们换一个初始状态 t_0，比如 [0.2, 0.3, 0.5]，继续运行上面的代码，只是将init_array变一下，最后结果为：

  [plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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]

后续还开始收敛于 [ 0.62484014 0.31264614 0.06251372]

这个转移矩阵就厉害了。

不管我们的初始状态是什么样子的，只要状态转移矩阵不发生变化，当 n→∞ 时，最终状态始终会收敛到一个固定值。

矩阵

在矩阵分析，自动控制原理等过程中，经常会提到矩阵的幂次方的性质。

我们也看看这个状态转移矩阵 P 的幂次方有什么有意思的地方？

废话不多说，直接上代码。

  [py]
1
2
3
4
5
6
7
8
9
10
11
def matrixpower():
    transfer_matrix = np.array([[0.9, 0.075, 0.025],
                               [0.15, 0.8, 0.05],
                               [0.25, 0.25, 0.5]])
    restmp = transfer_matrix
    for i in range(25):
        res = np.dot(restmp, transfer_matrix)
        print i, "\t", res
        restmp = res

matrixpower()

运行结果：

  [plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
0 	[[ 0.8275   0.13375  0.03875]
 [ 0.2675   0.66375  0.06875]
 [ 0.3875   0.34375  0.26875]]
1 	[[ 0.7745   0.17875  0.04675]
 [ 0.3575   0.56825  0.07425]
 [ 0.4675   0.37125  0.16125]]
2 	[[ 0.73555   0.212775  0.051675]
 [ 0.42555   0.499975  0.074475]
 [ 0.51675   0.372375  0.110875]]
3 	[[ 0.70683   0.238305  0.054865]
 [ 0.47661   0.450515  0.072875]
 [ 0.54865   0.364375  0.086975]]
4 	[[ 0.685609   0.2573725  0.0570185]
 [ 0.514745   0.4143765  0.0708785]
 [ 0.570185   0.3543925  0.0754225]]
5 	[[ 0.6699086  0.2715733  0.0585181]
 [ 0.5431466  0.3878267  0.0690267]
 [ 0.585181   0.3451335  0.0696855]]
6 	[[ 0.65828326  0.28213131  0.05958543]
 [ 0.56426262  0.36825403  0.06748335]
 [ 0.5958543   0.33741675  0.06672895]]
7 	[[ 0.64967099  0.28997265  0.06035636]
 [ 0.5799453   0.35379376  0.06626094]
 [ 0.60356362  0.33130471  0.06513167]]
8 	[[ 0.64328888  0.29579253  0.06091859]
 [ 0.59158507  0.34309614  0.06531879]
 [ 0.60918588  0.32659396  0.06422016]]
9 	[[ 0.63855852  0.30011034  0.06133114]
 [ 0.60022068  0.33517549  0.06460383]
 [ 0.61331143  0.32301915  0.06366943]]
10 	[[ 0.635052    0.30331295  0.06163505]
 [ 0.60662589  0.3293079   0.06406621]
 [ 0.61635051  0.32033103  0.06331846]]
11 	[[ 0.63245251  0.30568802  0.06185947]
 [ 0.61137604  0.32495981  0.06366415]
 [ 0.61859473  0.31832073  0.06308454]]
12 	[[ 0.63052533  0.30744922  0.06202545]
 [ 0.61489845  0.32173709  0.06336446]
 [ 0.6202545   0.31682232  0.06292318]]
13 	[[ 0.62909654  0.30875514  0.06214832]
 [ 0.61751028  0.31934817  0.06314155]
 [ 0.62148319  0.31570774  0.06280907]]
14 	[[ 0.62803724  0.30972343  0.06223933]
 [ 0.61944687  0.3175772   0.06297594]
 [ 0.6223933   0.3148797   0.062727  ]]
15 	[[ 0.62725186  0.31044137  0.06230677]
 [ 0.62088274  0.31626426  0.062853  ]
 [ 0.62306768  0.31426501  0.06266732]]
16 	[[ 0.62666957  0.31097368  0.06235675]
 [ 0.62194736  0.31529086  0.06276178]
 [ 0.62356749  0.31380891  0.0626236 ]]
17 	[[ 0.62623785  0.31136835  0.0623938 ]
 [ 0.6227367   0.31456919  0.06269412]
 [ 0.62393798  0.31347059  0.06259143]]
18 	[[ 0.62591777  0.31166097  0.06242126]
 [ 0.62332193  0.31403413  0.06264394]
 [ 0.62421263  0.31321968  0.0625677 ]]
19 	[[ 0.62568045  0.31187792  0.06244162]
 [ 0.62375584  0.31363743  0.06260672]
 [ 0.62441624  0.31303361  0.06255015]]
20 	[[ 0.6255045   0.31203878  0.06245672]
 [ 0.62407756  0.31334332  0.06257913]
 [ 0.62456719  0.31289565  0.06253716]]
21 	[[ 0.62537405  0.31215804  0.06246791]
 [ 0.62431608  0.31312525  0.06255867]
 [ 0.62467911  0.31279335  0.06252754]]
22 	[[ 0.62527733  0.31224646  0.06247621]
 [ 0.62449293  0.31296357  0.0625435 ]
 [ 0.62476209  0.3127175   0.06252042]]
23 	[[ 0.62520562  0.31231202  0.06248236]
 [ 0.62462404  0.3128437   0.06253225]
 [ 0.62482361  0.31266126  0.06251514]]
24 	[[ 0.62515245  0.31236063  0.06248692]
 [ 0.62472126  0.31275483  0.06252391]
 [ 0.62486922  0.31261956  0.06251122]]

从第 20 次开始，结果开始收敛，并且每一行都为 [ 0.6255045 0.31203878 0.06245672]

马尔可夫链细致平稳条件

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

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

以上是马尔可夫链收敛的必要条件。

假设有一个概率的单纯形向量 v0，例如我们前面的例子 [0.2, 0.3, 0.5]

有一个概率转移矩阵 P，例如我们前面的例子：

  [plaintext]
1
2
3
0.9     0.075   0.025 
0.15    0.8     0.0.5
0.25    0.25    0.5

其中，v0 每个元素的取值范围为[0,1]，并且所有元素的和为1。

而 P 的每一行也是个概率单纯形向量。

由前面的例子我们不难看出，当 v0 与 P 的n次幂相乘以后，发现得到的向量都会收敛到一个稳定值，而且此稳定值与初始向量 v0 无关！

那么所有的转移矩阵 P 都有这种现象嘛？

或者说满足什么样的条件的转移矩阵 P 会有这种现象？

细致平衡条件

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

π_i * P_ij = π_j * P_ji

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

证明过程比较简单：

取 j→∞，则有：

  [plaintext]
1
πP = π;

马尔可夫链收敛性质

PageRank 算法

1998年，Lawrence Page、Sergey Brin、Rajeev Mowatani和Terry Winorad出版了“PageRank引文排名：

为网页带来秩序（The PageRank Citation Ranking: Bringing Order to the Web）”，该文介绍了谷歌起初使用的而如今非常著名的PageRank算法。

20多年后，谷歌已经成为互联网巨头，即使算法已经发展了很多，PageRank仍然是谷歌排名算法的“象征”（即使很少有人能真正说出它在算法中所占的重量）。

马尔可夫链数学

从理论角度来看，有趣的是，PageRank算法的一个常见解释依赖于简单但基本的马尔可夫链数学概念。

我们将在本文中看到，马尔可夫链是随机建模的强大工具，对任何数据科学家都有用。

更特别的是，我们将回答一些基本的问题，例如：什么是马尔可夫链，它们有什么好的性质，以及可以用它们做什么？

马尔可夫性质与马尔可夫链

有一些众所周知的随机过程家族：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。

这些特定的案例，每一个都有具体的特性，使我们能够更好地研究和理解它们。

“马尔可夫性质”是使研究随机过程更加容易的一个性质。

马尔可夫性质非常非正式地表示，对于一个随机过程，如果我们知道在给定时间过程所取的值，我们就不会通过收集更多关于过去的知识来获得关于过程未来行为的任何额外信息。

用更为数学的术语表述，在任何给定的时间内，给定当前和过去状态的过程的未来状态的条件分布仅取决于当前状态，而完全不取决于过去状态（无记忆属性）。

具有马尔可夫性质的随机过程称为马尔可夫过程。

马尔可夫性质

马尔可夫性质表示这样一个事实，即在给定的时间步和已知当前状态的情况下，通过收集有关过去的信息，我们不会得到任何关于未来的额外信息。

基于前面的定义，我们现在可以定义“同构离散时间马尔可夫链”（为了简单起见，下面将称为“马尔可夫链”）。

马尔可夫链是一个具有离散时间和离散状态空间的马尔可夫过程。

因此，马尔可夫链是一个离散的状态序列，每个状态序列都是从一个离散的状态空间（有限或无限）中提取出来的，并且遵循马尔可夫性质。

在数学上，我们可以用下列式子表示马尔可夫链：

其中，在每一时刻，过程的值都是取自离散集E中的，如下所示：

  [plaintext]
1
x_n ∈ E, 任意 n ∈ N

那么，马尔可夫性质意味着有如下结论：

最后一个公式表达了这样一个事实：

对于给定的历史（我现在在哪里，我以前在哪里），下一个状态（我将去向何方）的概率分布仅取决于当前状态，而不取决于过去的状态。

我们决定在这篇介绍性文章中只描述基本的同构离散时间马尔可夫链。

然而，也存在异构（时间依赖）和/或时间连续的马尔可夫链。

下面我们将不讨论模型的这些变体。

还要注意，上面给出的马尔可夫性质的定义是非常简单的：真正的数学定义涉及过滤的概念，这远远超出了这个适度介绍的范围。

拓展阅读

Vertibi 算法

隐马尔可夫模型（Hidden Markov Model, HMM）

最大熵模型

蒙特卡洛

贝叶斯原理

马尔可夫随机场（Markov Random Field, MRF）

马尔可夫决策过程（Markov decision process, MDP）

参考资料

知乎-马尔可夫链（Markov Chain）是什么鬼

知乎-如何通俗地解释马尔科夫链?

知乎-如何用简单易懂的例子解释隐马尔可夫模型？

知乎-马尔可夫链蒙特卡罗算法（MCMC）

马尔科夫链(Markov chain)5分钟简单入门

MBA 智库-马尔可夫链模型（Markov Chain Model）

吸收xx

吸收马尔科夫链图解

java 实现

马尔科夫链算法的JAVA实现

隐马尔科夫模型java实现

马尔科夫链
- 概念
快速入门
马尔科夫链基本特性
马尔可夫模型（Markov model）
一个经典的马尔科夫链实例
马尔可夫链细致平稳条件
- 细致平衡条件
- 马尔可夫链收敛性质
PageRank 算法
拓展阅读
参考资料
- 吸收xx
- java 实现

马尔科夫链

概念

快速入门

条件1-概率向量(状态向量)

条件2-转移概率矩阵

简单例子

基础知识

测试代码

初始状态无关性

马尔科夫链基本特性

核心思想

状态转移矩阵

核心定理

细致平稳定理

马尔可夫模型（Markov model）

1. 隐马尔可夫模型（Hidden Markov Model, HMM）

2. 马尔可夫决策过程（Markov decision process, MDP）

3. 马尔可夫随机场（Markov Random Field, MRF）

哈里斯链（Harris chain）

一个经典的马尔科夫链实例

数学公式

具体例子

状态转移矩阵

矩阵

马尔可夫链细致平稳条件

细致平衡条件

马尔可夫链收敛性质

PageRank 算法

马尔可夫链数学

马尔可夫性质与马尔可夫链

马尔可夫性质

拓展阅读

参考资料

吸收xx

java 实现

更多学习