二、马尔可夫链
马尔可夫链是满足马尔可夫性质的随机过程。 马尔可夫链 ![二、马尔可夫链 - 图1] 的状态，其取值范围称作状态空间。 马尔可夫链的数学定义为： ![二、马尔可夫链 - 图4] 。 2.1 马尔可夫链示例
社会学家把人按照经济状况分成三类：下层、中层、上层。用状态
1,2,3代表着三个阶层。社会学家发现：决定一个人的收入阶层的最重要因素就是其父母的收入阶层。 如果一个人的收入属于下层，则他的孩子属于下层的概率是 0.65，属于中层的概率是 0.28，属于上层的概率是 0.07 。 如果一个人的收入属于中层，则他的孩子属于下层的概率是 0.15，属于中层的概率是 0.67，属于上层的概率是 0.18 。 如果一个人的收入属于上层，则他的孩子属于下层的概率是 0.12，属于中层的概率是 0.36，属于上层的概率是 0.52 。 从父代到子代，收入阶层的变化的转移概率如下：子代阶层1 子代阶层2 子代阶层3 父代阶层1 0.65 0.28 0.07 父代阶层2 0.15 0.67 0.18 父代阶层3 0.12 0.36 0.52 使用矩阵的表示方式，转移概率矩阵记作：
假设当前这一代人在下层、中层、上层的人的比例是概率分布 ![二、马尔可夫链 - 图6] ，则：
他们的子女在下层、中层、上层的人的概率分布是
他们的孙子代的分布比例将是
….第
假设初始概率分布为 ![二、马尔可夫链 - 图11] ，给出前 14 代人的分布状况：
0 0.72 0.19 0.09 1 0.5073 0.3613 0.1314 2 0.399708 0.431419 0.168873 3 0.34478781 0.46176325 0.19344894 4 0.3165904368 0.4755635827 0.2078459805 5 0.302059838985 0.482097475693 0.215842685322 6 0.294554638933 0.485285430346 0.220159930721 7 0.290672521545 0.486874112293 0.222453366163 8 0.288662659788 0.487677173087 0.223660167125 9 0.28762152488 0.488086910874 0.224291564246 10 0.287082015513 0.488297220381 0.224620764107 11 0.286802384833 0.488405577077 0.22479203809 12 0.286657431274 0.488461538107 0.224881030619 13 0.286582284718 0.488490482311 0.22492723297 14 0.28654332537 0.488505466739 0.224951207891
可以看到从第 9 代开始，阶层分布就趋向于稳定不变。
4. 如果换一个初始概率分布为 ![二、马尔可夫链 - 图12] ，给出前 14 代人的分布状况：
0 0.51 0.34 0.15
1 0.4005 0.4246 0.1749
2 0.345003 0.459586 0.195411
3 0.31663917 0.47487142 0.20848941
4 0.3020649027 0.4818790066 0.2160560907
5 0.294550768629 0.48521729983 0.220231931541
6 0.290668426368 0.486853301457 0.222478272175
7 0.288659865019 0.487671049342 0.223669085639
8 0.28761985994 0.488085236095 0.224294903965
9 0.287081082851 0.488296834394 0.224622082755
10 0.286801878943 0.488405532034 0.224792589023
11 0.286657161801 0.488461564615 0.224881273584
12 0.286582142693 0.488490512087 0.224927345221
13 0.28654325099 0.488505487331 0.224951261679
14 0.286523087645 0.488513240994 0.224963671362
可以发现到第 8 代又收敛了。
5. 两次不同的初始概率分布，最终都收敛到概率分布 ![二、马尔可夫链 - 图13] 决定的。
计算 ![二、马尔可夫链 - 图16]：
0 [[ 0.65 0.28 0.07]
[ 0.15 0.67 0.18]
[ 0.12 0.36 0.52]]
1 [ [ 0.4729 0.3948 0.1323]
[ 0.2196 0.5557 0.2247]
[ 0.1944 0.462 0.3436]]
...
18 [[ 0.28650397 0.48852059 0.22497545]
[ 0.28650052 0.48852191 0.22497757]
[ 0.28649994 0.48852213 0.22497793]]
19 [[ 0.28650272 0.48852106 0.22497622]
[ 0.28650093 0.48852175 0.22497732]
[ 0.28650063 0.48852187 0.2249775 ]]
20 [[ 0.28650207 0.48852131 0.22497661]
[ 0.28650115 0.48852167 0.22497719]
[ 0.28650099 0.48852173 0.22497728]]
21 [[ 0.28650174 0.48852144 0.22497682]
[ 0.28650126 0.48852163 0.22497712]
[ 0.28650118 0.48852166 0.22497717]]
...
可以看到 ：
发现当 ![二、马尔可夫链 - 图18] 。
2.2 平稳分布
1. 马尔可夫链定理：如果一个非周期马尔可夫链具有转移概率矩阵 ![二、马尔可夫链 - 图21]，且它的任何两个状态是联通的，则有：
其中：
* 
* 
* 概率分布 
称概率分布 ![二、马尔可夫链 - 图33] 为马尔可夫链的平稳分布。
2. 注意，在马尔可夫链定理中：
马尔可夫链的状态不要求有限，可以是无穷多个。
非周期性在实际任务中都是满足的。
* 两个状态的连通指的是：状态 
马尔可夫链的任何两个状态是联通的含义是：存在一个 ![二、马尔可夫链 - 图39] 中的任何一个元素的数值都大于零。
3. 从初始概率分布 ![二、马尔可夫链 - 图41] ，则有：
假设到达第 ![二、马尔可夫链 - 图47] 步时，马尔可夫链收敛，则有：
所以 ![二、马尔可夫链 - 图49] 都是同分布的随机变量（当然它们并不独立）。
如果从一个具体的初始状态 ![二、马尔可夫链 - 图50] 。
根据马尔可夫链的收敛行为，当 ![二、马尔可夫链 - 图52] 的样本。
4. 定理：如果非周期马尔可夫链的转移矩阵 ![二、马尔可夫链 - 图55] 是马尔可夫链的平稳分布。
这被称作马尔可夫链的细致平稳条件`detailed balance condition` ，其证明如下：
.
## 文章列表
- [AI算法工程师手册-一、基本知识](https://www.oomspot.com/post/aisuanfagongchengshishouceyijibenzhishi)
- [AI算法工程师手册-一、数值稳定性](https://www.oomspot.com/post/aisuanfagongchengshishouceyishuzhiwendingxing)
- [AI算法工程师手册-一、概率与分布](https://www.oomspot.com/post/aisuanfagongchengshishouceyigailuyufenbu)
- [AI算法工程师手册-一、蒙特卡洛方法](https://www.oomspot.com/post/aisuanfagongchengshishouceyimengtekaluofangfa)
- [AI算法工程师手册-七、信息论](https://www.oomspot.com/post/aisuanfagongchengshishouceqixinxilun)
- [AI算法工程师手册-三、MCMC 采样](https://www.oomspot.com/post/aisuanfagongchengshishoucesanmcmccaiyang)
- [AI算法工程师手册-三、二阶导数与海森矩阵](https://www.oomspot.com/post/anfagongchengshishoucesanerjiedaoshuyuhaisenjuzhen)
- [AI算法工程师手册-三、大数定律及中心极限定理](https://www.oomspot.com/post/chengshishoucesandashudinglujizhongxinjixiandingli)
- [AI算法工程师手册-三、矩阵运算](https://www.oomspot.com/post/aisuanfagongchengshishoucesanjuzhenyunsuan)
- [AI算法工程师手册-二、向量操作](https://www.oomspot.com/post/aisuanfagongchengshishouceerxiangliangcaozuo)
- [AI算法工程师手册-二、期望和方差](https://www.oomspot.com/post/aisuanfagongchengshishouceerqiwanghefangcha)
- [AI算法工程师手册-二、梯度下降法](https://www.oomspot.com/post/aisuanfagongchengshishouceertiduxiajiangfa)
- [AI算法工程师手册-二、马尔可夫链](https://www.oomspot.com/post/aisuanfagongchengshishouceermaerkefulian)
- [AI算法工程师手册-五、常见概率分布](https://www.oomspot.com/post/aisuanfagongchengshishoucewuchangjiangailufenbu)
- [AI算法工程师手册-五、拟牛顿法](https://www.oomspot.com/post/aisuanfagongchengshishoucewuniniudunfa)
- [AI算法工程师手册-八、其它](https://www.oomspot.com/post/aisuanfagongchengshishoucebaqita)
- [AI算法工程师手册-六、 约束优化](https://www.oomspot.com/post/aisuanfagongchengshishouceliuyueshuyouhua)
- [AI算法工程师手册-六、先验分布与后验分布](https://www.oomspot.com/post/anfagongchengshishouceliuxianyanfenbuyuhouyanfenbu)
- [AI算法工程师手册-四、牛顿法](https://www.oomspot.com/post/aisuanfagongchengshishoucesiniudunfa)
- [AI算法工程师手册-四、特殊函数](https://www.oomspot.com/post/aisuanfagongchengshishoucesiteshuhanshu)
