根据一系列硬币翻转生成从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。在最坏情况下所需的翻转数仍然是无限的，但这种情况永远不会出现。