3

问题描述

有时我使用 Mersenne Twister 引擎从均匀分布中得到相同的随机数，即使我正确使用了引擎并对其进行了迭代。我知道引擎的可能状态的数量是有限的，可能生成的值的数量也是有限的，但现在情况并非如此。

使用 boost 的实现，在范围 [0; 上生成 1e6 个均匀分布的随机值；1e7)。这意味着可能的值比所需的随机值数量要多。但是，我经常得到相同的值，有时在这个范围内超过 100 倍。这怎么可能？

代码

提供了一个简单的代码来重现这种情况。在两个平台上我都遇到了同样的问题：

  • 带有 boost-random:x64-windows 1.71.0 的 MSVS 2019 和
  • g++ (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609 与 libboost-dev 1.58.0.1ubuntu1
#include <iostream>
#include <chrono>

#include <boost/random/mersenne_twister.hpp>          // random number generator
#include <boost/random/uniform_real_distribution.hpp> // uniform distribution generator
using namespace std;

int main()
{
    size_t seed = static_cast<int> (std::chrono::system_clock::now().time_since_epoch().count());
    cout << "seed = " << seed << endl;
    
    boost::random::mt19937 engine(seed);                         // the random number generator engine
    boost::random::uniform_real_distribution<double> u(0, 1e7);  // uniformly distributed double values on the range [0; 1e7)
    cout.precision(20);
    vector<double> history;                                      // stores the generated values for comparison
    for (size_t i = 0; i < 1e6; ++i)
    {
        history.push_back(u(engine));
        for (size_t j = 0; j < i; ++j)
            if (history[i] == history[j])
                cout << "Equal values ("<< history[i] <<") at ID = " << i << " and " << j << endl;
    }
}

问题

代码中是否存在产生相同值的错误？或者它是boost中的一个错误？

对于我的任务，生成具有均匀分布的数字很重要。找到相同的值是最简单的测试之一，但还有更多，我确信我不想对像 Boost 这样的知名库进行质量分析。我不想使用标准库，因为不能保证两个不同的编译器会为相同的种子值提供相同的序列，但这是任务的要求。你能建议什么样的解决方案？

笔记

如果将生成的值与生成的值进行比较，则会看到一种奇怪的行为std::random generates。来自random::boost种子 4561565448989 的值的示例是

1755586.0406719148159
3354420.976247638464   <--
3630764.0071026980877
3488445.2889673411846  <--
7920481.4555123448372
8773544.1024415194988  <--

而标准库生成

3354420.9766563926823  <--
3488445.2898126943037  <--
8773544.1042856499553  <--
...

也就是说，boost 序列中每一秒生成的值都非常接近标准库实现中的对应值。当 boost-sequence 中的两个值相等时，standard-library-sequence 中的值不相等，而是彼此接近。MSVS 和 g++ 编译器也有相似之处，它们有权对 Mersenne Twister 和发行版有不同的实现。

更新

可怜的种子？

有人提出，可能是种子值差导致了这种现象，因为size_t只能2^64生成许多不同的初始状态。更糟糕的是，我们的生命很短暂，可能的时间价值更小。虽然这是真的，但它并不能解释为什么不同的状态会多次生成相同的数字。毕竟，引擎只启动一次，所以我从 64 位子集中选择了一个状态，它是所有可能状态的子集。

如果我多次启动引擎并且我在不同（但不够不同）启动的引擎的序列中发现相同的值，那么糟糕的种子可能是一个原因。

它是分发生成器

如果使用标准的 MT 引擎，但使用 boost 的分布，问题仍然存在。但是如果引擎是boost的引擎并且分配是标准的，那么问题就消失了。问题是，正如彼得指出的那样，统一分布取决于我使用 boost 的平台。

一些统计数据

我对分布进行了一些分析。使用相同的boost::random::mt19937 engine，但无论是 boost's 还是 std's uniform_real_distribution<double> u(0, 1)，我生成了值对并研究了它们的差异并绘制了它们的相关积分I ( x )，即两个值比x更接近的概率。为U [0; 1) 是一维域，I ( x ) 以线性函数开始，用于小x值（并且趋于 1）。结果如下图所示。 显示 std 和 boost 的相关积分以及期望值的图 该图表明来自 boost 实现的分布不仅有偏差，而且只有 4 个可能的距离值，而众所周知doubles 更密集，std 确实产生了更大的距离值谱。

错误还是不是错误？已删除的答案

一个已被删除的答案建议提高种子值，但到目前为止，事实证明这不是问题的根源。从那以后，我也在boost 的 github上发布了这个问题，但仍然不清楚问题出在哪里。这可能是 boost 中的一个错误，但即使在这种情况下，这个 SO 源也可以帮助其他人识别其分发生成器中的问题。

4

1 回答 1

2

这不是 Boost 中的错误。问题是由于较旧的 32 位 MersenneTwister 提供的分辨率有限。您在累积分布上看到的步骤等于 2 -32 ~ 10 -10。几年前，我意识到了一个代价高昂的现实世界模拟失败。解决方案是使用能够产生全精度双精度的 RNG，同时通过所有统计测试套件，例如 MersenneTwister64 或 MIXMAX，后者现在在 Boost 中可用。

于 2019-11-26T19:49:54.200 回答