马可夫链

数学术语

马可夫链，因俄罗斯数学家安德烈·马可夫得名，是离散时间离散状态的马可夫过程。

简介

马可夫链，因俄罗斯数学家安德烈·马可夫（Андрей Андреевич Марков，1856年6月14日－1922年7月20日）得名，是离散时间离散状态的马可夫过程。在马可夫过程（具有无后效性）中，在给定当前知识或信息的情况下，只有当前的状态用来预测将来，过去（即当前以前的历史状态）对于预测将来（即当前以后的未来状态）是无关的。与马可夫链并列的马可夫过程有泊松过程（时间连续，状态离散）和维纳过程（时间连续，状态连续）。

而马可夫链的所涉及的时间和状态的分布都离散，于是，马可夫链可以看作一步一步、每一步对应不同状态的集合。在马可夫链的每一步，可以从一个状态变到另一个状态，也可以保持当前状态，状态的改变叫做过渡，与不同的状态改变相关的概率叫做过渡概率（一步转移概率）。例如，随机漫步就属于马可夫链。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的(无论之前漫步路径是如何的)。

历史背景

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

事实上，马可夫过程的提出前，人们观察到物理学中，很多确定性现象遵从如下演变原则：由时刻t0系统或过程所处的状态，可以决定系统或过程在时刻t＞t0所处的状态，而无须借助于t0以前系统所处的历史状态。如微分方程初值问题所描绘的物理过程就属于这类确定性现象。把上述原则延伸到随机现象，即当一物理系统或过程遵循的是以上原则或规律时，可引入统计规律概念“马可夫性”或“无后效性”。

定义

马可夫链(Markov Chains) ：

定义

马可夫链是随机变量的一个数列。令随机过程{Xn, n = 0, 1, 2, . . . , }取有限或可数的正值，除非特殊说明，该过程的可能值集合将由非负整数集合{0, 1, 2, . . .}来表示，当Xn = i 时我们称该过程在时间n时的状态为i.

P{Xn+1 = j|Xn = i,Xn−1 = in−1, . . . ,X1 = i1,X0 = i0} = Pij

假设该过程在状态i，它达到下一个状态j的概率是固定的。也就是说，对于所有的状态i0,i1,..i,j,以及所有的时间n＞=0,其概率可表示为：

P{Xn+1 = j|Xn = i,Xn−1 = in−1, . . . ,X1 = i1,X0 = i0} = Pij。

把满足这样条件的过程称为马可夫链Markov Chain。

等式的的意义可理解为：对于一个马科夫链，给定过去的状态X0,X1,...Xn-1和当前的状态Xn，任意未来状态Xn+1的条件分布与过去的状态是独立的，而仅仅与当前的状态相关。

Pij的值就是由当前的状态i进入未来状态j的概率。

例子

例1：

假设明天下雨的几率依赖今天是否下雨，而与过去的天气无关。假设如果今天下雨了明天下雨的概率是α，如果今天不下雨明天下雨的概率是β。

可以定义下雨时状态为0，不下雨时状态为1，那么以上描述的就是一个双态马可夫链问题，它的转移概率如下所示：

例2：

（构建一个马可夫链）假设今天是否下雨依赖于过去两天的天气情况。特别的，假设过去两天都下雨，那么明天下雨的概率是0.7，如果今天下雨昨天没下雨，那么明天下雨的概率是0.5，如果今天没下雨，昨天下了雨，明天下雨的概率是0.4，如果过去两天都没下雨，那么明天下雨的概率是0.2.

如果我们令时刻n+1的状态仅仅依赖于n时刻是否下雨，那么以上的描述就不是一个马可夫链。但是，我们可以构建一个马可夫链：任意时刻的状态是由过去两天的天气情况确定的。也就是说，这个随机过程有如下4种状态：

状态0 今天昨天都下雨了

状态1 今天下雨昨天没下雨

状态2 今天没下雨昨天下雨

状态3 今天昨天都没下雨

那么本例就表示了一个4态马可夫链，其转移概率矩阵如下所示：

例3：

（random walk 随机游走）对于满足状态空间为i = 0，±1,±2,...且Pi,i+1 = p = 1 − Pi,i−1, i = 0,±1, . . .其中0 ＜p ＜ 1。这样的马可夫链称为随机游走。该模型可以用来描述一个人在一条直线上行走，在任意一个点他往右的概率p或往左走的概率为1-p。

例4：

假设有无穷多个瓶子，我们当前标以0,1，每一个瓶子放不同个数球，每瓶中的球都标以B0的B1，B2，等（不同的球可以有相同的“编号），假设我们从标以0的瓶中随便抽一个球，则此球的“编号什么BJ，我们再从第j个瓶中抽取-球，若此球”编号什么BK，我们当前再从第ķ个瓶中抽取一球，……这样一直做下去，我们就得到一个马可夫链。原因和前面几个例子相同。事实上任一个马可夫链都和这个模型等价，我们只要适当的选取每个瓶中球的个数，同时加以适当的编号，我们就可得取第一和第二个例子。

例5：

考虑以下股票模式，若股票上涨则明天会上涨的几率为0.7;若股价下跌则明天会上涨的几率为0.5。

这是一个马可夫链，状态0代表上涨，而状态1代表股票下跌。

转换矩阵为：

0.7 0.3

P= 0.5 0.5

假设一个赌者有$1，而且每次赌赢$1的几率为p，或赌输$1的几率为1-p。

这个赌博当其中一位赌者累积为$3或破产($0)就停止。

这个模式是马可夫链，状态相当于赌者手上的钱，即$0,$1,$2,$3，及其转换矩阵为：1 0 0 0

1-p 0 p 0

p= 0 1-p 0 p

0 0 0 1