Introduction to Markov chain

马尔可夫链(Markov chain)是数学建模和机器学习常用的工具(据说尤其在NLP中,我目前尚不了解很多,但之前曾看过一篇用简单的马尔可夫链实现一个鸡汤生成器的博文,有兴趣的朋友可以看看)。这篇文章将对它做一个简单的介绍。

以下内容为本人在参考了一些资料后的原创,因此版权属于本人。欢迎转载,但请标明原作者和原链接。

由于内容比较繁多,我将在未来一段时间内完成这篇文章。

另注:根据作者测试,本文在移动端存在一个问题:公式无法显示完全。 解决办法是点击公式,使其出现选择框;长按至出现选项;选择Math Settings 里的 Scale All Math... 将scale调为大概50%,即可显示完全。

如下图所示:

image_1c52vkbaacsv1euj1eqabv61b2rm.png-67.5kB

什么是Markov chain?

定义

维基百科上给出的定义如下:

马尔可夫链(英语:Markov chain),又称离散时间马尔可夫链(discrete-time Markov chain,缩写为DTMC),因俄国数学家安德烈·马尔可夫(俄语:Андрей Андреевич Марков)得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。

而用形式化的语言描述则为:
当等式两边的条件概率都有意义时,
$$P(X_{n+m} = j\space| X_{n} = i, X_{n-1} = i_{n-1},…X_{1} = i_{1} ) = P(X_{n+m} = j\space| X_{n} = i)$$
$m = 1$ 时等式成立,则随机变量序列 $X_n$ 是一个马尔可夫链, $X_i$ 的可能值构成的可数集称为该链的状态空间(state space)

定义的推论

使用数学归纳法容易证明, 若 $m = 1$时 上式成立,则 $m$ 为任意正整数都成立。
要完成这个证明,我们先证明这样一个引理:

引理1 $P(A|B) = \sum P(A|B\cap C_i)\times P(C_i|B)$
其中,$\sum P(C_i) = 1$。

证明

$$\sum P(A|B\cap C_i)\times P(C_i|B)=\sum \frac{P(A\cap B\cap C_i)}{P(B\cap C_i)}\times P(C_i|B)= \sum \frac{P(A\cap B\cap C_i)}{P(B)P(C_i|B)}\times P(C_i|B) \\= \sum \frac{P(A\cap B\cap C_i)}{P(B)} = \frac{\sum P(A\cap B \cap C_i)}{P(B)} = \frac{P(A\cap B)}{P(B)}= P(A|B)$$

引理1,我们有:
$$P(X_{n+m+1} = k\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1 )\\=\sum_{k’ \in S}P(X_{n+m+1} = k\space|X_{n+m}=k’,X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1)\\ \times P(X_{n+m}=k’\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1)$$

这里我们已经知道 $m = 1$ 时是成立的,那么
$$P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\=P(X_{n+m+1} = k\space| X_{n+m} = k’)\\=P(X_{n+m+1} = k\space| X_{n+m} = k,X_{n} = i_{n})$$
这个等式成立是因为 $X_{n+m+1}$ 只与 $X_{n+m}$ 有关,至于我们为什么要引入 $X_{n} = i$,稍后再说。

对于乘号右边的 $P(X_{n+m}=k’\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1)$, 根据归纳假设,有:
$ P(X_{n+m}=k’\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1) = P(X_{n+m} = k’\space|X_n=i_n)$

于是,上面的等式可以改写为:
$$ P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\ =\sum_{k’\in S} P(X_{n+m+1} = k\space| X_{n+m} = k’,X_{n} = i_{n}) \times P(X_{n+m} = k’\space|X_n=i_n) $$

接下来我们证明第二个引理:

引理2: $P(A\cap B|C) = P(A|B\cap C) \times P(B|C)$

证明
$$P(A|B\cap C) \times P(B|C) = \frac{P(A\cap B\cap C)}{P(B\cap C)}\times \frac{P(B\cap C)}{P(C)} = \frac{P(A\cap B\cap C)}{P(C)} = P(A\cap B|C)$$

写到这里,刚才我们引入 $X_{n} = i$ 的目的就很显然了。我们可以将刚才的等式再次改写为:
$$ P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\ =\sum_{k’\in S} P(X_{n+m+1} = k\space| X_{n+m} = k’,X_{n} = i_{n}) \times P(X_{n+m} = k’\space|X_n=i_n) \\ =\sum_{k’\in S} P(X_{n+m+1} = k,X_{n+m} = k’\space|X_{n} = i_{n})\\= P(X_{n+m+1} = k\space|X_n=i_n)$$

这样,我们证明了,如果$m = 1$等式成立, 当$m$为任意正整数时,该等式都成立。

概率转移矩阵

开普曼-柯尔莫哥洛夫公式

刚刚我们分析的正是马尔可夫链的第一个性质:马氏性
接下来我们要讨论另一个性质:时齐性(time-homogeneity)
时齐性是指,系统由状态 $i$ 到状态 $j$ 的转移概率只依赖于其时间间隔的长短,与起始时间无关
用形式化的语言描述:
$$P(X_{n+m} = j\space | X_{n} = i) = P(X_{n+m+k} = j\space | X_{n+k} = i)$$

既然与起始时间 $n$ 无关, 那我们就可以将概率 $P(X_{n+m} = j\space | X_{n} = i)$ 写作 $P_{ij}(m)$ 。

需要注意的是,时齐性是我们的假设,而非能通过数学推导得出的性质。我们做出这个假设是因为它符合我们现实生活中的场景。

对于符合时齐性的马尔可夫链,我们可以定义这样一个概率转移矩阵$P(m)$:
$P(m)$ 是以 $m$ 步转移概率$P_{ij}(m)$为元素的矩阵(即 $(P(m))_{ij} = P_{ij}(m)$,也称为该链的 $m$ 步转移矩阵。通常记 $P(1)$ 为 $P$。

它具有以下几个性质:

  • $\forall i,j\in S, 0 < P_{ij}(m) < 1$ .

  • $\displaystyle{\forall i, \sum_{j\in S} P_{ij}(m) = 1}$ 换句话说, $P(m)$ 的每一行都是在 $S$ 上的一个概率分布。

  • $P(0)$ 是一个单位矩阵。

以上几个性质比较显然,这里就不做更多说明。

这里要重点提到的是开普曼-柯尔莫哥洛夫公式(The Chapman-Kolmogorov Equations)

$ \forall m,n, P(m+n) = P(m)P(n)\\$ 亦即,$\forall m,n, P_{ij}(m+n) = \displaystyle{\sum_{k\in S}P_{ik}(m)P_{kj}(n)}$

证明:由引理1

$$\displaystyle{P_{ij}(m+n) = P(X_{m+n+1} = j \space| X_1 = i)\\ = \sum_{k\in S}P(X_{m+n+1} = j |X_{m+1} = k, X_1 = i)\times P(X_{m+1} = k\space|X_1 = i)\\=\sum_{k\in S}P_{ik}(m)P_{kj}(n)}$$

由此,我们能得到以下两个推论:

推论1: $ P(n) = P(n-1)P(1) = P(n-2)P(1)^2 = …P(1)^n = P^n$

推论2: 如果我们设初始的概率分布为 $P^{(0)} $(行向量), 那么经过了 $n$ 个步骤后的概率分布 $P^{(n)} = P^{(0)}P(n) = P^{(0)}P^n$

极限概率分布

我们知道,概率分布矩阵的每个元素都属于$[0,1]$, 那么很自然地,我们就会想知道:

对其求 $n$ 次幂后得到的 $P^n$, 是否有极限呢?

对于有限的随机序列 $X_n$, $P$ 和 $P^n$ 都是大小有限的方阵。这意味着我们也许可以用单纯的线性代数思想来解决这个问题。

线性代数的角度

纯粹从线性代数的角度来看这个问题,我们的 $P$ 具有什么性质呢?

  1. 所有元素均为非负数。
  2. 每行元素和为 $1$。

在这样性质的基础上,下面我们证明:

  1. $P$ 的任意一个特征值 $\lambda$ 满足 $ |\lambda| <= 1$。
  2. $P$ 有特征值 $1$, 且非重根。

证明

  1. 令 $\lambda$ 对应的特征向量 $x = (x_1, x_2,...x_n)^T$, 设 $x_i = max\{x_1,x_2...,x_n\}$。

    由于 $Px = \lambda x$, $(Px)_{i} = \displaystyle{\sum_{j=1}^n a_{ij}x_{j}} = \lambda x_i$

    两边同时取绝对值,有 $|\lambda| |x_i| = |\displaystyle{\sum_{j=1}^n a_{ij}x_{j}}|\\\leqslant \displaystyle{\sum_{j=1}^n a_{ij}|x_{j}}| \leqslant \displaystyle{(\sum_{j=1}^n a_{ij})|x_i| = x_i}$

    因此 $\lambda \leqslant 1$。

  2. 很容易发现 $1$ 是一个特征值,我们只需要取 $x = (1,1,..1)^T$,就可以很容易地发现 $Px = x$。

    因此我们需要证明的是 $1$ 不是重根。

    采用反证法

    我们已经知道 $1$ 是一个特征值,如果他是重根的话,那么 $det(P-\lambda I)$ 中至少有两个 $(1-\lambda)$ 的因子。

    对于 $det(P-\lambda I)$ , 我们把每一列的数字累加到第 $n$ 列,可使第 $n$ 列全为 $(1-\lambda)$,这里我们可以提出第一个因子。这时行列式最右一列均为 $1$, 一个很自然的想法是,前 $n -1 $ 行减去第 $n$ 行:这样第 $n$ 列就只有一个非零元了。按第 $n$ 列展开,我们得到 $det(P-\lambda I) = (1-\lambda) det(Q-\lambda I’)$。其中$Q$ 为 $n-1$ 阶方阵,且$Q_{ij} = a_{ij} - a_{nj}$;$I’$ 是 $n-1$ 阶单位矩阵。这是很容易验证的。

    这时候 $Q$ 必有特征值 $1$.

    接下来我们考虑 $Q$ 关于 $1$ 的行特征向量(注意是行特征向量,即 $Q^T$ 的列特征向量)$\beta = (\beta_1,\beta_2,..\beta_{n-1})$。

    我们有 $$(\beta Q)_j = \displaystyle{\sum_{i=1}^{n-1}\beta_i(a_{ij}-a_{nj})=\beta_j}$$

    接下来讨论 $\beta$ 中元素的正负性。设有 $p$ 个正元素(分别为 $\beta_{s_1},\beta_{s_2},..\beta_{s_p}$); $q$ 个非正元素(分别为$\beta_{t_1},\beta_{t_2},..\beta_{t_q}$)。另外我们不妨设$\rho = |\beta|\geqslant 0$;因为如果小于 $0$, 我们可以取 $-\beta$ 作为我们讨论的对象。

    这样,对 $\beta$ 中的正元素,我们可以将上面的式子改写为:

    $$ \displaystyle{\sum_{i=1}^{n-1}\beta_ia_{it_k}-\rho a_{nt_k}=\beta_{t_k}}\space\space (k = 1,2,...p)$$ 累加,得到: $$ \displaystyle{\sum_{i=1}^{n-1}\beta_i(\sum_{k = 1}^{p}a_{it_k})-\rho( \sum_{k=1}^{p}a_{nt_k})=\sum_{k=1}^p\beta_{t_k}}$$

    为了简化式子,不妨令 $d_i = \displaystyle{\sum_{k=1}^{p}a_{it_k} < \sum_{i=1}^{n}a_i = 1}$ :

    $$ \displaystyle{\sum_{i=1}^{n-1}\beta_id_i-\rho d_n=\sum_{k=1}^p\beta_{t_k}}$$ $$ \displaystyle{\sum_{k=1}^{p}\beta_{s_k}d_{s_k} + \sum_{k=1}^{q}\beta_{t_k}d_{t_k}-\rho d_n=\sum_{k=1}^p\beta_{t_k}}$$ $$ \displaystyle{\sum_{k=1}^{q}\beta_{t_k}d_{t_k}-\rho d_n=\sum_{k=1}^p\beta_{t_k} - \sum_{k=1}^{p}\beta_{s_k}d_{s_k} > 0}$$

    而等式左边显然是负数,矛盾。这说明 $Q$ 没有特征值 $1$, 也就是说 $P$ 的特征值 $1$ 无重根。

回到我们对极限的讨论。如果这个极限 $L$ 存在,那么它会满足:$$LP = L$$

也就是说它的每一行都是 $P$ 关于特征值 $1$ 的行特征向量; 我们刚刚证明$1$ 这个特征值无重根,那么这个行特征向量是唯一的。

—— 是的, $L$ 的每一行都相同,均为 $P$ 关于 $1$ 的行特征向量。

极限何时存在?

【 最近事务繁多,更新无限期推迟】

有任何错误,请在评论区指正或者给我发邮件。(评论使用Disqus系统,可能需要翻墙)

This blog is under a CC BY-NC-SA 3.0 Unported License
Link to this article: http://huangweiran.club/2018/01/29/Introduction to Markov chain/