logo标签列表

生成随机布尔值

c++randomboolean
11

我目前正在使用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++中有更好的方法？

4
如果没有重复，序列将是无限交替的“true”和“false”，这意味着零熵（随机性），因此有重复是正常的。 - François Andrieux
1
你如何判断随机性？有什么说法可以证明在一系列数据中出现30个真值，2个假值和30个真值并不是随机的？ - DeiDei
8
这段代码是在判断随机生成的数字是否等于1，其中rand() % (1 - 0 + 1)用来生成0或1两个数中的一个。相比于rand() % 2，这个方法能够确保在更多的编译器和平台上生成真正的随机数。 - n. m.
2
  1. rand()因其底位不随机而著名（这就是你要测试的内容）。
  2. 它真的随机吗？绝对不是（但在计算机上，很少有东西是真正随机的）。但是还有一些具有更好熵的系统（例如std::random）。
  3. 在真正的随机系统中，连续出现某个数值并不罕见；在足够大的输入集中，它们很可能会发生（不会不太可能出现）。
 - Martin York
1
@n.'pronouns'm. 哈哈哈，读完那些废话后我的第一个想法就是LMFAO！特别是(1 - 0 + 1)这部分。如果他们的目标是“最奇怪的表示2的方式”，他们也可以写成(232783 - 232782 + 1) :P - Kenny83
显示剩余2条评论
6个回答
21

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比率，那么您可以创建一个介于0和1之间的随机浮点数，并将小于某个阈值z的值设置为真，否则为假。

关于出现长时间连续相同布尔值的原因

我还没有解释为什么您的代码会出现30个“真”或“假”的连续值。虽然rand()不应再使用，并且您的代码中似乎存在一些不必要的加减一和零，但不应该出现这样的问题。但是，我现在意识到您问题中的文本含义不明确。如果您连续运行并退出程序30次，则应该预期看到重复的值-即使使用我的代码也是如此。大多数随机数生成器实际上是伪随机数生成器。每次运行程序时，它们都将产生相同的随机数字序列；这对于结果的一致性非常重要。但是，在程序运行时（例如将您的randomBool()放入循环中），您不应该看到如此长的连续段，因为它们将非常不可能。

长时间连续相同布尔值的不可能性

我很惊讶收到评论表示不同意我的观点，即随机布尔值的30个“真”或“假”的连续段是不可能的（当真或假等概率时）。我意识到人们对概率的一个常见误解是“运气”会尝试平衡事物，所以如果硬币抛掷已经连续出现几次正面朝上，则宇宙将尝试纠正这一点，并使反面更有可能。由于这种误解，人们低估了得到所有正面或所有反面的连续段的可能性，我认为这个答案和主要问题的评论的动机是纠正这个常见错误。

然而，存在一个真正的原因，长时间的连续段（特别是30个）越来越不可能。使用随机无偏硬币投掷的术语，每个独立同分布的硬币投掷只有50%的机会与前一个相同。因此，长连续段的概率随着连续段长度的增加呈指数级下降。对于长度为L的连续段，全是正面朝上的概率是2^L；任一类型的连续段概率是2^L或1/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万分之1。由于在1e8次投掷中有约1e8/24 ~ 430万个这样的独立区间，我们预计会出现很少这样的连续投掷，因此这似乎是正确的[但需要注意的是，精确计算期望比较困难]。与此同时，长度为30的连续投掷在任意独立的30次投掷中出现的概率为537百万分之1，甚至比长度为24的连续投掷更不可能发生。

1
@NathanOliver 五个随机布尔值连续相等的概率是2种情况（全为真或全为假）中的一种，总共有2^5=32种可能性，即1/16 -- 不太可能。但对于30个情况，概率是2/2^30 -- 或者说是5.37亿分之一。 - jwimberley
@jwimberley 概率不是这样累积的。每次投掷硬币时，您有50/50的机会。之前的结果不重要。这使得连胜变得非常容易。 - NathanOliver
2
我鼓励你们两个运行一些模拟，并计算出你们发现长串的频率。连续5个或更多值的串是相当合理和可能的，但随着串长度的增加，概率呈指数级下降，这正是因为翻转是IID事件，每次新的翻转只有50%的机会与之前的相同。 - jwimberley
好的。我使用您的代码，在 100,000 次迭代中获得了 19 的连续性：http://coliru.stacked-crooked.com/a/8b3c2ef406a1f409 - NathanOliver
@NathanOliver 很好，你的新结果完全可信。你必须承认，你无法产生长度为30的连续串（比长度为18的连续串更不可思议）。 - jwimberley
显示剩余5条评论
3
bool randomBool() {
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

这可能是将rand()的输出转换为布尔值的最糟糕的方法之一。在许多实现中，低位比高位的随机性要差得多。
理想情况下，您应该完全使用其他方法，但如果必须使用rand()，请尝试以下方法：
bool randomBool() {
   return rand() > (RAND_MAX / 2);
}
使用您的测试代码运行100,000次，这将返回一个最长连续出现18次的结果。 - David Schwartz
2

这是一个C++11函数模板，用于生成具有指定概率（默认为0.5表示均匀分布）的布尔结果（二项式分布）：

Original Answer翻译成"最初的回答"

#include <random>
template <typename Prob = double>
bool binomial_trial(const Prob p = 0.5) {
    static auto dev = std::random_device();
    static auto gen = std::mt19937{dev()};
    static auto dist = std::uniform_real_distribution<Prob>(0,1);
    return (dist(gen) < p);
}
2
在现代C++中，有一种专门的方式可以生成随机布尔值——通过伯努利分布：
#include <random>

bool randomBoolean() {
  static std::default_random_engine generator(std::random_device{}());
  // With p = 0.5 you get equal probability for true and false
  static std::bernoulli_distribution distribution(0.5);
  return distribution(generator);
}

详情请参见此处

1
伪随机数生成器的低位比特往往提供的随机性较少。这对于内置的rand()函数尤其如此，它通常实现为LCG。生成随机的bool的最佳方法是使用MSB位。实际上，这是一个标准的Bernoulli分布，概率为1/2。
#include <cmath>
#include <cstdlib>

inline bool random_bool()
{
   static const int shift = static_cast<int>(std::log2(RAND_MAX));
   return (rand() >> shift) & 1;
}
0

如果rand()是真正的伪随机数生成器，那么它就是真正的伪随机数生成器，尽管如果RAND_MAX是偶数（即偶数比奇数多一个），分布可能会非常轻微地不均匀。但通常RAND_MAX足够大，差异可以忽略不计。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接