我偶然發現了一個基本的離散數學/概率問題，我想了解一些改進我的解決方案的想法。給定概率的樣本
假設給你一個集合（字母表，自然數等）。你如何確保你從這個集合中以給定的概率P繪製一定的值X？
我會解釋我用一個例子天真的解決方案：
Collection = {A, B}
X = A, P = 1/4
我們建立一個數組v = [A, B, B, B]和我們使用rand函數均勻採樣數組的索引，即{0, 1, 2, 3}
這方法有效，但效率不高：較小的P，v的內存存儲量更大。因此，我想知道stackoverflow社區在改進這個方面有什麼想法。
謝謝！
將區間[0,1]劃分爲聯合爲[0,1]的不相交區間。創建每個分區的大小以對應於選擇每個事件的概率。然後簡單地從[0,1]中隨機抽樣，評估結果所在的分區，然後查找與該間隔相對應的選擇。在你的例子中，這將導致以下2個區間[0,1/4）和[1/4,1] - 從[0,1]生成隨機均勻值。如果您的樣本位於第一個區間，則選擇X = A，如果在其他區間則爲X = B。
您提出的解決方案確實不是很好，解決它的最一般和最有效的方法就像數學家的狀態（這被稱爲逆CDF方法）。對於您的具體問題，即多項採樣，您還可以使用二項分佈的一系列繪圖來從您的集合中進行採樣。如果您不熟悉採樣方法，這通常更直觀。
如果集合中的第一個項目具有概率p_1，則在區間[0-1]中統一採樣。如果樣本小於p_1，則返回項目1.否則，按1-p_1對剩餘結果進行重新歸一化，並在下一個可能結果中重複該過程。在每次不成功採樣後，將剩餘結果用拒絕結果的總概率重新歸一化，以便剩餘結果的總和爲1.如果得到最後結果，則以概率1返回結果。該過程的結果將爲隨機樣本分佈根據您的原始矢量。
該方法使用多項式的單個成分是二項分佈的事實，並且多項式的任何子矢量也是多項式的，參數由上述的重整化給出。