加权随机n次优化

Question

一个数组中有10个加权元素。我想随机选择一个元素N次，然后计算每个元素出现的次数。是否有一种算法可以在不需要选择N次的情况下为我提供元素计数<代码>N可能是一个很大的数字，在这种情况下，必须生成N个样本是低效的。

例如：一个盒子里有2个红色的球和8个白色的球。从盒子里随机挑选一个球，然后放回去，重复100次。计算拾取红色球或白色球的总次数。

我想知道是否有可能在不进行100次采样的情况下获得计数。

Answer 1

假设数组有n个元素。设X1，X2。。。，Xn表示随机变量，其中Xi表示第n个元素出现的次数，然后以X1=X1，X2=X2。。。，X（i-1）=X（i-1），Xi服从二项分布，参数为（N-x1-x2-…-X（i-1））和1/（N-i 1）。所以你可以画X1，X2。。。，Xn按如下顺序：

#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 << ", ";
}