math - 基于一系列硬币翻转生成从 0 到 9 的随机数

Question

我可以用什么方法来最小化 生成从 0 到 9 的均匀分布数字所需的硬币翻转量？

我做了一些研究，但我一直无法弄清楚如何使它适应这个特定问题:

Expand a random range from 1–5 to 1–7

https://www.quora.com/How-do-I-use-a-fair-6-sided-die-to-generate-a-random-number-from-1-to-20-with-each-outcome-occurring-with-the-same-probability

https://cs.stackexchange.com/questions/570/generating-uniformly-distributed-random-numbers-using-a-coin

Answer 1

抛硬币时，您至少需要 10 种可能的组合。如果硬币翻转 4 次，我们将有 16 个排列。因此，所需的最少翻转次数为 4。

通过引用你的 reference 中提到的算法，我们可以如下实现这个问题。

变量 randNum返回 0-9 之间均匀分布的随机数。

函数rand2通过为 T 和 H 分配 0 和 1 值来模拟抛硬币练习，反之亦然。

int[][][][] fourDimArr = { { { {1, 2},{3, 4} }, {{5, 6} ,{7, 8} } }, { { {9,10},{0,0} }, { {0,0},{0,0} } } };
int result = 0;
    while (result == 0)
    {
        int i = rand2();
        int j = rand2();
        int k = rand2();
        int l = rand2();
        result = fourDimArr[i][j][k][l];
    }
int randNum = result-1;

James K Polk 建议了一个更简单、更直观的实现。在下面的评论中。它涉及使用硬币翻转的结果作为四位数字的位。

通过拒绝值 >= 10 ，我们将生成一个在 0-9 之间均匀分布的随机数。有关实现，请参阅下面的代码片段。

int result = 11;
        while(result>=10){
            result = 0;
            for(int j = 0; j < 4; j++){
                result = (result<<1)|rand2();
            }
        }
randNum = result;

rand2 的一个示例实现如下:

private static int rand2() {
    if(Math.random()>0.5)return 1;
    return 0;
}

注意:所需的最小翻转次数是 4。在最坏情况下所需的翻转次数仍然是无限的，但这种情况永远不会出现。