区块链技术博客
www.b2bchain.cn

【算法模型】S07E14 状态转移:马尔科夫链初步求职学习资料

本文介绍了【算法模型】S07E14 状态转移:马尔科夫链初步求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

1.回顾两类重要的随机过程

在上一小节随机过程的概述中,我们提到过两类非常非常典型且重要的随机过程,一类是:伯努利过程和泊松过程,这一类随机过程是无记忆性的,也就是说未来的状态不依赖于过去的状态:新的“成功”或“到达”不依赖于该过程过去的历史情况。

而另一类则正好相反,未来的情况会依赖于过去的情况,并且能够在某种程度上通过过去发生的情况去预测未来,例如这一节我们的核心内容:马尔科夫过程,他在许许多多的领域都有深入和广泛的应用。

2.离散时间的马尔科夫链

2.1.马尔科夫链三要素

这是一类随着时间而发生状态变换的过程,因此分为离散时间的马尔科夫链和连续时间的马尔科夫链两类。我们首先考虑离散时间的马尔科夫链,他的状态在确定的离散时间点上发生变化。

离散时间的马尔科夫链有三个核心概念点:离散时间、状态空间、转移概率

在离散时间的马尔科夫链中,我们通常使用$n$来表示时刻,用$X_n$来表示马尔科夫链在此时的状态,那么马尔科夫链所有的状态会构成一个如下的集合$S=left{ 1,…,m right}$,这个集合$S$我们把他称作是这个离散时间马尔科夫链的状态空间。

那么,在这个状态空间的基础之上,我们来讨论马尔科夫链的第二个概念:转移概率。转移概率是这么描述的:当离散时间的马尔科夫链当前的状态是$i$ 时,下一个状态等于$j$的概率就是转移概率,我们记作是$p_{ij}$。

转移概率$p_{ij}$本质上用一个条件概率就可以表达:

$p_{ij}=P(X_{n+1}=j|X_n=i),i,jin S$

我们举一个拥有三个状态的离散时间马尔科夫链,他的转移概率图如下:

【算法模型】S07E14 状态转移:马尔科夫链初步

图1.三状态离散时间马尔科夫链状态转移图

在这幅图中标明的是张三的三种状态,每天他都处于这三种状态中的一种:要么宅在家中,要么在外面运动,要么则是在网红点吃美食。这就是张三的状态空间,如果今天张三宅在家中,明天他仍然宅在家中的概率是$0.2$,明天出去吃美食的概率是$0.6$,明天出去运动的概率是$0.2$,这就是他的几个转移概率。

2.2.马尔科夫性

如果我们说离散时间、状态空间和转移概率是离散时间马尔科夫链的构成要素,那么马尔科夫性则是他的灵魂特征。

这个特性具体描述为:只要时刻$n$马尔科夫链的状态为$i$,不论过去发生了什么,也不论马尔科夫链是如何到达状态$i$的,下一个时刻$n+1$转移到状态$j$的概率一定都是转移概率$p_{ij}$ 。

我们还是用上面的图例来说明,比如张三今天是在吃美食,那么不管他昨天是在运动还是宅在家中,他明天出去运动的概率都不变,就是$0.3$,出去继续吃美食的概率也不变,还是$0.6$。概况的说来就是:下一个状态只与当前状态有关,而与更早的历史状态无关。

语言上七七八八的说了这么多,又是举例子、又是理论术语的,其实落实在数学语言的表达上,还是一个条件概率等式的事儿:

即对任意的时刻$n$,对状态空间中的任意状态$i,jin S$,以及时刻$n$前(也就是历史上的)任意可能的状态序列$i_0,…,i_{n-1}$ ,均有:

$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=P(X_{n+1}=j|X_n=i)=p_{ij}$

很清楚也很直白:下一个状态$X_{n+1}$的概率分布只依赖于前一个状态 $X_n$ 。

2.3.转移概率和状态转移矩阵

那么问题来了,这个转移概率$p_{ij}$具有什么样的性质?首先$p_{ij}$满足非负性,这是必须的。

其次再有:$sum_{j=1}^{m}{p_{ij}}=1$ ,这个等式对所有的$i$都成立。这个其实很好理解,我们还是对照着上面那个张三的状态图来看。比如他今天宅在家中,那么他明天继续宅在家中的概率是$0.2$,明天出去运动的概率是$0.2$,明天出去吃美食的概率是$0.6$,不管这三个概率如何取值,如何分配,有一点是肯定的,就是三者相加必须等于$1$。

我们关注一下这里特殊一点的情况,即当$i=j$时,$p_{ii}$的取值问题。其实就是对应了张三今天宅在家中,明天继续宅在家中的情况。虽然状态没有发生变化,但是我们可以认为是状态发生了一次特殊的转移,也就是自身转移。

在状态空间$S$中,任意两个状态$i$和$j$之间都有一个转移概率$p_{ij}$,并且满足$p_{ij} ge 0$(当状态$i$无法转移到状态$j$的时候,$p_{ij}=0$)。那么我们可以把状态空间中的状态间的所有转移概率按照顺序组织成一个二维矩阵,其中第$i$行、第$j$列的元素就是$p_{ij}$,那么这个二维矩阵$begin{bmatrix}p_{11}&p_{12}&…&p_{1m}\p_{21}&p_{22}&…&p_{2m}\…&…&…&…\p_{m1}&p_{m2}&…&p_{mm}end{bmatrix}$,就称为是转移概率矩阵,他刻画了对应的马尔科夫链的本质。

我们沿用张三的例子:我们令状态$1$为宅在家中;状态$2$为运动;状态$3$ 为吃美食,那么这个马尔科夫链就是是一个$3 times 3$的$2$维矩阵 $begin{bmatrix}0.2&0.2&0.6\0.2&0.1&0.7\0.1&0.3&0.6end{bmatrix}$

3.马尔科夫链性质的总结

到这里,我们有必要停下来梳理一下马尔科夫链的最基本性质,一个马尔科夫链由以下主要特征确定:

第一是状态集合$S=left{ 1,2,…,m right}$;

第二是可能发生状态转移的$(i,j)$的集合,即那些$p_{ij}>0$的状态对;

第三是$p_{ij}$的取值。

而这三点都可以最终由一个二维的转移概率矩阵所描述。

并且由该上述特征所描述的马尔科夫链是一个随机变量序列 $X_0,X_1,X_2,……$ ,他们取值于状态空间$S$,并且满足:对于任意的时间$n$,所有状态$i,jin S$ ,以及之前所有可能的状态序列$i_0,…,i_{n-1}$,均有$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=p_{ij}$。

4.一步到达与多步转移

4.1.多步转移的描述

刚才我们花大篇幅介绍的转移概率$p_{ij}$给出的是从状态$i$一步到达状态$j$ 的转移概率$p_{ij}=P(X_{n+1}=j|X_n=i)$。那么我们进一步拓展呢,我们不是通过一步,而是通过$m$步(其中 $m>1$)从状态$i$转移到状态$j$,那么这个对应的就是$m$步状态转移的概率。

写成条件概率的形式就是:

$p^{m}(i,j)=P(X_{n+m}=j|X_n=i)$

4.2.一个阶级流动性的例子

这里我们换一个例子来看看,社会的流动性问题是大家都非常关注的一个问题,社会的流动性强,社会的底层通过自身的努力使得家族向社会中层甚至上层流动是社会始终保持活力重要推动力。

社会学中就有一个非常有名的反映社会阶层流动的马尔科夫链,在这个马尔科夫链的状态空间中,有三个状态,状态$1$是处于贫困水平,状态$2$是中产阶级,状态$3$是财富自由,他的状态转移矩阵为:$begin{bmatrix}0.7&0.2&0.1\0.3&0.5&0.2\0.2&0.4&0.4end{bmatrix}$。

我们不讨论这里面数据的合理性和准确性,单单就事论事,如$p_{13}=0.1$,表示如果这一代人处于贫困水平,下一代人想成为财富自由的概率为$0.1$,而继续处于贫困水平的概率要大得多,为$0.7$。而如果这一代人处于财富自由的水平,那么他的下一代处于财富自由的概率也要大不少,为$0.4$。

那么,我们现在思考这么一个问题,假设爷爷处于贫困水平(状态1),那么父亲处于中产阶级(状态2),而你处于财富自由水平(状态3)的概率有多大?

从哪里入手呢?还是紧扣定义,从条件概率表达式入手:

$P(X_2=3,X_1=2|X_0=1)= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_0=1)}$ $= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_1=2,X_0=1)}cdotfrac{P(X_1=2,X_0=1)}{P(X_0=1)}$ $=P(X_2=3|X_1=2,X_0=1) cdot P(X_1=2|X_0=1)$

由于这是一个马尔科夫链,因此满足:

$P(X_2=3|X_1=2,X_0=1)=P(X_2=3|X_1=2)$

因此有:

$P(X_2=3,X_1=2|X_0=1)=P(X_2=3|X_1=2)P(X_1=2|X_0=1)$。

对应到转移概率矩阵中,就是从状态$1$转移到状态$2$的概率乘以从状态$2$转移到状态$3$的概率:$p_{12} p_{23}=0.2 cdot 0.2 = 0.04$。

接下来我们不指定父亲的状态,只看这么一个问题,就是假设爷爷是贫困水平(状态$1$),问孙子处于财富自由(状态$3$)状态的概率有多大?

那么这里只指定了爷爷和孙子所处的状态,那么父亲这一代可以是处于贫穷、中产和财富自由中的任意一种状态,那么这个概率的表达式写起来也很简单:

$P(X_2=3|X_0=1)$ $=P(X_2=3,X_1=1|X_0=1)+P(X_2=3,X_1=2|X_0=1)+P(X_2=3,X_1=3|X_0=1)$ $=p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33}=sum_{k=1}^3{p_{1k}p_{k3}}$ $=0.7cdot 0.1+0.2cdot 0.2+0.1cdot 0.4=0.15$

4.3.多步转移与矩阵乘法

1.回顾两类重要的随机过程

在上一小节随机过程的概述中,我们提到过两类非常非常典型且重要的随机过程,一类是:伯努利过程和泊松过程,这一类随机过程是无记忆性的,也就是说未来的状态不依赖于过去的状态:新的“成功”或“到达”不依赖于该过程过去的历史情况。

而另一类则正好相反,未来的情况会依赖于过去的情况,并且能够在某种程度上通过过去发生的情况去预测未来,例如这一节我们的核心内容:马尔科夫过程,他在许许多多的领域都有深入和广泛的应用。

2.离散时间的马尔科夫链

2.1.马尔科夫链三要素

这是一类随着时间而发生状态变换的过程,因此分为离散时间的马尔科夫链和连续时间的马尔科夫链两类。我们首先考虑离散时间的马尔科夫链,他的状态在确定的离散时间点上发生变化。

离散时间的马尔科夫链有三个核心概念点:离散时间、状态空间、转移概率

在离散时间的马尔科夫链中,我们通常使用$n$来表示时刻,用$X_n$来表示马尔科夫链在此时的状态,那么马尔科夫链所有的状态会构成一个如下的集合$S=left{ 1,…,m right}$,这个集合$S$我们把他称作是这个离散时间马尔科夫链的状态空间。

那么,在这个状态空间的基础之上,我们来讨论马尔科夫链的第二个概念:转移概率。转移概率是这么描述的:当离散时间的马尔科夫链当前的状态是$i$ 时,下一个状态等于$j$的概率就是转移概率,我们记作是$p_{ij}$。

转移概率$p_{ij}$本质上用一个条件概率就可以表达:

$p_{ij}=P(X_{n+1}=j|X_n=i),i,jin S$

我们举一个拥有三个状态的离散时间马尔科夫链,他的转移概率图如下:

【算法模型】S07E14 状态转移:马尔科夫链初步

图1.三状态离散时间马尔科夫链状态转移图

在这幅图中标明的是张三的三种状态,每天他都处于这三种状态中的一种:要么宅在家中,要么在外面运动,要么则是在网红点吃美食。这就是张三的状态空间,如果今天张三宅在家中,明天他仍然宅在家中的概率是$0.2$,明天出去吃美食的概率是$0.6$,明天出去运动的概率是$0.2$,这就是他的几个转移概率。

2.2.马尔科夫性

如果我们说离散时间、状态空间和转移概率是离散时间马尔科夫链的构成要素,那么马尔科夫性则是他的灵魂特征。

这个特性具体描述为:只要时刻$n$马尔科夫链的状态为$i$,不论过去发生了什么,也不论马尔科夫链是如何到达状态$i$的,下一个时刻$n+1$转移到状态$j$的概率一定都是转移概率$p_{ij}$ 。

我们还是用上面的图例来说明,比如张三今天是在吃美食,那么不管他昨天是在运动还是宅在家中,他明天出去运动的概率都不变,就是$0.3$,出去继续吃美食的概率也不变,还是$0.6$。概况的说来就是:下一个状态只与当前状态有关,而与更早的历史状态无关。

语言上七七八八的说了这么多,又是举例子、又是理论术语的,其实落实在数学语言的表达上,还是一个条件概率等式的事儿:

即对任意的时刻$n$,对状态空间中的任意状态$i,jin S$,以及时刻$n$前(也就是历史上的)任意可能的状态序列$i_0,…,i_{n-1}$ ,均有:

$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=P(X_{n+1}=j|X_n=i)=p_{ij}$

很清楚也很直白:下一个状态$X_{n+1}$的概率分布只依赖于前一个状态 $X_n$ 。

2.3.转移概率和状态转移矩阵

那么问题来了,这个转移概率$p_{ij}$具有什么样的性质?首先$p_{ij}$满足非负性,这是必须的。

其次再有:$sum_{j=1}^{m}{p_{ij}}=1$ ,这个等式对所有的$i$都成立。这个其实很好理解,我们还是对照着上面那个张三的状态图来看。比如他今天宅在家中,那么他明天继续宅在家中的概率是$0.2$,明天出去运动的概率是$0.2$,明天出去吃美食的概率是$0.6$,不管这三个概率如何取值,如何分配,有一点是肯定的,就是三者相加必须等于$1$。

我们关注一下这里特殊一点的情况,即当$i=j$时,$p_{ii}$的取值问题。其实就是对应了张三今天宅在家中,明天继续宅在家中的情况。虽然状态没有发生变化,但是我们可以认为是状态发生了一次特殊的转移,也就是自身转移。

在状态空间$S$中,任意两个状态$i$和$j$之间都有一个转移概率$p_{ij}$,并且满足$p_{ij} ge 0$(当状态$i$无法转移到状态$j$的时候,$p_{ij}=0$)。那么我们可以把状态空间中的状态间的所有转移概率按照顺序组织成一个二维矩阵,其中第$i$行、第$j$列的元素就是$p_{ij}$,那么这个二维矩阵$begin{bmatrix}p_{11}&p_{12}&…&p_{1m}\p_{21}&p_{22}&…&p_{2m}\…&…&…&…\p_{m1}&p_{m2}&…&p_{mm}end{bmatrix}$,就称为是转移概率矩阵,他刻画了对应的马尔科夫链的本质。

我们沿用张三的例子:我们令状态$1$为宅在家中;状态$2$为运动;状态$3$ 为吃美食,那么这个马尔科夫链就是是一个$3 times 3$的$2$维矩阵 $begin{bmatrix}0.2&0.2&0.6\0.2&0.1&0.7\0.1&0.3&0.6end{bmatrix}$

3.马尔科夫链性质的总结

到这里,我们有必要停下来梳理一下马尔科夫链的最基本性质,一个马尔科夫链由以下主要特征确定:

第一是状态集合$S=left{ 1,2,…,m right}$;

第二是可能发生状态转移的$(i,j)$的集合,即那些$p_{ij}>0$的状态对;

第三是$p_{ij}$的取值。

而这三点都可以最终由一个二维的转移概率矩阵所描述。

并且由该上述特征所描述的马尔科夫链是一个随机变量序列 $X_0,X_1,X_2,……$ ,他们取值于状态空间$S$,并且满足:对于任意的时间$n$,所有状态$i,jin S$ ,以及之前所有可能的状态序列$i_0,…,i_{n-1}$,均有$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=p_{ij}$。

4.一步到达与多步转移

4.1.多步转移的描述

刚才我们花大篇幅介绍的转移概率$p_{ij}$给出的是从状态$i$一步到达状态$j$ 的转移概率$p_{ij}=P(X_{n+1}=j|X_n=i)$。那么我们进一步拓展呢,我们不是通过一步,而是通过$m$步(其中 $m>1$)从状态$i$转移到状态$j$,那么这个对应的就是$m$步状态转移的概率。

写成条件概率的形式就是:

$p^{m}(i,j)=P(X_{n+m}=j|X_n=i)$

4.2.一个阶级流动性的例子

这里我们换一个例子来看看,社会的流动性问题是大家都非常关注的一个问题,社会的流动性强,社会的底层通过自身的努力使得家族向社会中层甚至上层流动是社会始终保持活力重要推动力。

社会学中就有一个非常有名的反映社会阶层流动的马尔科夫链,在这个马尔科夫链的状态空间中,有三个状态,状态$1$是处于贫困水平,状态$2$是中产阶级,状态$3$是财富自由,他的状态转移矩阵为:$begin{bmatrix}0.7&0.2&0.1\0.3&0.5&0.2\0.2&0.4&0.4end{bmatrix}$。

我们不讨论这里面数据的合理性和准确性,单单就事论事,如$p_{13}=0.1$,表示如果这一代人处于贫困水平,下一代人想成为财富自由的概率为$0.1$,而继续处于贫困水平的概率要大得多,为$0.7$。而如果这一代人处于财富自由的水平,那么他的下一代处于财富自由的概率也要大不少,为$0.4$。

那么,我们现在思考这么一个问题,假设爷爷处于贫困水平(状态1),那么父亲处于中产阶级(状态2),而你处于财富自由水平(状态3)的概率有多大?

从哪里入手呢?还是紧扣定义,从条件概率表达式入手:

$P(X_2=3,X_1=2|X_0=1)= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_0=1)}$ $= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_1=2,X_0=1)}cdotfrac{P(X_1=2,X_0=1)}{P(X_0=1)}$ $=P(X_2=3|X_1=2,X_0=1) cdot P(X_1=2|X_0=1)$

由于这是一个马尔科夫链,因此满足:

$P(X_2=3|X_1=2,X_0=1)=P(X_2=3|X_1=2)$

因此有:

$P(X_2=3,X_1=2|X_0=1)=P(X_2=3|X_1=2)P(X_1=2|X_0=1)$。

对应到转移概率矩阵中,就是从状态$1$转移到状态$2$的概率乘以从状态$2$转移到状态$3$的概率:$p_{12} p_{23}=0.2 cdot 0.2 = 0.04$。

接下来我们不指定父亲的状态,只看这么一个问题,就是假设爷爷是贫困水平(状态$1$),问孙子处于财富自由(状态$3$)状态的概率有多大?

那么这里只指定了爷爷和孙子所处的状态,那么父亲这一代可以是处于贫穷、中产和财富自由中的任意一种状态,那么这个概率的表达式写起来也很简单:

$P(X_2=3|X_0=1)$ $=P(X_2=3,X_1=1|X_0=1)+P(X_2=3,X_1=2|X_0=1)+P(X_2=3,X_1=3|X_0=1)$ $=p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33}=sum_{k=1}^3{p_{1k}p_{k3}}$ $=0.7cdot 0.1+0.2cdot 0.2+0.1cdot 0.4=0.15$

4.3.多步转移与矩阵乘法

1.回顾两类重要的随机过程

在上一小节随机过程的概述中,我们提到过两类非常非常典型且重要的随机过程,一类是:伯努利过程和泊松过程,这一类随机过程是无记忆性的,也就是说未来的状态不依赖于过去的状态:新的“成功”或“到达”不依赖于该过程过去的历史情况。

而另一类则正好相反,未来的情况会依赖于过去的情况,并且能够在某种程度上通过过去发生的情况去预测未来,例如这一节我们的核心内容:马尔科夫过程,他在许许多多的领域都有深入和广泛的应用。

2.离散时间的马尔科夫链

2.1.马尔科夫链三要素

这是一类随着时间而发生状态变换的过程,因此分为离散时间的马尔科夫链和连续时间的马尔科夫链两类。我们首先考虑离散时间的马尔科夫链,他的状态在确定的离散时间点上发生变化。

离散时间的马尔科夫链有三个核心概念点:离散时间、状态空间、转移概率

在离散时间的马尔科夫链中,我们通常使用$n$来表示时刻,用$X_n$来表示马尔科夫链在此时的状态,那么马尔科夫链所有的状态会构成一个如下的集合$S=left{ 1,…,m right}$,这个集合$S$我们把他称作是这个离散时间马尔科夫链的状态空间。

那么,在这个状态空间的基础之上,我们来讨论马尔科夫链的第二个概念:转移概率。转移概率是这么描述的:当离散时间的马尔科夫链当前的状态是$i$ 时,下一个状态等于$j$的概率就是转移概率,我们记作是$p_{ij}$。

转移概率$p_{ij}$本质上用一个条件概率就可以表达:

$p_{ij}=P(X_{n+1}=j|X_n=i),i,jin S$

我们举一个拥有三个状态的离散时间马尔科夫链,他的转移概率图如下:

【算法模型】S07E14 状态转移:马尔科夫链初步

图1.三状态离散时间马尔科夫链状态转移图

在这幅图中标明的是张三的三种状态,每天他都处于这三种状态中的一种:要么宅在家中,要么在外面运动,要么则是在网红点吃美食。这就是张三的状态空间,如果今天张三宅在家中,明天他仍然宅在家中的概率是$0.2$,明天出去吃美食的概率是$0.6$,明天出去运动的概率是$0.2$,这就是他的几个转移概率。

2.2.马尔科夫性

如果我们说离散时间、状态空间和转移概率是离散时间马尔科夫链的构成要素,那么马尔科夫性则是他的灵魂特征。

这个特性具体描述为:只要时刻$n$马尔科夫链的状态为$i$,不论过去发生了什么,也不论马尔科夫链是如何到达状态$i$的,下一个时刻$n+1$转移到状态$j$的概率一定都是转移概率$p_{ij}$ 。

我们还是用上面的图例来说明,比如张三今天是在吃美食,那么不管他昨天是在运动还是宅在家中,他明天出去运动的概率都不变,就是$0.3$,出去继续吃美食的概率也不变,还是$0.6$。概况的说来就是:下一个状态只与当前状态有关,而与更早的历史状态无关。

语言上七七八八的说了这么多,又是举例子、又是理论术语的,其实落实在数学语言的表达上,还是一个条件概率等式的事儿:

即对任意的时刻$n$,对状态空间中的任意状态$i,jin S$,以及时刻$n$前(也就是历史上的)任意可能的状态序列$i_0,…,i_{n-1}$ ,均有:

$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=P(X_{n+1}=j|X_n=i)=p_{ij}$

很清楚也很直白:下一个状态$X_{n+1}$的概率分布只依赖于前一个状态 $X_n$ 。

2.3.转移概率和状态转移矩阵

那么问题来了,这个转移概率$p_{ij}$具有什么样的性质?首先$p_{ij}$满足非负性,这是必须的。

其次再有:$sum_{j=1}^{m}{p_{ij}}=1$ ,这个等式对所有的$i$都成立。这个其实很好理解,我们还是对照着上面那个张三的状态图来看。比如他今天宅在家中,那么他明天继续宅在家中的概率是$0.2$,明天出去运动的概率是$0.2$,明天出去吃美食的概率是$0.6$,不管这三个概率如何取值,如何分配,有一点是肯定的,就是三者相加必须等于$1$。

我们关注一下这里特殊一点的情况,即当$i=j$时,$p_{ii}$的取值问题。其实就是对应了张三今天宅在家中,明天继续宅在家中的情况。虽然状态没有发生变化,但是我们可以认为是状态发生了一次特殊的转移,也就是自身转移。

在状态空间$S$中,任意两个状态$i$和$j$之间都有一个转移概率$p_{ij}$,并且满足$p_{ij} ge 0$(当状态$i$无法转移到状态$j$的时候,$p_{ij}=0$)。那么我们可以把状态空间中的状态间的所有转移概率按照顺序组织成一个二维矩阵,其中第$i$行、第$j$列的元素就是$p_{ij}$,那么这个二维矩阵$begin{bmatrix}p_{11}&p_{12}&…&p_{1m}\p_{21}&p_{22}&…&p_{2m}\…&…&…&…\p_{m1}&p_{m2}&…&p_{mm}end{bmatrix}$,就称为是转移概率矩阵,他刻画了对应的马尔科夫链的本质。

我们沿用张三的例子:我们令状态$1$为宅在家中;状态$2$为运动;状态$3$ 为吃美食,那么这个马尔科夫链就是是一个$3 times 3$的$2$维矩阵 $begin{bmatrix}0.2&0.2&0.6\0.2&0.1&0.7\0.1&0.3&0.6end{bmatrix}$

3.马尔科夫链性质的总结

到这里,我们有必要停下来梳理一下马尔科夫链的最基本性质,一个马尔科夫链由以下主要特征确定:

第一是状态集合$S=left{ 1,2,…,m right}$;

第二是可能发生状态转移的$(i,j)$的集合,即那些$p_{ij}>0$的状态对;

第三是$p_{ij}$的取值。

而这三点都可以最终由一个二维的转移概率矩阵所描述。

并且由该上述特征所描述的马尔科夫链是一个随机变量序列 $X_0,X_1,X_2,……$ ,他们取值于状态空间$S$,并且满足:对于任意的时间$n$,所有状态$i,jin S$ ,以及之前所有可能的状态序列$i_0,…,i_{n-1}$,均有$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},…,X_0=i_0)=p_{ij}$。

4.一步到达与多步转移

4.1.多步转移的描述

刚才我们花大篇幅介绍的转移概率$p_{ij}$给出的是从状态$i$一步到达状态$j$ 的转移概率$p_{ij}=P(X_{n+1}=j|X_n=i)$。那么我们进一步拓展呢,我们不是通过一步,而是通过$m$步(其中 $m>1$)从状态$i$转移到状态$j$,那么这个对应的就是$m$步状态转移的概率。

写成条件概率的形式就是:

$p^{m}(i,j)=P(X_{n+m}=j|X_n=i)$

4.2.一个阶级流动性的例子

这里我们换一个例子来看看,社会的流动性问题是大家都非常关注的一个问题,社会的流动性强,社会的底层通过自身的努力使得家族向社会中层甚至上层流动是社会始终保持活力重要推动力。

社会学中就有一个非常有名的反映社会阶层流动的马尔科夫链,在这个马尔科夫链的状态空间中,有三个状态,状态$1$是处于贫困水平,状态$2$是中产阶级,状态$3$是财富自由,他的状态转移矩阵为:$begin{bmatrix}0.7&0.2&0.1\0.3&0.5&0.2\0.2&0.4&0.4end{bmatrix}$。

我们不讨论这里面数据的合理性和准确性,单单就事论事,如$p_{13}=0.1$,表示如果这一代人处于贫困水平,下一代人想成为财富自由的概率为$0.1$,而继续处于贫困水平的概率要大得多,为$0.7$。而如果这一代人处于财富自由的水平,那么他的下一代处于财富自由的概率也要大不少,为$0.4$。

那么,我们现在思考这么一个问题,假设爷爷处于贫困水平(状态1),那么父亲处于中产阶级(状态2),而你处于财富自由水平(状态3)的概率有多大?

从哪里入手呢?还是紧扣定义,从条件概率表达式入手:

$P(X_2=3,X_1=2|X_0=1)= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_0=1)}$ $= frac{P(X_2=3,X_1=2,X_0=1)}{P(X_1=2,X_0=1)}cdotfrac{P(X_1=2,X_0=1)}{P(X_0=1)}$ $=P(X_2=3|X_1=2,X_0=1) cdot P(X_1=2|X_0=1)$

由于这是一个马尔科夫链,因此满足:

$P(X_2=3|X_1=2,X_0=1)=P(X_2=3|X_1=2)$

因此有:

$P(X_2=3,X_1=2|X_0=1)=P(X_2=3|X_1=2)P(X_1=2|X_0=1)$。

对应到转移概率矩阵中,就是从状态$1$转移到状态$2$的概率乘以从状态$2$转移到状态$3$的概率:$p_{12} p_{23}=0.2 cdot 0.2 = 0.04$。

接下来我们不指定父亲的状态,只看这么一个问题,就是假设爷爷是贫困水平(状态$1$),问孙子处于财富自由(状态$3$)状态的概率有多大?

那么这里只指定了爷爷和孙子所处的状态,那么父亲这一代可以是处于贫穷、中产和财富自由中的任意一种状态,那么这个概率的表达式写起来也很简单:

$P(X_2=3|X_0=1)$ $=P(X_2=3,X_1=1|X_0=1)+P(X_2=3,X_1=2|X_0=1)+P(X_2=3,X_1=3|X_0=1)$ $=p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33}=sum_{k=1}^3{p_{1k}p_{k3}}$ $=0.7cdot 0.1+0.2cdot 0.2+0.1cdot 0.4=0.15$

4.3.多步转移与矩阵乘法

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 【算法模型】S07E14 状态转移:马尔科夫链初步求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们