吉布斯抽样的一个简单理解

本文来自Cross Validated中一个人的回答。原文： Can someone explain Gibbs sampling in very simple words?

假设你是一个地下城主，在举办地下城与勇士的比赛。其中一个选手扔出了一个叫“Spell of Eldritch Chaotic Weather”的法术。但是你从来没听过这个法术。这个选手给了你一本很厚的书，说这个法术的效果是这本书中的出现的某个效果。这本书总共有1000个效果，每种效果都有个相对概率。这本书告诉你，最有可能的效果是“火球”，其他效果都使用相对于火球的概率来描述，比如书本第155页描述的“闪避风暴”的效果是“火球”概率的一半。

你如何从这本书中抽取一个随机的效果呢？你可以这样做：

接受-拒绝算法（Accept-reject algorithm）:

1. 投掷一个有1000面的骰子来决定选择哪个效果作为候选效果；
2. 假设候选效果相对于最有可能的“火球”有44%的可能，也就是说以44%的概率接受这个效果（那就再投掷一个100面的骰子，如果骰子向上的值小于44就选择这个，否则继续步骤1，直到你接受某个效果为止）
3. 你接受的这个效果就是你抽样的法术效果

接受-拒绝算法可以保证你以某个相对的概率从某个分布中抽取样本。

在你投掷了足够多次的骰子之后，你终于选择到了一个法术效果“召集青蛙”。你终于深吸一口气，然后回去继续主持你的比赛。

结果另一个选手不甘示弱，使出了“Lv. 2 arcane cyber-effect storm”。对于这个法术，有两个随机的效果出现：一个随机产生某种攻击，另一个随机产生某种魔法。这个法术的手册很大，只能用CD装。打开CD你的下巴都掉了（这哥们真是诙谐啊）：你发现每个攻击的记录都和之前的法术一样大，因为它列出了每一种伴随可能产生的魔法。

'Cupric Blade'（攻击名称）
伴随这个攻击最有可能的魔法为'Hotelling aura'
'Jackal Vision' 在这个攻击下出现的概率大约是 'Hotelling aura' 33%
'Toaster Ears' 在这个攻击下出现的概率大约是 'Hotelling aura' 20%
...

类似的，每个攻击法术发生的概率也都取决于魔法出现的情况。

对这种情况如何抽样呢？这是就可以使用吉布斯抽样了。

吉布斯抽样（Gibbs sampler algorithm）:

1. 随机选择一个攻击法术
2. 使用接受-拒绝算法抽取这个攻击法术下面的某种魔法
3. 忘掉步骤1中的攻击法术，使用接受-拒绝算法抽取步骤2魔法效果发生下的攻击效果
4. 继续步骤2，重复足够多次数（比如10000次）
5. 算法迭代到最后一次的抽样结果，就是你抽取的法术结果