Unbiased random number generator using a biased one

by

The events (p)(1-p) and (1-p)(p) are equiprobable. Taking them as 0 and 1 respectively and discarding the other two pairs of results you get an unbiased random generator.

In code this is done as easy as:

int UnbiasedRandom()
{
    int x, y;

    do
    {
        x = BiasedRandom();
        y = BiasedRandom();
    } while (x == y);

    return x;
}

More Related Contents:

  1. Select k random elements from a list whose elements have weights
  2. Data structures for loaded dice?
  3. Choosing n numbers with fixed sum
  4. What should be the algorithm of the below statement?
  5. Unique (non-repeating) random numbers in O(1)?
  6. Expand a random range from 1–5 to 1–7
  7. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  8. What distribution do you get from this broken random shuffle?
  9. Pseudorandom Number Generator – Exponential Distribution
  10. Shuffle list, ensuring that no item remains in same position
  11. True random number generator [closed]
  12. Probability of collision when using a 32 bit hash
  13. Fastest primality test
  14. Create a random permutation of 1..N in constant space
  15. Creating a random number generator from a coin toss
  16. Given a number, produce another random number that is the same every time and distinct from all other results
  17. What is a loop invariant?
  18. Random points inside a parallelogram
  19. Reservoir sampling
  20. Generating shuffled range using a PRNG rather than shuffling
  21. Randomly choosing from a list with weighted probabilities
  22. A Good and SIMPLE Measure of Randomness
  23. What are probabilistic data structures?
  24. Constant Amortized Time
  25. What would cause an algorithm to have O(log n) complexity?
  26. Need for predictable random generator
  27. How to compute a 3D Morton number (interleave the bits of 3 ints)
  28. Enumerating all paths in a directed acyclic graph
  29. An algorithm to space out overlapping rectangles?
  30. Reverse complex 2D lookup table

Leave a Comment