Fair Coin from a Biased Coin, Uniform 1-to-n Sampler Bug, Monte Carlo with Threads

This coding exercise has four connected parts built on random number generation: a fair coin from an unfair one, a bug hunt in a sampler built on that coin, a value estimated by simulation, and a faster version of the simulation that uses multiple threads. ### Clarifying Questions - Is the bias of the unfair coin known, and is it guaranteed to be strictly between 0 and 1? - Are successive flips of the unfair coin independent of each other? - Which language will you use, and do its threads run in parallel on several cores? ### Part 1 — A fair coin from an unfair coin You are given `biased_flip()`, which returns heads or tails, heads with a fixed probability $p$ that you do not know. Using only `biased_flip()`, implement `fair_flip()`, which returns heads and tails with probability exactly one half each. The interviewer described the method: flip the unfair coin twice; heads followed by tails counts as heads, and tails followed by heads counts as tails. Complete the method, implement it, and explain why it is fair. ```hint Some pairs decide nothing Two of the four outcomes of a pair are not mapped to an answer. Decide what to do with them, and compare the probabilities of the two pairs that are mapped. ``` #### What This Part Should Cover - What happens on the two outcomes the method does not map - Why the result is exactly fair whatever the bias is - The expected number of unfair flips per fair flip, and how it behaves as the bias becomes extreme ### Part 2 — Find the bug in a uniform sampler Next you are given code that uses `fair_flip()` to return an integer from 1 to n, each with probability 1/n, and asked to find its bug. The code from the round was not reported; the version below is an illustrative stand-in containing a bug of the kind such code tends to have. ```python def uniform_1_to_n(n: int) -> int: """Should return each of 1, 2, ..., n with probability 1/n.""" bits = max(1, (n - 1).bit_length()) # enough bits to write 0 .. n - 1 value = 0 for _ in range(bits): value = 2 * value + fair_flip() # fair_flip() returns 1 for heads, 0 for tails return value % n + 1 ``` Find the bug, show a value of n for which the output is not uniform and by how much, and fix it. Then list what else you would check when reviewing a sampler like this one. ```hint Count the outcomes For a small n that is not a power of two, list every equally likely value of `value` and see which result each one produces. ``` #### What This Part Should Cover - The defect, demonstrated with an exact count for a specific n - A fix that is exactly uniform, with the reason it is, and its expected cost in fair flips - Other defects worth checking in sampler code, such as range errors, the case n = 1, and partial redraws ### Part 3 — Estimate a value by simulation The interviewer then gives a formula for a random quantity computed with the functions above, together with the exact value that its average approaches. Compute the quantity many times in a loop and average the results to approximate that value. The formula and the value from the round were not reported; as a stand-in, estimate the expected value of the larger of two independent draws of `uniform_1_to_n(6)`, whose exact value is 161/36, about 4.472. ```hint How wrong can an average be? The error of an average of independent trials shrinks at a known rate as the number of trials grows. Use that rate to choose the number of iterations instead of guessing. ``` #### Clarifying Questions for this Part - How close to the exact value must the estimate be, and how often may it miss? - Is there a time limit on the computation? #### What This Part Should Cover - A correct estimation loop built on the earlier parts - Choosing the number of iterations from the variance and the target accuracy - Checking the estimate against the exact value, with an error bar ### Part 4 — Speed up the loop with threads Finally, show how to use multiple threads to make the simulation loop faster. ```hint Share nothing in the hot loop Consider which state the threads would share, such as the random generator and the running total, and what that sharing would cost. ``` #### What This Part Should Cover - Splitting the iterations into chunks and combining the partial results correctly - Separate random state per worker, with independent and reproducible seeds - Whether threads actually run in parallel in your language, and what to use if they do not ### What a Strong Answer Covers - A complete fair-coin construction with its probability argument and expected cost - A precise diagnosis of the sampler bug backed by an exact count, and an exactly uniform fix - An estimate whose number of iterations is justified by its standard error - A parallel design without shared mutable state in the loop, with reproducible seeding and correct aggregation - Clean code that separates the source of randomness from the logic, so each part can be tested ### Follow-up Questions - How would you test that `fair_flip` and `uniform_1_to_n` are actually fair, and how many samples would you need? - The fixed sampler throws away flips whenever it rejects a value. How could it use fewer flips per call on average? - The threaded version gives a slightly different estimate from the single-threaded one with the same seed. Is that a bug? - If the bias were known, could you produce fair flips more efficiently?