Uniform integer from a fair coin

Question

You can flip a fair coin as often as you like and nothing else.

Return a uniform integer in $\{0, 1, \dots, n-1\}$ . Prove uniformity, give the expected number of flips, and explain why the naive "gather bits, take mod $n$ " is biased.

Accepted Answer

Read the coin as bits. Let b = \lceil \log2 n \rceil be the smallest number of bits that can hold n-1. Assemble a b-bit number in \{0, \dots, 2^b - 1\}; if it lands below n, return it, otherwise reject and start over. Why it is uniform. Each of the 2^b bit-strings is equally likely (independent fair flips). We accept exactly the first n of them, each still equally likely, so every output 0 \dots n-1 has the same conditional probability. Rejected trials are independent and identically distributed, so restarting never favors any value. Expected flips. Each trial costs b flips and accepts with p…

Uniform integer from a fair coin

Your answer

More Coding questions