Generate uniform 0–6 from biased coin

You are given a function:

• int getRandom01Biased() returns 0 with probability p and 1 with probability 1-p, where p is unknown and may be any value in (0,1).

Design and implement:

• int getRandom06Uniform() that returns an integer in [0,6] with exactly uniform probability 1/7.

Constraints/notes:

• You may call getRandom01Biased() multiple times.
• The algorithm must be correct for any p in (0,1).
• Discuss expected number of calls (at least at a high level).

Generate Uniform 0–6 from a Biased Coin

You are given access to a biased coin through a function getRandom01Biased() that returns 0 with probability p and 1 with probability 1-p, where p is unknown and can be any value in (0,1). Design an algorithm getRandom06Uniform() that returns each integer in [0, 6] with exactly equal probability 1/7, no matter what p is.

For this coding version, the random coin is modeled deterministically by a list stream of 0s and 1s. Read the list from left to right as consecutive outputs of getRandom01Biased().

Your task is to simulate the correct exact algorithm:

1. Build an unbiased random bit using pairs of biased outputs:
   • 01 -> 0
   • 10 -> 1
   • 00 and 11 are discarded
2. Use three unbiased bits to form a number in [0, 7].
3. If the number is 7, reject it and repeat.
4. Return the first accepted value in [0, 6].

This algorithm is correct for every p in (0,1). In the real probabilistic setting, each unbiased bit needs 1 / (p(1-p)) biased calls in expectation, and the full [0,6] generator needs 24 / (7p(1-p)) biased calls on average.

Examples

Example 1

Input: [0,1,0,1,1,0]
Output: 1

Explanation: Pairs are 01 -> 0, 01 -> 0, 10 -> 1, so the unbiased bits are 001, which is 1.

Example 2

Input: [1,0,1,0,0,1]
Output: 6

Explanation: Pairs are 10 -> 1, 10 -> 1, 01 -> 0, so the unbiased bits are 110, which is 6.

Hints

1. A pair of outcomes 01 and 10 have the same probability, even when the coin is biased.
2. Once you can generate fair bits, think about creating a value in [0,7] and using rejection sampling.