Creating a random number generator from a coin toss

by

You can build a rng for the smallest power of two greater than n as you described. Then whenever this algorithm generates a number larger than n-1, throw that number away and try again. This is called the method of rejection.

Addition

The algorithm is

Let m = 2^k >= n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= n
return r

The probability that this loop stops with at most i iterations is bounded by 1 - (1/2)^i. This goes to 1 very rapidly: The loop is still running after 30 iterations with probability less than one-billionth.

You can decrease the expected number of iterations with a slightly modified algorithm: 

Choose p >= 1
Let m = 2^k >= p n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= p n
return floor(r / p)

For example if we are trying to generate 0 .. 4 (n = 5) with the simpler algorithm, we would reject 5, 6 and 7, which is 3/8 of the results. With p = 3 (for example), pn = 15, we’d have m = 16 and would reject only 15, or 1/16 of the results. The price is needing four coin flips rather than 3 and a division op. You can continue to increase p and add coin flips to decrease rejections as far as you wish.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Expand a random range from 1–5 to 1–7
  3. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  4. What distribution do you get from this broken random shuffle?
  5. Select k random elements from a list whose elements have weights
  6. Data structures for loaded dice?
  7. Pseudorandom Number Generator – Exponential Distribution
  8. Choosing n numbers with fixed sum
  9. Shuffle list, ensuring that no item remains in same position
  10. True random number generator [closed]
  11. Create a random permutation of 1..N in constant space
  12. Given a number, produce another random number that is the same every time and distinct from all other results
  13. Random points inside a parallelogram
  14. Reservoir sampling
  15. Generating shuffled range using a PRNG rather than shuffling
  16. Randomly choosing from a list with weighted probabilities
  17. A Good and SIMPLE Measure of Randomness
  18. Unbiased random number generator using a biased one
  19. Calculate the sum with minimum usage of numbers
  20. What is the optimal algorithm for the game 2048?
  21. Reverse the ordering of words in a string
  22. Converting a Uniform Distribution to a Normal Distribution
  23. Can hash tables really be O(1)?
  24. Fast way to calculate n! mod m where m is prime?
  25. Sum-subset with a fixed subset size
  26. Travelling Salesman with multiple salesmen?
  27. What is amortized analysis of algorithms? [closed]
  28. need an algorithm for collapsing netblock ranges into lists of superset ranges
  29. Why is vector array doubled?
  30. Can brute force algorithms scale?

Leave a Comment