拒絕取樣（rejection sampling）

假設你想在一座形狀古怪的小山下均勻撒點——一個你算得出卻反轉不了的機率密度。這裡有個美妙又簡單的點子：對一個完全罩住這座山的大矩形均勻擲飛鏢，只「保留」落在山的曲線底下的飛鏢，其餘的丟掉（拒絕）。你保留下來的點，恰好按山的形狀分布。這就是馮諾伊曼發明的拒絕取樣。

精確地說：要從目標密度 f 取樣，挑一個你「會」取樣的簡單「提議」密度 g，以及一個常數 M，使處處 f(x) <= M * g(x)，於是 M*g 形成一個坐在 f 上方的包絡。重複：從 g 抽一個候選 x，抽一個均勻數 u 落在 [0, 1)，若 u <= f(x) / (M * g(x)) 則「接受」x，否則拒絕並重試。被接受的 x 恰好服從 f——不必反轉、不必對 f 積分，你只要能算到 f 相差一個常數即可。平均而言你接受的比例是 1/M，即 f 底下面積與包絡底下面積之比；包絡愈緊貼 f，浪費的飛鏢愈少。

它的魅力在於對幾乎任何你寫得出又圈得住的密度都能用，即使沒有閉式累積分布函數，而且它給出「精確」樣本（不是近似）。它誠實的弱點是效率：若包絡 M*g 遠大於 f——在高維中很容易發生，那裡一個盒子會讓任何尖峰密度底下的區域相形見絀——則 1/M 變得極小，你幾乎拒絕一切，每個被接受的樣本都浪費了巨大力氣。所以拒絕取樣在低維且提議貼合時大放異彩，否則嚴重退化，這也是 MCMC 方法在困難的高維取樣中取而代之的原因之一。