同一個隨機來源
模擬時,我們常先取得零與一之間的均勻隨機數 ,但所需的結果可以偏斜、離散,甚至同時含有連續部分及原子。如何由同一種輸入產生這些分佈?想像從左到右累積概率:累積分佈函數(CDF)告訴我們到某個位置為止已有多少概率,而分位數則指出首次累積到指定比例的位置。
設 是累積分佈函數。 非遞減、右連續,並滿足 和 。它可以跳躍,也可以在區間上保持不變,因此普通反函數未必存在。
定義 29.1.1
(廣義分位數)
對 ,累積分佈函數 的廣義分位數為
由 在兩端的極限,這個集合非空且有下界,故 是實數。若輸入在 上均勻, 和 的取值不影響其分佈,也不必在端點強行指定有限值。
定理 29.1.2
(反變換構造)
若 在 上均勻,而 是累積分佈函數 的廣義分位數,則 的累積分佈函數是 。此結果同時適用於連續、離散及混合分佈。
證明
(分位數的事件等式)
我們證明:對任意實數 和 ,
若 ,則 屬於定義 的集合,所以其下確界滿足 。反過來,由於 非遞減,定義集合是一個向右無界的區間。取集合中的點 (若 本身已在集合內,可取 )。則 ,由右連續性得 。若 ,單調性便給出 。
由於 在 上均勻,上述等式對每個實數 給出
包括 和 的情況。因此 的累積分佈函數是 。
證明透視
右連續性與下確界在哪裏用上
整個證明就是事件等式;有了它,均勻分佈只需一行便把 化成數值 。等式有容易的一半和精細的一半。容易的一半 只用到下確界的定義。精細的一半需要 ,即下確界能被取到;這是唯一用到右連續性的地方。
「」與「」的配合是有意的選擇。若改用左連續版本的 ,取到下確界這一步在原子處可能失效,而等式恰好會在那些令離散分佈成為可能的跳躍處破壞。論證中沒有假設 連續或嚴格遞增;正因如此,同一個構造涵蓋離散、連續及混合分佈。
三個分位數計算
例題 29.1.3
(離散分佈)
設 、、。累積分佈函數在 跳躍,因此
三個區間的長度分別是 ,正好給出所需的概率。對連續均勻輸入,更改分界點的輸出不會改變分佈;上式的端點歸屬則是按 的定義決定的。
例題 29.1.4
(指數分佈)
設 , 時 , 時 。對 ,當 時 不成立;當 時它等價於 ,即 。因此
此例中解方程 得到同一答案,因為 在 上連續且嚴格遞增。驗算:對 ,。
例題 29.1.5
(左端有原子的混合分佈)
設 以概率 等於 ,否則在 上均勻分佈,故 時 , 時 , 時 。若 ,則 ,而 時 ,所以 。若 ,則 恰好當 ,所以 。
邊界情況在原子處。整段輸入 都被送到單一值 ,給出 ;在 上,映射 把餘下的概率均勻鋪在 上。這裏當 時方程 無解,但 仍有定義。
反方向的變換
定理 29.1.6
(概率積分變換)
若 的累積分佈函數 在整條實數線上連續,則 在 上均勻。這裏不要求 嚴格遞增。
證明
(使用等值集合的右端點)
固定 ,令 。由兩端極限,這個集合非空且有上界,故 有限。集合中的點從左趨近 ,由連續性得 ; 右側的點滿足 ,由連續性得 。因此 。若 ,則 ;若 ,則 。所以
由於 取值於 ,而上式對每個 成立, 在 上均勻。
證明透視
為甚麼平坦部分無妨而跳躍不行
關鍵一步是把 選為等值集合 的右端點,而不是去解 。若 在高度 的某段區間上平坦,方程便有許多解;取上確界選出一點 ,使 ,而平坦區間本來就沒有概率。
連續性用了兩次,分別得出 和 。若 在 處跨過 跳躍,便可能有 ,而 ,計算結果會是 而不是 。沒有任何一步用到嚴格遞增,所以定理不作此假設。
連續性確實重要:若 在 有原子,則 以至少 的概率等於 ,而均勻分佈沒有原子。單獨套用 不可能把同一個原子拆成連續區間。
反例模式
公平硬幣的 CDF 值並非均勻
設 。此時 以各 的概率取值 和 。例如 ,並非 。同一個不連續的 仍可用反變換 構造;反方向的結論則需要連續性。
用獨立隨機性填補跳躍
有一個有用的修補方法。記左極限 ,於是 是 處的跳躍。
定理 29.1.7
(隨機化概率積分變換)
設 的累積分佈函數為 ,而 與 獨立、在 上均勻。則
在 上均勻,不論 屬於哪一類型。
證明
(按 相對於分位數的位置分情況)
固定 ,令 。事件等式給出 ,而每個 都有 ,所以 。按 的位置拆分事件 。
若 ,則 ,故這情況貢獻 。
若 ,則 。在有正跳躍的點, 給出 。在沒有跳躍的點, 迫使 ,於是 落在 右方一段 為常數的區間內,而這樣的區間概率為零。這情況貢獻 。
若 且跳躍 為正,由 的獨立性,
因為該比值在 內。若 ,則 且 ,貢獻 依然相同。三種情況相加得 。
在原子 處,這個式子把其概率均勻分配到跳躍區間 ;沒有跳躍時則 。
常見錯誤
常見錯誤
(對含原子的分佈解 )
對原子位於 的離散分佈,方程 無解: 在 由 跳到 。反變換抽樣並不需要方程有解。廣義分位數給出 ,即累積概率首次達到 的點。
常見錯誤
(以為分位數是具有該概率的唯一點)
對取值 的公平硬幣,每個 都滿足 及 ,所以每個這樣的 都是中位數。廣義分位數並沒有找出「真正」的中位數,而是作出一個確定的選擇 ,即累積分佈函數達到 的最小點。
練習
快速檢查
(設 、、。求廣義分位數,並計算 。)
先列出 在三個原子的值。
解答 · 答案
、、。因此當 時 ;當 時 ;當 時 。事件 即 ,概率為 。
快速檢查
(設 ()、()、()。求 和均勻 的 。)
在 上,累積分佈函數連續且嚴格遞增。
解答 · 答案
對 ,在 時 即 ,所以 。因此 ,與 一致。
快速檢查
(設 是伯努利(Bernoulli)變量,,其中 。求 的分佈,並解釋為何它不均勻。)
計算 在兩個可能值的取值。
解答 · 答案
,;因此 以概率 取值 ,以概率 取值 。它有原子,故不是連續均勻分佈。
快速檢查
(在伯努利情況中,令 是獨立均勻變量。分別寫出 、 時的隨機化變換 ,並驗證 時 。)
先求 與 。
解答 · 答案
由於 、: 時 ; 時 。若 ,只有 有貢獻,;若 ,概率為 。兩個條件均勻區間剛好填滿 。