c++ - 生成随机 boolean 值

Question

我目前正在实现 Eller's Algorithm在 C++ 中，关于迷宫的随机性，一个小细节困扰着我。

到目前为止，我使用以下代码生成随机 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 的随机整数来模拟随机 boolean 值:

#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 比率的“真”和“假”值，您可以创建一个介于 0 和 1 之间的随机 float ，并将小于某个阈值 z 的值称为真，否则为假。

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

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

长时间连续出现的可能性不大

我很惊讶地收到不同意我的断言的评论，即连续出现 30 个“真”或“假”随机 boolean 值是不可能的(当真或假的可能性相同时)。我意识到对概率的一个常见误解是“运气”试图平衡事情，所以如果一次抛硬币连续几次出现正面，那么宇宙将尝试纠正这一点并使反面更多可能。由于这种误解，人们低估了获得所有正面和所有反面条纹的可能性，我认为对这个答案和主要问题的评论的动机是为了纠正这个常见错误。

但是，有一个真实的原因，那就是长时间连续(尤其是长达 30 次)越来越不可能了。使用随机无偏硬币抛掷的语言，每次 IID(独立同分布)硬币抛掷与前一次相同的概率只有 50%。因此，长条纹的概率随条纹的长度呈指数下降。对于长度为L的连胜，所有头朝上的连胜概率是2^L中的1；任何一种类型的连续出现的概率是 2^L 中的 2 或 2^(L-1) 中的 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 次 throw 串中，出现这种长度的连胜概率为 2^(24-1) 分之一，或大约 800 万分之一。由于在 1e8 次 throw 中大约有 1e8/24 ~ 430 万次这样的单独延伸，我们预计会有少量这样的条纹，所以这似乎是正确的 [我上面的警告是计算准确的期望值很困难]。与此同时，长度为 30 的连胜在任何独立的 30 次翻转中出现的概率为 5.37 亿分之一，甚至比长度为 24 的连胜的可能性要低得多。