二、马尔可夫链

1. 马尔可夫链是满足马尔可夫性质的随机过程。

   马尔可夫链 描述了一个状态序列，其中每个状态值取决于前一个状态。 为随机变量，称为时刻 的状态，其取值范围称作状态空间。

   马尔可夫链的数学定义为： 。

2.1 马尔可夫链示例

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

2. 使用矩阵的表示方式，转移概率矩阵记作：

   

   假设当前这一代人在下层、中层、上层的人的比例是概率分布 ，则：

   • 他们的子女在下层、中层、上层的人的概率分布是
   • 他们的孙子代的分布比例将是
   • ….
   • 第 代子孙在下层、中层、上层的人的比例是

3. 假设初始概率分布为 ，给出前 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. 如果换一个初始概率分布为 ，给出前 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. 两次不同的初始概率分布，最终都收敛到概率分布 。 这说明收敛的行为和初始概率分布 无关，而是由概率转移矩阵 决定的。

   计算 ：

   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]]
     ...

   可以看到 ：

   

   发现当 足够大的时候， 矩阵 收敛且每一行都稳定收敛到 。

2.2 平稳分布

1. 马尔可夫链定理：如果一个非周期马尔可夫链具有转移概率矩阵 ，且它的任何两个状态是联通的，则有：

   

   其中：

   • 为所有可能的状态。

   • 是转移概率矩阵 的第 行第 列的元素，表示状态 转移到状态 的概率。

   • 概率分布 是方程 的唯一解，其中 。

     称概率分布 为马尔可夫链的平稳分布。

2. 注意，在马尔可夫链定理中：

   • 马尔可夫链的状态不要求有限，可以是无穷多个。

   • 非周期性在实际任务中都是满足的。

   • 两个状态的连通指的是：状态 可以通过有限的 步转移到达 (并不要求从状态 可以直接一步转移到状态 ）。

     马尔可夫链的任何两个状态是联通的含义是：存在一个 ，使得矩阵 中的任何一个元素的数值都大于零。

3. 从初始概率分布 出发，在马尔可夫链上做状态转移，记时刻 的状态 服从的概率分布为 ， 记作 ，则有：

   

   假设到达第 步时，马尔可夫链收敛，则有：

   

   所以 都是同分布的随机变量（当然它们并不独立）。

   如果从一个具体的初始状态 开始，然后沿着马尔可夫链按照概率转移矩阵做调整，则得到一个转移序列 。

   根据马尔可夫链的收敛行为，当 较大时， 将是平稳分布 的样本。

4. 定理：如果非周期马尔可夫链的转移矩阵 和某个分布 满足： ，则 是马尔可夫链的平稳分布。

   这被称作马尔可夫链的细致平稳条件detailed balance condition ，其证明如下：

   

   .