Question

Markov Chain

许多个状态，每个状态都可以转移到其他状态，转移机率的总和都是 1。转移机率习惯写成一个矩阵，称作“转移矩阵 Transition Matrix”、“随机矩阵 Stochastic Matrix”。

选定一个状态作为起点，不断移动（不断转移状态、状态不断变化），走出一条路线。考虑所有可能的路线，每一条路线都可以明确计算其机率。将所有路线，朦胧地幻想成一条路线，步步充满随机，这条路线叫做“马可夫链”。

Markov Chain 可以看成图论的有向图：状态是点，状态转移是边，机率是边的权重，转移矩阵是图论资料结构 adjacency matrix。

Markov Chain 的主要功用，是预测事情的未来发展。一些体积微小、性质稳定的东西（例如空气分子、细胞），适合使用 Markov Chain 模拟未来发展情况（例如气体扩散、细胞繁殖）。Markov Chain 是物理模拟、化学模拟领域的重要工具。

动画： http://setosa.io/blog/2014/07/26/markov-chains/

走 n 步抵达什麽状态？

一个状态的机率，是所有来源状态各自乘上转移机率，再加总。

走 1 步，可以表示成矩阵乘以向量。矩阵是转移矩阵的转置，向量是每个状态的抵达机率。一开始，起始状态的抵达机率是 1，其馀状态的抵达机率是 0。

走 n 步，即是矩阵的 n 次方乘以向量。类似于图论的 Transitive Closure。

最终走向什麽状态？

走无限多步。矩阵的∞次方。中途可能收敛到某个状态。

直觉的演算法：一步一步走，矩阵一个一个乘。

较快的演算法：计算 eigenvalue 的绝对值。

数学家已经证明：

一、eigenvalue 一定包含 1。
二、所有的 eigenvalue，绝对值均小于等于 1。

结局可能是：

一、只有一个 1，其他均小于 1：收敛至 1 的 eigenvector 的方向上面。
二、有许多个 1：收敛至这些 eigenvector 构成的区域裡面。
三、有-1：状态不断循环。
四、有虚数、其长度为 1：状态不断循环。

若将这个世界的时间线想成是 Markov Chain，那麽这个世界的未来，也许同归于一，也许不断轮迴。

途中走过什麽状态？

reducibility：状态 x 到 y，有路可通（机率大于零）。即是图论的 Reachability。

periodicity：状态 x 到 x，所有可能的步数，找出其规律。即是找出经过 A 的环，找出其边数，找出其规律。类似于图论的 Cycle Basis。

recurrent：状态 x 出发，所有路线都走回 x，无法摆脱轮迴。

每个状态出现多少次？

https://class.coursera.org/smac-002/lecture/

http://www.52nlp.cn/lda-math-mcmc-和-gibbs-sampling1

http://www.52nlp.cn/lda-math-mcmc-和-gibbs-sampling2

当转移机率满足某些条件时，我们可以藉由随机取样，得到合法状态，并且得到每个状态的出现比例。

关键字是 stationary distribution、steady state distribution、equilibrium distribution。

UVa 10828 11021 11762 12730 11680 Timus 1766

应用：Animation State Machine

Animation State Machine

游戏动画、游戏 AI、游戏平衡的经典工具！

这裡提供的 Markov Chain 只是推测，应该是错的。

应用：Random Walk

Random Walk on 3x3 Grid

一个 3x3 的方格棋盘，左上角放著一个棋子。棋子可以上下左右移动一格，机率各是 1/4。如果棋子出界，那麽棋子归回原位。

棋子走零步，停于左上的机率为 1，其馀格子为 0。

棋子走一步，停于左上的机率为 2/4，上、左的机率各为 1/4，其馀为 0。

棋子走两步，停于左上的机率为 6/16，上、左的机率各为 3/16，右上、左下的机率各为 1/16，中央为 2/16，其馀为 0。

那麽棋子走 n 步呢？

_______     [2]     [ 2 1 0 1 0 0 0 0 0 ] [1]
|0|1|2|     [1]     [ 1 1 1 0 1 0 0 0 0 ] [0]
|-+-+-|     [0]     [ 0 1 2 0 0 1 0 0 0 ] [0]
|3|4|5|   1 [1]   1 [ 1 0 0 1 1 0 1 0 0 ] [0]
|-+-+-|   - [0] = - [ 0 1 0 1 0 1 0 1 0 ] [0]
|6|7|8|   4 [0]   4 [ 0 0 1 0 1 1 0 0 1 ] [0]
‾‾‾‾‾‾‾     [0]     [ 0 0 0 1 0 0 2 1 0 ] [0]
 board      [0]     [ 0 0 0 0 1 0 1 1 1 ] [0]
 index      [0]     [ 0 0 0 0 0 1 0 1 2 ] [0]
         ^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^ ^^^
           x1                 A            x0

走一步的结果，採用递归法来分析：一个状态的机率，是所有来源状态各自乘上转移机率，再加总。计算方式恰好符合线性变换的定义，于是可以写成矩阵。

走 n 步，即是计算矩阵的 n 次方。观念如同图论的“ Transitive Closure ”。

运用 Markov Chain 可以得知世界终焉之时，棋子大概会在哪。

发挥想像力，应用非常广。迷路回不了家的机率、人类经济活动与最终财富分配等等。

应用：PageRank

PageRank

http://blog.csdn.net/monkey_d_meng/article/details/6556295

http://morris821028.github.io/2015/03/09/bigdata-page-rank/

Markov Decision Process（Under Construction!）

Markov Decision Process

“马可夫决策程序”。

【注：process 是连续版本，chain 是离散版本。此处的 MDP 是离散版本，照理要取名 chain；而作者不知为何取名 process。】

类神经网路、马可夫决策程序（以时刻展开），两者构造大同小异，于是最近计算学家拿类神经网路的计算设备来研究马可夫决策程序。

http://ai.berkeley.edu/lecture_slides.html

应用：Pac-Man

Pac-Man

Automaton（Under Construction!）

Automaton

“自动机”。