從列表中選擇一個隨機元素需要多少熵？
假設我想從大小列表中選擇一個隨機元素 $ 2^n $ , 對於任何整數 $ n $ . （這裡，隨機是指選擇每個項目的機率相等。）我的直覺告訴我需要 $ n $ 一點點的熵。例如，對於大小為 64 的列表，我需要 6 位熵。
但是，我需要多少位熵才能從列表中選擇一個隨機元素，該元素的大小不是 $ 2^n $ ? 例如，對於大小為 3 或 10 的列表？
我的直覺說我需要找到 $ n $ 這樣 $ 2^n $ 是列表大小的倍數，以確保選擇每個項目的機率相等。（這適用於所有大小的列表 $ 2^n $ .) 然而，這在實踐中似乎行不通：似乎沒有任何 $ n $ 這樣 $ 2^n $ 平均分為 3 或 10。
可以使用一種稱為Knuth Yao 採樣的技術來實現這一點。它：
- 允許您從任何分佈中取樣 $ X $ 有限支持的（比如函式在哪裡 $ f(i, s) = \text{the }i\text{th bit of }\Pr_X[X = s] $ 是有效可計算的）
- 平均使用 $ \leq H(X) + 2 $ 熵位，其中 $ H(X) $ 是所考慮的分佈的熵。
然後可以替換 $ X $ 與您的分佈（說統一 $ 3^n $ 元素）來獲得結果。我將快速描述 Knuth-Yao 採樣在其餘答案中的工作原理。
Knuth Yao 採樣的工作原理是建構一個特定的（通常是無限的）二叉樹，並在其上執行無偏隨機遊走。樹的葉節點由基礎機率分佈上的元素標記，當您點擊葉節點時，您會終止遍歷並將該元素作為樣本輸出。
為什麼要這樣做？基本思想是把葉子標記為 $ s $ 在深處 $ i $ 當且當 $ f(i, s) = 1 $ . 那麼下面的事實可以結合起來說明採樣器的輸出分佈是精確的 $ X $ :
- 在二叉樹的無偏行走期間到達任何特定節點的機率是 $ 1/2^i $ ， 在哪裡 $ i $ 是節點的深度
- 因此，採樣器在標記為的葉子中結束的機率 $ s $ 在深處 $ i $ 是 $ f(i, s)/2^i $ （如果 $ f(i, s) = 0 $ , 沒有這樣的葉子，否則正好有 1)。
- 採樣器最多可以進入一個葉子（它在之後終止），因此它們形成一組獨立的事件。
然後有一個：
$$ \begin{align*} \Pr[\text{KY sampler outputs }s]&= \sum_{i = 0}^\infty \Pr[\text{KY sampler outputs }s\text{ in depth }i]\ &=\sum_{i = 0}^\infty f(i, s) / 2^i\ &= \Pr[X = s] \end{align*} $$
表明平均熵使用受以下限制 $ H(X)+2 $ 需要一個相當仔細的論據，你可以在 Knuth 和 Yao 的初始論文中找到它（實際上很難找到，但可以在 Knuth 的精選論文集之一中找到（Selected Papers on Analysis of Algorithms, entry 34 The非均勻隨機數生成的複雜性）。
你需要 $ log_2 N $ 一點點的熵。所以從正式的角度來看，從 10 個元素的列表中，你需要 $ 3.321928 $ 一點點的熵。
但是，如果您真的想使用 N 個隨機位獲取隨機元素（具有等機率的機率），則需要進行縮放。
一種天真的方法是獲取 $ n $ 位，獲得 $ r \in [0, 2^n) $ 並且只是獲取元素 $ r \ mod \ N $ . 這提供了一個隨機元素，但並非所有元素都同樣可能被選中。
一個選項是獲取元素 $ r $ 如果 $ r < N $ 否則重新開始，儘管這將是無限的。Jacques 博士在http://mathforum.org/library/drmath/view/65653.html上描述了一種更優化的方法（信用轉到random.org FAQ 2.10以找到連結），您可以在其中累積剩餘部分以形成新數字，它需要更少的隨機位，儘管仍然是無界的。