Derive uniform RNGs from limited or biased sources

Consider a function rand5() that is already implemented. On every call, it independently outputs one of the integers in the set $\{1,2,3,4,5\}$, and each possible value has probability $1/5$.

Part A. Using only rand5(), implement a new function rand7() that returns an integer from the set $\{1,\ldots,7\}$, with each value having probability $1/7$. The procedure must be unbiased and must terminate. It should also have a near-optimal expected number of rand5() calls. Prove that the output distribution is uniform, and calculate the exact expected number of rand5() calls made by your implementation.

Part B. Generalize the same idea. Suppose you are given randM(), which samples uniformly from $\{1,\ldots,M\}$, and you need to build randN(), which samples uniformly from $\{1,\ldots,N\}$, where M and N are arbitrary positive integers. Give an algorithm that is correct for all positive M and N. State an upper bound on its expected number of randM() calls in terms of M and N. Also describe how the reduction should be approached when N is much larger than M, and when M is much larger than N.

Part C. Now a biased primitive is provided: toss(p) returns 1 with probability p and 0 with probability 1-p, where p is an unknown number strictly between 0 and 1. First, construct fair_coin(), which returns 0 or 1 each with probability $1/2$, using only toss(p). Prove that it is fair, and express the expected number of tosses as a function of p. Then extend the method to sample uniformly from $\{1,\ldots,K\}$ using only toss(p). Analyze termination and give the expected number of tosses, or an upper bound, as a function of p and K.

Example 1:

Input: none
Output: 4

Explanation: A single call to rand7() may return any integer from 1 to 7; this example shows one such possible output. The correctness requirement is that the distribution over many independent calls is uniform.

Example 2:

Input: none
Output: 1

Explanation: A single call to fair_coin() may return either 0 or 1; this example shows one possible output. Both outcomes must occur with probability $1/2$.

Constraints:

• Every call to a provided random primitive is independent.
• Only the specified primitive may be used as a source of randomness.
• M, N, and K are positive integers.
• The unknown bias satisfies $0 < p < 1$.