# 快速入门

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

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

## 简单例子

1 0.5 0.3 0.3
2 0.2 0.1 0.6
3 0.3 0.6 0.1

| 0.5	| 0.2	| 0.3 |
| 0.3	| 0.1	| 0.6 |
| 0.3	| 0.6	| 0.1 |


java 实现的矩阵乘法

### 测试代码

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));
}

• 输出日志
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]


### 初始状态无关性

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]


# 马尔科夫链基本特性

## 细致平稳定理

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

# 马尔可夫模型（Markov model）

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

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

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

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

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

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

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

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

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

MRF最常见的例子是伊辛模型（Ising model）。

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

## 数学公式

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


## 具体例子

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

0.9     0.075   0.025
0.15    0.8     0.0.5
0.25    0.25    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()


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

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]


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]


## 矩阵

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()


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]]


# 马尔可夫链细致平稳条件

1. 可能的状态数是有限的。

2. 状态间的转移概率需要固定不变。

3. 从任意状态能够转变到任意状态。

4. 不能是简单的循环，例如全是从x到y再从y到x。

0.9     0.075   0.025
0.15    0.8     0.0.5
0.25    0.25    0.5


## 细致平衡条件

π_i * P_ij = π_j * P_ji

πP = π;


# PageRank 算法

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

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

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

## 马尔可夫性质

x_n ∈ E, 任意 n ∈ N


Vertibi 算法

# 参考资料

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