Weighted random selection with and without replacement

by

One of the fastest ways to make many with replacement samples from an unchanging list is the alias method. The core intuition is that we can create a set of equal-sized bins for the weighted list that can be indexed very efficiently through bit operations, to avoid a binary search. It will turn out that, done correctly, we will need to only store two items from the original list per bin, and thus can represent the split with a single percentage.

Let’s us take the example of five equally weighted choices, (a:1, b:1, c:1, d:1, e:1)

To create the alias lookup:

  1. Normalize the weights such that they sum to 1.0. (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) This is the probability of choosing each weight.

  2. Find the smallest power of 2 greater than or equal to the number of variables, and create this number of partitions, |p|. Each partition represents a probability mass of 1/|p|. In this case, we create 8 partitions, each able to contain 0.125.

  3. Take the variable with the least remaining weight, and place as much of it’s mass as possible in an empty partition. In this example, we see that a fills the first partition. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) with (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

  4. If the partition is not filled, take the variable with the most weight, and fill the partition with that variable.

Repeat steps 3 and 4, until none of the weight from the original partition need be assigned to the list.

For example, if we run another iteration of 3 and 4, we see

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) with (a:0, b:0.15 c:0.2 d:0.2 e:0.2) left to be assigned

At runtime:

  1. Get a U(0,1) random number, say binary 0.001100000

  2. bitshift it lg2(p), finding the index partition. Thus, we shift it by 3, yielding 001.1, or position 1, and thus partition 2.

  3. If the partition is split, use the decimal portion of the shifted random number to decide the split. In this case, the value is 0.5, and 0.5 < 0.6, so return a.

Here is some code and another explanation, but unfortunately it doesn’t use the bitshifting technique, nor have I actually verified it.

More Related Contents:

  1. Pick N distinct items at random from sequence of unknown length, in only one iteration
  2. Weighted random sample in python
  3. Python: Choose random line from file, then delete that line
  4. How to hash a string into 8 digits?
  5. Generate ‘n’ unique random numbers within a range [duplicate]
  6. Cost of len() function
  7. Quicksort with Python
  8. How to generate a random number with a specific amount of digits?
  9. Python random sample with a generator / iterable / iterator
  10. Modular multiplicative inverse function in Python
  11. How to trace the path in a Breadth-First Search?
  12. Random row selection in Pandas dataframe
  13. How to generate random numbers that are different? [duplicate]
  14. Representing and solving a maze given an image
  15. Sampling uniformly distributed random points inside a spherical volume
  16. Rotate image and crop out black borders
  17. Gauss-Legendre Algorithm in python
  18. Difference between np.random.seed() and np.random.RandomState()
  19. How to invert a permutation array in numpy
  20. Subset sum Problem
  21. Adjacency List and Adjacency Matrix in Python
  22. Binary search algorithm in python
  23. Random non overlapping circles(with circle number controlled) in python and pygame
  24. All possible paths from one node to another in a directed tree (igraph)
  25. fastest method of getting k smallest numbers in unsorted list of size N in python?
  26. Mergesort with Python
  27. Best way to randomize a list of strings in Python [duplicate]
  28. Find non-common elements in lists
  29. Generate random number in range excluding some numbers
  30. Can Python’s set absence of ordering be considered random order?

Leave a Comment