如何最好地從擲普通骰子中獲得位序列？
投擲普通骰子，可以得到
[0,5]. 在實踐中，將這些序列轉換為所需數量的比特序列的最佳過程是什麼？
Thomas 的第一個過程每卷產生 2 位，機率為 $ \frac23 $ ，即它產生 $ \frac43 \doteq 1.333 $ 位平均。正如他所描述的，這可以得到改進，但很快就會變得相當複雜。
通過取結果 mod 兩個導致每卷產生一個比特 $ 1 $ 每卷位，這並沒有更糟。結合這兩種簡單的方法，如
1 -> 00 2 -> 01 3 -> 10 4 -> 11 5 -> 0 6 -> 1非常簡單並且產生 $ 1+\frac23 = \frac53 \doteq 1.667 $ 每卷比特。AFAIK，這是您在不匯總卷的情況下可以獲得的最大值。
您可以將此想法應用於兩個卷並獲得 $ 5 $ 位機率為 $ \frac{32}{36} $ 和 $ 2 $ 位否則因此得到
$$ 2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83 = \frac{14}3 = 4\frac23 $$ 兩個卷的位，即， $ 2\frac13 \doteq 2.333 $ 每卷的位數，非常接近理論最大值 $ \log_2 6 \doteq 2.585 $ .
對於一個簡單的“沒有電腦的實現”，請注意，您可以直接從每個卷中提取 1 位，並且只需要處理“其餘的”（例如，您可以通過 $ n \bmod 2 $ 其餘的通過 $ \lfloor \frac{n-1}3 \rfloor $ ）。這使得使用小桌子甚至可以輕鬆組合 3 或 4 卷。
兩卷的確切程序
為簡單起見，我們假設每卷產生一個數字 $ n_i $ 從集合 $ {0, 1, \ldots, 5} $ .
- 從每個卷中提取一位作為 $ n_i \bmod 2 $ .
- 計算 $ 3 \cdot \lfloor \frac {n_1}2 \rfloor + \lfloor \frac {n_2}2 \rfloor $ ，這是數字 $ x \in {0, \ldots, 8} $
- 的情況下 $ x = 8 $ ，你運氣不好，除了第一步的兩個位之外什麼也沒有。
- 否則，使用 $ x \in {0, \ldots, 7} $ 作為接下來的三位。
所以，大多數時候你得到五個比特。平均而言，你得到
$$ \frac19 \cdot 2 + \frac89 \cdot 5 = \frac{42}9 = 4\frac23 $$ 位如上所述。
兩卷中有近 5.170 位，但如果不進一步聚合，您無法平均從中提取 5 位。
顯而易見的方法是考慮以下位提取算法：
- 擲骰子，產生一個整數 $ n $ 統一在 $ \mathbb{Z}_6 $ .
- 如果 $ n < 4 $ ， 返回 $ n $ 作為兩個位。否則，轉到 1。
這將返回兩個統一的位。該算法將始終終止，因為遞歸的機率等於 $ \frac{2}{6} $ 這是亞臨界的。可以在 Dennis 關於這個問題的文章中找到正確性證明。
該算法需要擲多少次骰子？至少一個，任意多個，但平均而言：
$$ 1 + \frac{2}{6} + \left ( \frac{2}{6} \right )^2 + \cdots = \sum_{t = 0}^\infty \left ( \frac{2}{6} \right )^t = \frac{3}{2} $$ 也就是說，平均而言，該算法需要擲一次半骰子。當然，根據資訊論，這表明無偏骰子擲骰的香農熵等於：
$$ \log_2{ \left ( 6 \right )} = \log_2{\left ( 4 \right )} + \log_2{ \left ( \frac{3}{2} \right )} $$
然而，這不是最優的。將其壓縮成兩個統一的位浪費了很多精力。我們能做得更好嗎？是的。例如，考慮將兩個骰子滾動在一起，繪製制服 $ n $ 在……之外 $ \mathbb{Z}_{36} $ . 然後我們可以應用相同的算法，但返回 5 位而不是 4 位，因為 $ 32 < 36 $ . 同樣，遞歸的機率也較低 $ \frac{4}{36} $ 這意味著我們正在浪費更少的時間和熵。
我們也可以擲三個骰子，畫畫 $ n $ 在……之外 $ \mathbb{Z}_{216} $ ，但這不是最優的，即使我們可以提取七位，遞歸的機率是 $ \frac{88}{216} $ 這比僅使用單個晶片要高得多。
所以，很明顯，“訣竅”是選擇整數個骰子，使得 $ 6^k $ 非常接近（但大於）二的冪，以最小化遞歸機率並最大化我們對熵的使用。可以編寫一個電腦程序來根據某些效率指標找到最佳擲骰數，具體取決於您的應用程序的需求（或者可能存在一般需求）。
這背後的“直覺”是您不能使用任意數量的熵，因為該位是可能的絕對最小資訊量。任何剩餘的非整數熵必須“留下”（這裡我們使用遞歸過程來消除它，但還有其他替代方案*）。
但是，如果您可以通過非破壞性過程（這裡，同時擲多個骰子）組合多個這樣的非整數熵，您自然會得到更多的整數熵（ $ 0.5 + 0.5 = 1 $ ) 可以讓您更好地利用原本必須扔掉的東西。
*該問題的答案還表明，就效率而言，遞歸併不是最佳方法。