Alias Sampling (Seeded)

Problem

Sample n values from a discrete distribution over probs using Walker's alias table and random.Random(seed). For each draw pick a column uniformly, keep it with prob[col], and otherwise take alias[col]. Return the counts per value.

Return [] for an empty distribution or n <= 0.

Hint

Sampling from an alias table costs O(1) per draw after the build.

Test cases

case 1

in: [[0.5,0.5],1000,42]

expected: [491,509]

case 2

in: [[0.7,0.3],2000,7]

expected: [1419,581]

case 3

in: [[0.3333333333333333,0.3333333333333333,0.3333333333333333],900,123]

expected: [310,314,276]

case 4

in: [[1],100,0]

expected: [100]

case 5

in: [[],10,1]

expected: []

Starter codePython

import random


def alias_sample_seeded(probs, n, seed):
    # Your code here
    pass

5 test cases · run your code against them in the editor