生成随机布尔值

Question

我目前正在用C++ 实现Eller算法,一个小细节让我对迷宫的随机性感到烦恼.

到目前为止,我使用以下代码生成随机bool:

bool randomBool()
{
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

// In main.cpp

time_t seconds;
time(&seconds);
srand((unsigned int) seconds);

但经过调试,我经常看到重复true或false生成,有时连续多达30次.

这个算法是真正随机的还是在C++中有更好的方法？

Answer 1

C++ 11中的STL构建了优于rand().的随机数生成方法.您可以通过0或1的随机整数模拟随机布尔值:

#include <iostream>
#include <random>

int main(int argc, char *argv[]) {
    auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    const unsigned int N = 100;
    unsigned int numTrue = 0;
    unsigned int numFalse = 0;
    for (int i = 0; i < 100; ++i) {
        bool b = gen();
        if (b) ++ numTrue;
        else ++numFalse;
    }
    std::cout << numTrue << " TRUE, " << numFalse << " FALSE" << std::endl;
}

您可以在标准C++参考中找到有关此库的更多详细信息.例如,如果您想要50/50比率的"true"和"false"值以外的其他值,则可以创建0到1之间的随机浮点数,并调用小于某个阈值的值z为true,否则为false.

我想,为什么你会看到长条纹

我没有解释为什么你的代码连续获得30个"true"或"false"值.虽然rand()不应该再使用,并且你的代码中似乎有一些不必要的加法和减法,但应该没有这样的问题.但是,我现在意识到你问题中的文字含糊不清.如果您连续30次运行并退出程序,您应该会看到重复的值 - 即使使用我的代码.大多数随机数生成器实际上是伪随机数生成器.每次运行程序时,它们都会产生相同的随机数序列; 这对于结果的一致性很重要.然而,当程序运行时(例如,将你randomBool()放在一个循环中),你不应该看到这样长度的条纹,因为它们是非常不可能的.

长条纹的不可能性

我很惊讶地收到不同意我的断言的评论,即30条"真实"或"虚假"的随机布尔是不可能的(当真或假同样可能时).我意识到对概率的一个常见误解是"运气"试图将事情解决掉,所以如果投掷硬币连续几次出现,那么宇宙将试图纠正这个问题并使尾巴更多有可能.由于这种误解,人们低估了所有头部和所有尾巴的条纹的可能性,我认为对这个答案和主要问题的评论的动机是纠正这个常见的错误.

然而,有一个真正的原因,长条纹(特别是长达30条)越来越不可能.使用随机无偏硬币抛出的语言,每个IID(独立且相同分布的)抛硬币只有50%的机会与之前相同.因此,长条纹的概率随着条纹的长度呈指数下降.对于长度为L的条纹,所有头部条纹的概率为1 ^ 2 ^ L; 任何一种条纹的概率是2 ^ 2 L或1 in 2 ^(L-1).以下是一些演示代码:

#include <iostream>
#include <random>
#include <map>

bool randomBool() {
    static auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    return gen();
}

int main(int argc, char *argv[]) {

    const unsigned int N = 1e8;
    std::map<unsigned int,unsigned int> histogram;
    bool current = randomBool();
    unsigned int currentLength = 1;
    for (int i = 0; i < N; ++i) {
        bool b = randomBool();
        if (b == current) {
            ++currentLength;
        } else {
            auto it = histogram.find(currentLength);
            if (it != histogram.end())
                it->second += 1;
            else
                histogram.insert(std::make_pair(currentLength,1));
            currentLength = 1;
        }
        current = b;
    }

    for (auto pair : histogram) 
        std::cout << "STREAK LENGTH " << pair.first << " OCCURS " << pair.second << " TIMES" << std::endl;
}

输出直方图是:

STREAK LENGTH 1 OCCURS 25011106 TIMES
STREAK LENGTH 2 OCCURS 12503578 TIMES
STREAK LENGTH 3 OCCURS 6249056 TIMES
STREAK LENGTH 4 OCCURS 3125508 TIMES
STREAK LENGTH 5 OCCURS 1560812 TIMES
STREAK LENGTH 6 OCCURS 781206 TIMES
STREAK LENGTH 7 OCCURS 390143 TIMES
STREAK LENGTH 8 OCCURS 194748 TIMES
STREAK LENGTH 9 OCCURS 97816 TIMES
STREAK LENGTH 10 OCCURS 48685 TIMES
STREAK LENGTH 11 OCCURS 24327 TIMES
STREAK LENGTH 12 OCCURS 12176 TIMES
STREAK LENGTH 13 OCCURS 6149 TIMES
STREAK LENGTH 14 OCCURS 3028 TIMES
STREAK LENGTH 15 OCCURS 1489 TIMES
STREAK LENGTH 16 OCCURS 811 TIMES
STREAK LENGTH 17 OCCURS 383 TIMES
STREAK LENGTH 18 OCCURS 193 TIMES
STREAK LENGTH 19 OCCURS 104 TIMES
STREAK LENGTH 20 OCCURS 43 TIMES
STREAK LENGTH 21 OCCURS 20 TIMES
STREAK LENGTH 22 OCCURS 14 TIMES
STREAK LENGTH 23 OCCURS 4 TIMES
STREAK LENGTH 24 OCCURS 3 TIMES

难以计算多个翻转N中的长度L的预期条纹数,因为存在许多长度L的重叠区段,其中可存在这样的条纹.但请注意,此直方图遵循大致指数分布,每个条目大约是前一个条目的一半.

最大连胜数为24 [注意:之前版本中的一个错误计为23].在任何24个投掷的独立字符串中,该长度连续的概率是1 ^ 2 ^(24-1),或者约为800万.由于在1e8投掷中大约有1e8/24~430万个这样的单独延伸,我们期待少量这样的条纹,所以这似乎是正确的[我的上述警告,计算确切的期望是困难的].同时,在30次翻转的任何独立延伸中,长度为30的条纹在5.37亿的概率为1,并且甚至比长度24的条纹更不可能.