Katkat
Back

Transform Biased and Uniform Random Bits Exactly

LinkedInMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenStatistics & Math

Last updated

Tests the ability to design and mathematically prove exact random variate generators between biased and uniform bit sources, analyzing termination and expected sample complexity.

Scenario

In online experimentation and bandit routing systems, randomization services often rely on specialized hardware entropy sources or fixed-ratio coin flips. You are tasked with designing two fundamental sampling primitives that convert between biased and fair independent bit streams without introducing numerical approximation error.

Assume all source bit draws are independent and identically distributed (i.i.d.).

Part 1: Fair Bit from an Unknown Biased Source

You are provided with a function flip_biased() that returns 1 with an unknown probability p and 0 with probability 1 - p, where 0 < p < 1. The value of p is strictly stationary across flips.

  1. Specify an algorithm generate_fair_bit() that returns 0 or 1 with exact probability 0.5.
  2. Prove mathematically why the output bit is unbiased, regardless of the value of p.
  3. Compute the expected number of calls to flip_biased() required to produce a single fair bit in terms of p. At what value of p is the expected number of calls minimized, and what is that minimum?

Part 2: Arbitrary Biased Bit from Fair Bits

You are provided with a standard unbiased generator flip_fair() that outputs 0 or 1 with probability 0.5 each. You need to implement generate_biased_bit(target_p) which outputs 1 with exact probability target_p and 0 with probability 1 - target_p, where target_p is in the open interval (0, 1).

  1. Describe an algorithm that simulates target_p exactly using sequential fair coin flips. (Hint: consider the binary expansion of target_p).
  2. Prove that the probability of returning 1 matches target_p exactly.
  3. Derive the expected number of fair coin flips required to terminate when target_p = 1/3, and determine the worst-case expected number of flips across all possible values of target_p in (0, 1).

Assumptions and Requirements

  • The source bits are strictly i.i.d.
  • Your algorithms must terminate with probability 1 (almost sure termination).
  • No external pseudo-random number generator is allowed; only the specified bit generator may be invoked.

Hints

Hint 1

For Part 1, consider pairing consecutive independent flips and examining the probabilities of the asymmetric outcomes (0, 1) versus (1, 0).

Hint 2

For Part 2, express target_p as a binary decimal 0.b1 b2 b3... and compare it bit-by-bit against a sequence of fair coin tosses.

Hint 3

Notice that the comparison between a random binary fraction and target_p can terminate the moment the first differing bit is observed.

Follow-up questions

  • How can you optimize Part 1 (von Neumann extractor) to achieve entropy efficiency closer to Shannon's source coding theorem?
  • If target_p is an irrational number like 1/pi, how does the algorithm in Part 2 behave in terms of memory and termination?
  • If the biased source in Part 1 has a slow drift over time (non-stationary p), how does that affect the fairness of the output, and how would you detect it?