Skip to content

<random>: Poisson approximation for binomial_distribution is not accurate #1530

@MattStephanson

Description

@MattStephanson

For binomial_distribution(t,p) with t >= 25 and t*p < 1, it is approximated by a Poisson distribution. This is not very accurate, especially for smaller values of t.

Command-line test case

c:\temp>type test.cpp
#include <cmath>
#include <iostream>
#include <random>
#include <vector>

using namespace std;

int main() {
    constexpr int it_max  = 100'000;
    constexpr int n       = 25;
    constexpr double mean = 0.99;
    constexpr double p    = mean / n;
    constexpr double var  = n * p * (1.0 - p);

    mt19937 gen;
    binomial_distribution<> dist(n, p);

    vector<int> counts(n + 1);
    for (int i = 0; i < it_max; ++i) {
        ++counts[static_cast<size_t>(dist(gen))];
    }

    double sample_mean = 0.0;
    for (size_t i = 1; i < counts.size(); ++i) {
        sample_mean += static_cast<double>(i) * counts[i];
    }
    sample_mean /= it_max;

    double sample_var = 0.0;
    for (size_t i = 0; i < counts.size(); ++i) {
        sample_var += counts[i] * pow(i - sample_mean, 2);
    }
    sample_var /= it_max - 1;

    cout << "Expected variance: " << var << endl
         << "Observed variance: " << sample_var << endl;

    return 0;
}

c:\temp>cl /EHsc test.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.28.29617 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

test.cpp
Microsoft (R) Incremental Linker Version 14.28.29617.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:test.exe
test.obj

c:\temp>.\test.exe
Expected variance: 0.950796
Observed variance: 0.985299

Expected behavior
Observed variance should be within 0.01 (~95% CI) of expected.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingfixedSomething works now, yay!

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions