Question

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

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

   马尔可夫链的数学定义为： $ MathJax-Element-130 $ 。

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. 使用矩阵的表示方式，转移概率矩阵记作：

   $ \mathbf P= \begin{bmatrix} 0.65&0.28&0.07\\ 0.15&0.67&0.18\\ 0.12&0.36&0.52 \end{bmatrix} $

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

   • 他们的子女在下层、中层、上层的人的概率分布是 $ MathJax-Element-132 $
   • 他们的孙子代的分布比例将是 $ MathJax-Element-133 $
   • ....
   • 第 $ MathJax-Element-173 $ 代子孙在下层、中层、上层的人的比例是 $ MathJax-Element-135 $

3. 假设初始概率分布为 $ MathJax-Element-136 $ ，给出前 14 代人的分布状况：

   
   xxxxxxxxxx
     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. 如果换一个初始概率分布为 $ MathJax-Element-137 $ ，给出前 14 代人的分布状况：

   
   xxxxxxxxxx
     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. 两次不同的初始概率分布，最终都收敛到概率分布 $ MathJax-Element-144 $ 。 这说明收敛的行为和初始概率分布 $ MathJax-Element-164 $ 无关，而是由概率转移矩阵 $ MathJax-Element-176 $ 决定的。

   计算 $ MathJax-Element-163 $ ：

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

   可以看到 ：

   $ \mathbf P^{18}=\mathbf P^{19}=\cdots=\begin{bmatrix} 0.286& 0.489 & 0.225 \\ 0.286 & 0.489 & 0.225 \\ 0.286& 0.489 & 0.225 \\ \end{bmatrix} $

   发现当 $ MathJax-Element-173 $ 足够大的时候， 矩阵 $ MathJax-Element-163 $ 收敛且每一行都稳定收敛到 $ MathJax-Element-144 $ 。

2.2 平稳分布

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

   $ \lim_{n\rightarrow \infty} \mathbf P^{n}=\begin{bmatrix} \pi {(1)}&\pi {(2)}&\cdots&\pi {(j)}&\cdots\\ \pi {(1)}&\pi {(2)}&\cdots&\pi {(j)}&\cdots\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ \pi {(1)}&\pi {(2)}&\cdots&\pi {(j)}&\cdots\\ \vdots&\vdots&\ddots&\vdots&\vdots \end{bmatrix}\\ \pi {(j)} =\sum_{i=0}^{\infty} \pi {(i)} P_{i,j} $

   其中：

   • $ MathJax-Element-146 $ 为所有可能的状态。

   • $ MathJax-Element-147 $ 是转移概率矩阵 $ MathJax-Element-176 $ 的第 $ MathJax-Element-165 $ 行第 $ MathJax-Element-161 $ 列的元素，表示状态 $ MathJax-Element-165 $ 转移到状态 $ MathJax-Element-161 $ 的概率。

   • 概率分布 $ MathJax-Element-153 $ 是方程 $ MathJax-Element-154 $ 的唯一解，其中 $ MathJax-Element-155 $ 。

     称概率分布 $ MathJax-Element-175 $ 为马尔可夫链的平稳分布。

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

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

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

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

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

3. 从初始概率分布 $ MathJax-Element-164 $ 出发，在马尔可夫链上做状态转移，记时刻 $ MathJax-Element-165 $ 的状态 $ MathJax-Element-166 $ 服从的概率分布为 $ MathJax-Element-167 $ ， 记作 $ MathJax-Element-168 $ ，则有：

   $ X_0 \sim \vec\pi_0\\ X_1 \sim \vec\pi_1\\ \cdots\\ X_n \sim \vec\pi_n\\ X_{n+1} \sim \vec \pi_{n+1}\\ \cdots $

   假设到达第 $ MathJax-Element-173 $ 步时，马尔可夫链收敛，则有：

   $ X_n \sim \vec\pi\\ X_{n+1} \sim \vec\pi\\ \cdots $

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

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

   根据马尔可夫链的收敛行为，当 $ MathJax-Element-173 $ 较大时， $ MathJax-Element-174 $ 将是平稳分布 $ MathJax-Element-175 $ 的样本。

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

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

   $ \pi(i)P_{i,j}=\pi(j)P_{j,i} \rightarrow \sum_{i=1}^{\infty}\pi(i)P_{i,j}=\sum_{i=1}^{\infty}\pi(j)P_{j,i}= \pi(j)\sum_{i=1}^{\infty}P_{j,i}=\pi(j) \rightarrow \vec\pi\mathbf P=\vec\pi $

   .