1700537550
1700537551
对于前一步产生的样本，依次采样和更新每个维度的值，即依次抽取分量，, …, ；
1700537552
1700537553
1700537554
形成新的样本。
1700537555
1700537556
1700537557
同样可以证明，上述过程得到的样本序列会收敛到目标分布p(x)。另外，步骤（2）中对样本每个维度的抽样和更新操作，不是必须按下标顺序进行的，可以是随机顺序。
1700537558
1700537559
在拒绝采样中，如果在某一步中采样被拒绝，则该步不会产生新样本，需要重新进行采样。与此不同，MCMC采样法每一步都会产生一个样本，只是有时候这个样本与之前的样本一样而已。另外，MCMC采样法是在不断迭代过程中逐渐收敛到平稳分布的，因此实际应用中一般会对得到的样本序列进行“burn-in”处理，即截除掉序列中最开始的一部分样本，只保留后面的样本。
1700537560
1700537561
问题3 MCMC采样法如何得到相互独立的样本？
1700537562
1700537563
难度：★★☆☆☆
1700537564
1700537565
分析与解答
1700537566
1700537567
与一般的蒙特卡洛算法不同，MCMC采样法得到的样本序列中相邻的样本不是独立的，因为后一个样本是由前一个样本根据特定的转移概率得到的，或者有一定概率就是前一个样本。如果仅仅是采样，并不需要样本之间相互独立。如果确实需要产生独立同分布的样本，可以同时运行多条马尔可夫链，这样不同链上的样本是独立的；或者在同一条马尔可夫链上每隔若干个样本才选取一个，这样选取出来的样本也是近似独立的。
1700537568
1700537569
·总结与扩展·
1700537570
1700537571
MCMC采样法应用十分广泛，比如可以思考如何用MCMC采样法来求一个分布的众数？MCMC采样法在最大似然估计或贝叶斯推理中是如何使用的？
1700537572
1700537573
逸闻趣事
1700537574
1700537575
1700537576
1700537577
用MCMC采样法破解密码
1700537578
1700537579
斯坦福大学统计学教授Persi Diaconis是一位传奇人物。他在14岁时就成了一名魔术师。为了看懂数学家William Feller的概率论著作，他24岁就进入大学读书。由于Diaconis曾向《科学美国人》投稿介绍他的洗牌方法，使得在《科学美国人》上常年开设数学游戏专栏的著名数学科普作家Martin Gardner给他写了推荐信去哈佛大学。当时哈佛大学的统计学家Frederick Mosteller正在研究魔术，于是Diaconis成了Mosteller的学生（对他这段传奇经历有兴趣的读者可以看一看统计学史话《女士品茶》）。下面要讲的这个故事，是Diaconis在他的文章“The Markov Chain Monte Carlo Revolution”中给出的破译犯人密码的例子。
1700537580
1700537581
一天，一位研究犯罪心理学的医生来到斯坦福大学拜访Diaconis。他带来了一个囚犯所写的密码信息，希望Diaconis能帮他找出密码中的信息。这个密码里的每个符号应该对应着某个字母（见图8.7），但是如何把这些字母准确地找出来呢？Diaconis和他的学生Marc Coram采用了MCMC采样法解决了这个问题。
1700537582
1700537583
1700537584
1700537585
1700537586
图8.7 囚犯密码的密文
1700537587
1700537588
这其实是一个非常典型的恺撒密码。手工用频率分析法，尝试不同的组合并观察结果是否有意义也可以解决这个问题。但是，除了部分高频字母，大部分字母的出现频率是差不多的，而且与文本内容有关，这样需要尝试非常多的组合，而且需要人为地判断结果是否有意义。因此，单纯地依靠字母频率分析是不够的，应该考虑更一般的特征，比如字母之间的共同出现的频率。更进一步地，可以考虑字母之间的转移概率，例如，当前一个字母为辅音时，后一个字母出现元音的概率更大；或者，连续几个辅音出现之后再出现辅音的概率将非常低。这样就可以请出MCMC方法了，以大量英文语料为基础，统计从字母x到字母y的转移概率：无论是加密前还是加密后的文本，特定位置之间的转移概率是一致的，大致趋近于正常英文语料的转移概率。
1700537589
1700537590
Diaconis和他的学生Coram按照这个思路对密文进行解密。首先，用《战争与和平》作为标准文本，统计一个字母到另一个字母的一步转移概率；然后，根据Metropolis-Hastings算法，在假设所有对应关系出现的可能性相等的前提下（也就是无信息先验），随机给出了密码字符和字母的对应关系；再利用前边得到的转移概率，计算这种对应关系出现的概率p1；然后，随机抽取两个密码字符，互换它们的对应字母，计算此时对应关系的概率p2；最后，如果p2>p1，接受新的对应关系；否则，抛一枚以p2/p1的概率出现正面的硬币，如果出现正面，则接受新的对应关系，否则依然保持旧有的对应关系。这就是Metropolis-Hastings算法的运用，当算法收敛时，就会得到真实的对应关系。事实上，当算法运行了2000多步的时候，就得到了一个混合了英语和西班牙语的文本段落，如图8.8所示。
1700537591
1700537592
1700537593
1700537594
1700537595
图8.8 囚犯密码的明文
1700537596
1700537597
1700537598
1700537599