马尔可夫链

w页码，1/5(W)马尔可夫链

维基百科，自由的百科全书

马尔可夫链，因俄罗斯数学家安德烈·马尔可夫得名，是数学中

具有马尔可夫性质的离散时间随机过程。该过程中，在给定当

前知识或信息的情况下，只有当前的状态用来预测将来，过去

（即当前以前的历史状态）对于预测将来（即当前以后的未来

状态）是无关的。

在马尔可夫链的每一步，系统根据概率分布，可以从一个状态

变到另一个状态,也可以保持当前状态。状态的改变叫做过渡，

与不同的状态改变相关的概率叫做过渡概率。随机漫步就是马

尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，

每一步可以移动到任何一个相邻的点，在这里移动到每一个点

的概率都是相同的(无论之前漫步路径是如何的)。

一个具有两个转换状态的马尔可夫链. 目录

■1 历史

■2 定义

■3 性质

■3.1 可还原性

■3.2 周期性

■3.3 重现性

■3.4 各态历遍性

■3.5 律动性

■3.6 平稳状态分析和极限分布

■4 可反转马尔可夫链

■5 有限状态空间中的马尔可夫链

■6 科学应用

■6.1 统计

■6.2 生物

■6.3 地理

■6.4 因特网应用

■6.5 马尔可夫模仿文本生成器

■7 参看

■8 参考文献

■9 外部链接

历史

马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。

定义

马尔可夫链是随机变量X1,X2,X3...的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。如果Xn + 1对于过去状态的条件概率分布仅是Xn的一个函数，则

w页码，2/5(W)这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。

性质

可还原性

马尔可夫链是由一个条件分布来表示的

同样，

这些式子可以通过乘以转移概率并求k − 1次积分来一般化到任意的将来时间n + k。

周期性

边际分布 P(Xn)是在时间为n时的状态的分布。初始分布为P(X0)。该过程的变化可以用以下的一个时

间步幅来描述：

这是Frobenius-Perron equation的一个版本。这时可能存在一个或多个状态分布π

满足

其中Y只是为了便于对变量积分的一个名义。这样的分布π被称作是“平稳分布”（Stationary

Distribution）或者“稳态分布”（Steady-state Distribution）。一个平稳分布是一个对应于特征值为1的条件分布函数的特征方程。

平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”。

重现性

各态历遍性

各态历经性

律动性

平稳状态分析和极限分布

可反转马尔可夫链

可反转马尔可夫链类似于应用贝叶斯定理来反转一个条件概率

以上就是反转的马尔可夫链。因而，如果存在一个π，使得

所以，对于可反转马尔可夫链，π总是一个平稳分布。

有限状态空间中的马尔可夫链

如果状态空间是有限的，则转移概率分布可以表示为一个具有(i,j)元素的矩阵，称之为“转移矩阵”

：是一步转移矩阵，就是.不可约，并且是非周期的，则

,收

独立于初始分布π。这是由Perron-Frobenius theorem所指出的。

正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵。

注意：在上面的定式化中，元素(i,j)是由j转移到i的概率。有时候一个由元素(i,j)给出的等价的定式化等于由i转移到j的概率。在此情况下，转移矩阵仅是这里所给出的转移矩阵的转置。另外，一个系统的平稳分布是由该转移矩阵的左特征矢量给出的，而不是右特征矢量。

转移概率独立于过去的特殊况为熟知的Bernoulli scheme。仅有两个可能状态的Bernoulli scheme被熟知为伯努利过程

科学应用

统计

马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。

生物

马尔可夫链也有众多的生物学应用，特别是增殖过程，可以帮助模拟生物增殖过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。

地理

马尔可夫链最近的应用是在地理统计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程中。

因特网应用

谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的。马尔可夫模型也被应用于分析用户浏览网页的行为。一阶或者二阶的马尔可夫模型可以用于对一个用户从某一网络链接转移到另一链接的行为进行建模，然后这些模型可以用于对用户之后的浏览行为进行预测。

马尔可夫模仿文本生成器

马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件。马尔可夫链还被用于谱曲。

参看

■马尔可夫性质

■马尔可夫

■隐马尔可夫模型

参考文献

■A.A. Markov.

w页码，5/5(W)外部链接

■免费的《概率论入门》书中有关马尔可夫链的章节

(http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf)

■生成文本 (http://www.cs.bell-labs.com/cm/cs/pearls/sec153.html) (有关使用马尔可夫链产生随机文本)■世界上最大的矩阵计算

(http://www.mathworks.com/company/newsletters/news_notes/clevescorner/oct02_cleve.html) (Google's

PageRank as the stationary distribution of a random walk through the Web.)■Disassociated Press (http://www.gnu.org/software/emacs/manual/html_node/Dissociated-Press.html) in Emacsapproximates a Markov process

■[1] (http://rapt.us/toys/chain.pl) Markov chains used to produce semi-coherentEnglish.

■有关马尔可夫链的资源列表 (http://www.compression-links.info/Markov)

来自“http://zh.wikipedia.org/w/index.php?title=%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE&oldid=18203744” 2个分类: 概率论随机过程

■本页面最后修订于2011年10月31日(星期一) 12:48。

■本站的全部文字在知识共享署名-相同方式共享3.0协议之条款下提供，附加条款亦可能应用。（请参阅使用条款）

Wikipedia和维基百科标志是维基媒体基金会的注册商标；维基是维基媒体基金会的商标。

维基媒体基金会是在美国佛罗里达州登记的501(c)(3)免税、非营利、慈善机构。