马尔科夫链简析
前面几期博客一直在说蒙特卡洛的知识,说到底我们的目的是为了将马尔科夫链和蒙特卡洛采样结合起来的,今天我们通过几个小例子来分析一下马尔科夫链。 这中间涉及了比较多的数学知识,但是我们将从例子的角度分析,让马尔科夫链不那么的费解!
马尔科夫链应用
社会学家经常把人按其经济状况分成3类:下层(lower_class)、中层(middle-class)、上层(upper-class),我们用1,2,3 分别代表这三个阶层。 社会学家们发现决定一个人的收入阶层的最重要的因素就是其父母的收入阶层。如果一个人的收入属于下层类别,那么他的孩子属于下层收入的概率是0.65, 属于中层收入的概率是0.28,属于上层收入的概率 是 0.07。事实上,从父代到子代,收入阶层的变化的转移概率如下 :
使用矩阵的表示方式,转移概率矩阵记为:
假设当前这一代人处在下层、中层、上层的人的比例是概率分布向量\(π_0= [ π_0(1),π_0(2),π_0(3)]\),那么他们的子女的分布比例将是\(π_1=π_0P\), 他们的孙子代的分布比例将是\(π_2= π_1P=π_0P^2,….\), 第\(n\)代子孙的收入分布比例将是\(π_n= π_{n-1}P=π_0P^n,….\)。假设初始概率分布为 \(π_0 =[0.21,0.68, 0.11]\),则我们可以计算前\(n\)代人的分布状况如下:
我们发现从第7代人开始,这个分布就稳定不变了,这个是偶然的吗?我们换一个初始概率分布\(π_0 = [0.75, 0.15, 0.1]\)试试看, 继续计算前\(n\)代人的分布状况如下:
我们发现,到第9代人的时候,分布又收敛了。最为奇特的是,两次给定不同的初始概率分布,最终都收敛到概率分布\(π = [0.286,0.489,0.225]\), 也就是说收敛的行为和初始概率分布\(π_0\)无关。这说明这个收敛行为主要是由概率转移矩阵P决定的。
我们计算下\(P^n\):
我们发现,当n足够大的时候,这个\(P^n\)矩阵的每一行都是稳定地收敛到\(π = [0.286,0.489,0.225]\) 这个概率分布。自然地, 这个收敛现象并非是我们这个例子所独有,而是绝大多数“马尔科夫链”的共同行为。
马尔科夫链应用再谈
为了求得一个理论上的结果,我们来看一个更小规模的例子(这将方便我们后续的计算演示),假设在一个区域内,人们要么是住在城市,要么是住在乡村。 下面的矩阵告诉我们人口迁移的一些规律(或倾向)。例如,第1行第一列就表示,当前住在城市的人口,明年将会有90%的人选择继续住在城市。
作为一个简单的开始,试着来计算一下现今住在城市的人中2年后会住在乡村的几率有多大。分析可知,当前住在城市的人,1年后,会有90%继续选择住在城市, 另外10%的人则会搬去乡村居住。然后又过了1年,上一年中选择留在城市的人中又会有10%的人搬去乡村。而上一年中搬到乡村的人中将会有98%的选择留在乡村。 这个分析过程如下图所示,最终可以算出现今住在城市的人中2年后会住在乡村的几率\(=0.90\times 0.10 + 0.10\times 0.98\)。
其实你会发现我们的计算过程就是在做矩阵的平方。如下图所示,你会发现结果矩阵中第2行第1列的计算就是在执行上面在处理的操作。在此基础, 我们还可以继续计算n年后的情况,也就是计算矩阵A自乘n次后的结果。
如果我们假设最开始的时候,城乡人口的比例为7:3,那么我们可以用一个列向量来表示它\(P=[0.7, 0.3]^T\),我们想知道最终城乡人口的比例为何, 则就是要计算\(\lim_{n\rightarrow\infty}A^nP\)。如果最初城乡人口的比例为9:1,结果又如何呢?这些都要借助矩阵的极限,对角化操作以及马尔科夫链等概念来辅助我们的计算。
简析三个概念
我们来辨析三个概念:随机过程、马尔科夫过程、马尔科夫链。这三个概念中,都涉及到object和它们对应的state这两个要素。在刚刚给出的例子中, 研究的object就是人,人的state分为住在城市或者住在乡村两种。
- Stochastic process: a process where elements of a set are each classified as being in one of several fixed states that can switch over time by a probability.
- Markov process: a stochastic process with the property that, given the present state, the present and past states are independent.
- Markov chain: The Markov process with the finite possible states.
最宽泛的概念就是随机过程,限制最多的就是马尔科夫链。
对于马尔科夫链,必须满足两个条件:
- 当前状态仅跟上一个状态有关;
- 总共的状态数是有限的。如果状态数可以是无限多个,那样的问题就称为Markov process。
在某个时间点上,object的状态为s1,下一个时刻,它的状态以某种概率转换到其他状态(也包含原状态s1),这里所说的“以某种概率转换”最终是通过转移矩阵 (或称随机矩阵)的形式来给出的。转移矩阵的定义如下:
上式成立需要存在一个整数\(n\)使得\((A^n)_{ij}>0\)for all i, j。
所以从状态转移矩阵中,(结合之前的两个例子)我们可以看出$$A_{ij}元素给出的信息就是(在一个单位时间间隔内)object从状态 j 转移到状态 i 的概率。 其中任意一个转移矩阵中的某一列都是一个概率向量。
总结
我们通过分析马尔科夫链的两个例子已经对马尔科夫链的大体含以上得到了解答,进一步我们还会深入探讨!
谢谢观看,希望对您有所帮助,欢迎指正错误,欢迎一起讨论!!!