生成随机布尔值

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++ 中有更好的方法？

原文由 Null User 发布，翻译遵循 CC BY-SA 4.0 许可协议

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++ 参考中找到有关此库的更多详细信息。例如，如果您想要的不是“真”和“假”值的 ⁵⁰⁄₅₀ 比率，则可以创建一个介于 0 和 1 之间的随机浮点数，并将小于某个阈值 z 的值称为真，否则为假。

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

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

长条纹的可能性不大

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

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

原文由 jwimberley 发布，翻译遵循 CC BY-SA 3.0 许可协议