Data structures for loaded dice?

by

You are looking for the alias method which provides a O(1) method for generating a fixed discrete probability distribution (assuming you can access entries in an array of length n in constant time) with a one-time O(n) set-up. You can find it documented in chapter 3 (PDF) of “Non-Uniform Random Variate Generation” by Luc Devroye.

The idea is to take your array of probabilities pk and produce three new n-element arrays, qk, ak, and bk. Each qk is a probability between 0 and 1, and each ak and bk is an integer between 1 and n.

We generate random numbers between 1 and n by generating two random numbers, r and s, between 0 and 1. Let i = floor(r*N)+1. If qi < s then return ai else return bi. The work in the alias method is in figuring out how to produce qk, ak and bk.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  3. What distribution do you get from this broken random shuffle?
  4. Select k random elements from a list whose elements have weights
  5. Pseudorandom Number Generator – Exponential Distribution
  6. Choosing n numbers with fixed sum
  7. design a stack such that getMinimum( ) should be O(1)
  8. True random number generator [closed]
  9. Skip List vs. Binary Search Tree
  10. Generating shuffled range using a PRNG rather than shuffling
  11. Randomly choosing from a list with weighted probabilities
  12. What are probabilistic data structures?
  13. Unbiased random number generator using a biased one
  14. What is tail call optimization?
  15. Find kth smallest element in a binary search tree in Optimum way
  16. Nearest neighbors in high-dimensional data?
  17. Algorithm to generate anagrams
  18. Shuffle list, ensuring that no item remains in same position
  19. How to read values from numbers written as words?
  20. Find the first un-repeated character in a string
  21. What is a bubble sort good for? [closed]
  22. How do I find a factorial? [closed]
  23. Creating a random number generator from a coin toss
  24. Given a number, produce another random number that is the same every time and distinct from all other results
  25. Hashing a Tree Structure
  26. Best way of calculating n choose k?
  27. Algorithm for permutations of operators and operands
  28. Algorithm for merging two max heaps?
  29. Why is vector array doubled?
  30. Best algorithm for matching colours.

Leave a Comment