如何從指定的離散分佈生成一個隨機數？

Question

假設我們有一些具有有限數量可能結果的離散分佈，是否有可能比O（logn）更快地從這個分佈產生一個隨機數，其中n是可能的結果數？

如何使它在O（logn）時間：
- 使與累積概率的陣列（陣列[I] =概率該隨機數將是小於或等於i）
- 生成從隨機數均勻分佈（讓我們用k表示）
- 找出最小的i，例如k < Array [i]。它可以使用二進制搜索來完成。
- 我是我們的隨機數。

Answer 1

Walker的別名方法可以在常量最壞情況下使用一些需要預先計算的大小爲n的輔助數組繪製樣本。該方法在Devroye's book on sampling的第3章中描述，並在R sample（）函數中實現。您可以從R的源代碼或this thread獲取代碼。 A 1991 paper by Vose聲稱減少初始化成本。

請注意，除非您指定輸入的確切形式以及要繪製多少個隨機數，否則您的問題沒有明確定義。例如，如果輸入是給出每個結果的概率的數組，則算法不是O（log n），因爲它需要首先計算從輸入數組中獲得O（n）個時間的累積概率。

如果您打算繪製多個樣本，那麼生成單個樣本的成本並不那麼重要。重要的是生成m個結果的總成本以及所需的峯值內存。在這方面，別名方法非常好。如果您想要一次生成所有樣本，請使用發佈的O（n + m）算法here，然後對結果進行洗牌。