weighted random n-times optimization

user_5448398 0
Viewed 68

There are 10 weighted elements in one array. I want to select an element at random N times, and then count the number of times every element occurs. Is there an algorithm that will give me the count of elements without needing to select N times? N may be a large number, in which case having to generate N samples is inefficient.

For example: There are 2 red balls and 8 white balls in a box. Randomly pick a ball from the box, then put it back, repeated 100 times. Count the total number of times a red ball or a white ball is picked.

I want to know if it's possible to get the counts without sampling 100 times.

random algorithm c++
1 Answers

Say the array has n elements. Let X1, X2, ..., Xn denote the random variables where Xi represents the number of times the nth element occurs, then conditioned on X1 = x1, X2 = x2, ..., and X(i-1)=x(i-1), Xi obeys the binomial distribution with parameters (N - x1 - x2 - ... - x(i-1)) and 1 / (n - i + 1). So you can draw X1, X2, ..., Xn in order like this:

#include <iostream>
#include <random>

template <typename Iter, typename Int_type>
void draw(Iter begin, Iter end, Int_type N)
{
    auto n = std::distance(begin, end);
    static std::mt19937 gen{std::random_device{}()};
    while (begin != end) {
        std::binomial_distribution<Int_type> d(N, 1 / static_cast<double>(n));
        auto number = d(gen);
        *begin++ = number;
        --n;
        N -= number;
    }
}

int main()
{
    unsigned count[10];
    draw(std::begin(count), std::end(count), 10000u);
    for (auto i : count) std::cout << i << ", ";
}
user_53767890
Related