逆變換與拒絕抽樣（inverse-transform and rejection sampling）

每一場模擬都倚賴一項卑微的本領：把電腦那條介於 0 與 1 之間的均勻亂數流，變成你真正需要的任何分布的抽樣——常態、指數、自訂的形狀。兩個經典配方辦得到。逆變換抽樣在你能反轉累積分布函數時管用；拒絕抽樣在你不能時管用，靠的是巧妙地抽樣再丟掉一些。

逆變換倚靠一個叫做機率積分變換的小奇蹟：若 U 在 [0, 1] 上均勻、F 是你想要的累積分布函數（CDF），則 X = F^(-1)(U)，也就是分位數函數在 U 的值，恰好有分布 F。圖像是：在縱軸上於 0 與 1 之間均勻地挑一個高度 U，橫滑到 CDF 曲線，讀出曲線達到那個高度時的 x；做很多次，那些 x 就按 F 分布。例如指數的 F(x) = 1 - e^(-lambda x) 反轉得到 X = -ln(1 - U)/lambda，一行的產生器。拒絕抽樣處理 F^(-1) 沒有公式的常見情形：把目標密度 f 罩在一個縮放過、易抽的密度 g 之下（使得處處 c 乘以 g(x) >= f(x)），從 g 抽一個候選 x，抽一個均勻 u，只在 u <= f(x) / (c g(x)) 時「接受」x；否則丟棄再試。被接受的點恰好按 f 分布——幾何上，你是在外罩 c g 之下丟飛鏢，只留下同時落在 f 之下的那些。

這些是每一個更高階方法（蒙地卡羅、MCMC、自助法）底下的地基，而每一個都有它誠實的代價。逆變換是精確的，每次抽樣恰用一個均勻數，但它需要可反轉的 CDF，而許多分布沒有封閉形式的 CDF。拒絕法妙在普遍且精確，但它的效率是 1/c——即接受機率——所以若外罩與目標貼合得差，c 會很大，你幾乎全部拒絕，浪費巨大的工夫。整座建築也假設你底層的均勻產生器真的均勻且獨立；一個有瑕疵的產生器，會悄悄地汙染下游每一個抽樣。