взвешенная случайная 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 << ", ";
}