Metropolis Hasting演算法如何推導出Gibbs Sampling？

01-07

Metropolis Hasting是從Markov chain的stationary distribution推導得到的，基本為了滿足detailed balance而推理出（這塊推導細節在wikipedia上我還是存疑）。現在問題是Gibbs Sampling演算法如何從Metropolis Hasting推理出（接受率α=1？？）？

@程德華的回答使這個問題變得有意思了。我理解的「Gibbs sampling」 is a special case of MH 是指Gibbs update algorithm能從MH中導出（只要把gibbs update的每一步視為MH中的proposal，接受率為1）。

而systematic sweep（或者fixed scan）是多次Gibbs update的combination，這些combing kernels依賴於每一步的實現，是irreversible，（詳見RobertSahu(1997)）但這並不能說gibbs sampling不是MH的special case。每一次Gibbs Update都是reversible的，簡略證明詳見（http://www.mcmchandbook.net/HandbookChapter1.pdf section 1.12.4)。combinationmixing的方法很多，能塑造出來各種irreversible和reversible的chain，即便是systematic sweep也有一種子類別叫做「palindromic scan」，恰好它又是reversible的。

把MH里的proposal distribution設置為一個變數的conditional distribution, conditioned on 其他所有變數，就是Gibbs sampling。所以說gibbs sampling是MH的一個特例。為什麼Gibbs sampling的accept rate是一，參見 http://www.cs.cmu.edu/~epxing/Class/10708-14/lectures/lecture17-MCMC.pdf 的第46頁

這是一個有趣的問題。一般的教材里都會說Gibbs Sampling的接受率等於1，倒是也沒什麼大問題，不過不夠嚴格。

Systematic Sweep的Gibbs Sampling是無法從MH推出的，因為MH的Chain是reversible的，而Systematic Sweep的Gibbs chain不是reversible的。

但是還有一種random Sweep的Gibbs sampling, 那就可以從MH推出來了。

systematic sweep是固定一個variable ordering, e.g., $1,2,3,dots,n$ ,然後每次都按這個順序update variable.

random sweep是每次從 $[1:n]$ 中隨機抽一個序號，然後update這個variable.

此時可以證明acceptance rate=1，題主你想到了這個問題一定可以自己證出來。

Reference:

http://users.aims.ac.za/~ioana/notes-ch4-2x1.pdf

Gibbs sampler和 MH的關係直觀理解是這樣的。MH是一個很general的方法, 給一個proposal, 通過構造一個接受概率, 就可以實現target distribution。這個proposal 越合理(接近目標分布), 接受概率就越大, MH就越efficient(not in the sense of exploring the entire distribution). Gibbs sampler的proposal是從conditional distribution 來的, 對一個joint distribution來說, 用它本身的conditional distribution 採樣去propose下一步, 這當然是合理的. 對MCMC來說, 考慮的時候不需要想達到目標之前的過程,只要想假設已經達到目標, 那麼下一步是不是能保持目標分布。證明本身其實是很直接的。對MH的直觀理解參見 MCMC 演算法和 M-H 演算法裡面的「接受概率」是什麼意思？

看這篇文章 JinZhihui: LDA-math-MCMC 和 Gibbs Sampling

也許會有幫助