Transform Biased and Uniform Random Bits Exactly

Reason about two random-bit transformations. Explain the construction and prove the output probabilities; a few successful samples are not sufficient evidence of correctness. ### Part 1 — A uniform integer from a biased bit source `getRandom01Biased()` returns 0 with probability `p` and 1 with probability `1 - p`. Construct `getRandom06Uniform()` that returns each integer from 0 through 6 with probability `1/7`, without needing to know `p`. Identify the assumptions about successive calls that your construction needs, and discuss whether the task is possible for every value of `p`. #### What This Part Should Cover - Removal of the unknown bias and generation of exactly seven equally likely outcomes. - A proof using the probabilities of accepted events. - Termination and expected source-call cost, including degenerate or dependent sources. ### Part 2 — A biased bit from a uniform bit source Given `getRandom01Uniform()`, construct a generator with a specified bias `p`. Use the same convention as Part 1: return 0 with probability `p` and 1 with probability `1 - p`. Explain how the representation of `p` affects an exact implementation. Cover a rational probability and distinguish an exact procedure from rounding a finite-precision random number. #### What This Part Should Cover - An exact construction using independent fair bits. - The endpoint probabilities and invalid probability inputs. - Rejection or refinement that avoids a systematic rounding or modulo bias. ### What a Strong Answer Covers - Explicit independence and probability-representation assumptions. - A distinction between almost-sure termination and a fixed worst-case call limit. - Correct use of the requested 0-probability convention in both transformations. ```hint Compare two different two-call outcomes Under a fixed independent bias, compare the probability of 01 with the probability of 10 before deciding which observations to keep. ``` ### Follow-up Questions - Why does mapping a uniform three-bit integer with remainder modulo 7 create bias? - What can a histogram test reveal, and what can it not prove about the generator?