Weighted Random Number generator with updates

Question

My question is an extension of this question: Weighted random numbers

I'm trying to implement a weighted random numbers. I'm currently just banging my head against the wall and cannot figure this out.

In my project (Hold'em hand-ranges, subjective all-in equity analysis), I'm using Boost's random -functions. So, let's say I want to pick a random number between 1 and 3 (so either 1, 2 or 3). Boost's mersenne twister generator works like a charm for this. However, I want the pick to be weighted for example like this:

1 (weight: 90) 2 (weight: 56) 3 (weight:  4)

Does Boost have some sort of functionality for this?

The extension: the user is allowed to dynamically change the weight of a given key.

How does one optimally solve the problem?

The naive solution might be to scan through all elements, adjust the weight of all elements based on the new weight...but that's O(n) for the update. It's very inefficient. How do we do better?

I want update(key, w) and get() to be better than or equal to O(logn)

Answer 1

One possible solution comes from the arithmetic coding and Fenwick trees.

If you have a list of non-negative numbers, [a_0, ... a_n] of type T, the Fenwick tree data structure allows you to implement the following two functions in O(log n) time:

1. Index upper_bound(T p): for the given value p, calculate the smallest index i, such that the prefix sum a_0 + ... + a_i > p.
2. set(Index i, T p): Update a_i <- p.

The algorithm of generating a random i is simple: generate a random number k uniformly distributed in the range [0, sum a_i) and then use i = upper_bound(k) to find i.

Simple example:

i            0 1 2 3 4 5 6 7
a_i          0 1 0 0 3 4 0 2
prefix_sum   0 1 1 1 4 8 8 10

k                   0 1 2 3 4 5 6 7 8 9
i = upper_bound(k)  1 4 4 4 5 5 5 5 7 7

P.Fenwick. A New Data Structure for Cumulative Frequency Tables (PDF, 1994)

My C++ implementation of a Fenwick tree (not thoroughly tested)

Answer 2

You have both Python and C++ tagged, I'm not sure about Python but in C++ this is actually part of the STL. Take a look at piecewise_constant_distribution.

Answer 3

With python's numpy there is a function numpy.random.choice, that allows you to set probabilities (that sums to 1). So with your weights you could do:

weights = [90, 56, 4]
np.random.choice([1, 2, 3], p=[w / sum(weights) for w in weights])

I don't know about complexities, but numpy is known to be a very efficient library, so maye you can dig up to find its documents and implementation.

Answer 4

If you are using the algorithm from the accepted answer, all you have to do, when you change a single weight is, update the sum_of_weight:

sum_of_weight -= choice_weight[index];
sum_of_weight += new_weight;
choice_weight[index] = new_weight;

Answer 5

Why not the plain simple random.choice from a weighted list (generator). Let me know if it works :

import random
generator  = [1] * 90 + [2] * 56 + [3] * 4 #1 (weight: 90) 2 (weight: 56) 3 (weight:  4)
random.choice(generator)

Answer 6

int main()
{
    std::mt19937::result_type seed = std::random_device()();
    auto engine = std::mt19937(seed);

    auto initial_weights = { 90.0, 56.0, 4.0 };
    auto distribution = std::discrete_distribution<>(initial_weights);

    // Use the original distribution
    for (auto i = 0; i != 20; ++i)
    {
        std::cout << distribution(engine) << std::endl;
    }

    std::cout << std::endl;

    // Modify the distribution temporary when generating random numbers
    for (auto i = 0; i != 20; ++i)
    {
        auto param = std::discrete_distribution<>::param_type{ 90.0 - 4.5 * i, 56.0, 4.0 + 5.0 * i };
        std::cout << distribution(engine, param) << std::endl;
    }

    std::cout << std::endl;

    // Make a permanent change to the distribution
    auto param = std::discrete_distribution<>::param_type{ 30.0, 56.0, 40.0 };
    distribution.param(param);

    // Use the modified distribution
    for (auto i = 0; i != 20; ++i)
    {
        std::cout << distribution(engine) << std::endl;
    }

    std::cout << std::endl;

    return 0;
}