Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source

You have access to a uniform primitive randM() that returns an integer in {1, 2, ..., M} and (in part C) a biased primitive toss(p) that returns 1 with unknown probability p ∈ (0, 1) and 0 otherwise.

A) rand7() from rand5()

• Task: Implement rand7() that returns a value uniformly from {1, ..., 7} using only calls to rand5().
• Requirements: unbiased (exact), almost surely terminating, and near-optimal in expected rand5() calls.
• Deliverables: (i) a correct construction; (ii) a proof of uniformity; (iii) the exact expected number of rand5() calls.

B) General randN() from randM()

• Task: For arbitrary positive integers M and N, construct randN() from randM().
• Requirements: correctness for all M, N; almost sure termination.
• Deliverables: (i) an algorithm; (ii) an upper bound on the expected number of randM() calls in terms of M and N; (iii) discuss adaptations when N ≫ M and when M ≫ N.

C) Fairness from a Biased Source

• Given toss(p) that returns 1 with unknown probability p and 0 otherwise:
  1. Construct fair_coin() that returns 0/1 with probability 1/2 each. Prove correctness and derive the expected number of tosses as a function of p.
  2. Extend to sample uniformly from {1, ..., K} using only toss(p). Analyze termination and expected complexity.