一個骰子投出1~4的概率五分之一，5~6的概率是十分之一，如何設計可以得到1~9的等概率數字?

12-06

昨天筆試秒針系統的題目，沒有思路

個人意見，這類題的思路是：先算出預期想要達到的概率，然後再尋找不同的數字的組合來儘可能接近（但不超過）這個概率。

就本題而言，要得到1-9的等概率數字，則每個數的概率要1/9，但題目中的概率很難通過概率組合直接達到1/9，所以先找一個比它略小的概率，比如顯然本題中，1/10的概率是容易達到的。

所以很容易給出一種方法：

先擲1次，如果擲出的是5或6，則得到5或6；
如果擲出的是1-4，則再擲第2次，綜合兩次的結果；

1+奇數 —&>1
2+奇數 —&>2
3+奇數 —&>3
4+奇數 —&>4
5 —&>5
6 —&>6
1+偶數 —&>7
2+偶數 —&>8
3+偶數 —&>9
4+偶數 —&>重來

以上每個結果的概率都是 1/10
平均擲的次數為： $left( frac{1}{5} +frac{4}{5} imes 2 ight) imes frac{10}{9}=2$

以上只提供一種較為簡單的方法，但這並不是效率最高的。

以下結論為個人腦補，不一定可靠，如有錯誤請指出：
對於有a種可能的隨機數樣本（不管每種可能的概率有多大），要通過某種對應生成有b種可能的隨機數樣本，最高轉化率為 $log_{b}a$

就本題來說，最高轉化率為 $log_{9}6approx 0.815$ ，平均最少需要擲 1.23 次就可以完成轉換。

當然，這只是理論上的最高效率，實際上要找到哪怕是接近這個效率的方案都是不太容易的。

脫離原題目，補充一下 @曾加答案裡面的的猜想。
其實可以用資訊理論來解釋。一個骰子投一次結果所包含的信息量可以用下面這個公式算出來：
$-sum_{i} p_i log_2(p_i)$
如果只有6種結果，各種結果等概率的情況下包含的信息量最大，其值是 $log_2 6 approx 2.585$ ，但是題目里骰子的實際信息量只有大約2.522，還要更少一些。
但是1~9的等概率數字所包含的信息量是 $log_2 9 approx 3.170$ ，所以理論上我們想輸出N個1-9的獨立等概率數字，至少需要投kN次骰子( $kapprox frac{3.170}{2.522}approx 1.257$ )。