马尔可夫链（Markov Chain）

提出者：张超

来自知乎：数值策划备忘录——用容斥原理解决套装收集问题

说明

假设小明每个小时只做三件事情，吃饭，睡觉，打游戏，并且他做完某件事之后会做什么事情的概率是固定的，那么我们就可以用马尔可夫链，预测他之后在每个时间段做某件事情的概率。

这样一来我们就得到了一个小明的做事规律的状态转移矩阵

如果小明现在在睡觉，也就是

那他下一个小时会做的事情的概率为

=

他在第n个小时之后做这三件事情的概率，只需要用他的初始状态

去乘n次他的做事规律的状态转移矩阵就行。

应用

通过这个例子，我们可以知道，马尔可夫链可以用来解决一些涉及概率和期望的数值问题，这里我们来尝试求解一下最经典的装备掉落问题：

每天可以刷四次副本，初始有20%掉落概率装备，如果没有掉落，则下一次掉落概率增加20%（掉落了则掉落概率回到20%），求平均每天可以掉落几件装备？

状态一指掉落概率为20%的这一状态

它有0.8的概率向状态二转移，也有0.2的概率回到自己原来的状态，即掉落装备

状态转移矩阵

初始状态

那么我们要求解的，刷四次副本后平均可以掉落几件装备，可以理解为刷每次副本掉落装备的概率之和。

我们用初始状态，去对状态转移矩阵做四次矩阵乘积，得到以下结果：

不论是从状态几，只要是回到状态一，即完成了一次装备掉落。

因此，0.2+0.36+0.424+0.4112=1.3952即为平均每天可以掉落的装备件数。

马尔可夫链模型（Markov Chain Model）

马尔可夫链因安德烈·马尔可夫（Andrey Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。

时间和状态都是离散的马尔可夫过程称为马尔可夫链, 简记为{X_n=X(n),n=0,1,2,\cdots}。

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

P(X_{n+1}=x|X_0,X_1,X_2,\cdots,X_n)=P(X_{n+1}=x|X_n)

这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。

马尔可夫在1906年首先做出了这类过程 。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。

马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。

马尔可夫链是满足下面两个假设的一种随机过程：

1、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；

2、从t时刻到t+l时刻的状态转移与t的值无关。一个马尔可夫链模型可表示为=(S，P，Q)，其中各元的含义如下：

1）S是系统所有可能的状态所组成的非空的状态集，有时也称之为系统的状态空间，它可以是有限的、可列的集合或任意非空集。本文中假定S是可数集(即有限或可列)。用小写字母i,j(或Si,Sj)等来表示状态。

2）P=[P_{ij}]{n\times n}是系统的状态转移概率矩阵，其中Pij表示系统在时刻t处于状态i，在下一时刻t+l处于状态i的概率，N是系统所有可能的状态的个数。对于任意i∈s，有\sum{j=1}^NP_{ij}=1。

3）Q=[q_1,q_2\cdots q_n]是系统的初始概率分布，qi是系统在初始时刻处于状态i的概率，满足\sum_{i=1}^Nq_i=1。