Transform Biased and Uniform Random Bits Exactly

Below I treat every call to a random-bit source as an independent Bernoulli trial. Part 1 — Uniform integer from biased bits Assume the source produces independent bits with a fixed but possibly unknown bias: $$P(B_i = 1) = p,\qquad P(B_i = 0) = 1-p,$$ where $$0 0$$, so the number of attempts is finite with probability 1. However, neither stage has a fixed worst-case bound on the number of source bits. Any finite run of rejected pairs or rejected integers has positive…