免费智力题简单

A Fair Coin from a Biased One

考察公司Jane StreetOptiver

You are handed a coin that lands heads with some unknown probability $p$ , where $0 < p < 1$ . You may flip it as many times as you like.

Describe a procedure that produces a perfectly fair binary outcome — one that is heads with probability exactly $1/2$ — without knowing $p$ . Then compute the expected number of flips your procedure uses.

解析

Solution

The procedure. Flip the coin twice and look at the ordered pair:

HT → output heads
TH → output tails
HH or TT → discard and repeat

Why it is fair. The two flips are independent, so

P(HT) = p(1-p) \qquad\text{and}\qquad P(TH) = (1-p)p.

These are equal for every $p$ . Conditioning on the event that we stopped — that is, on $\{HT, TH\}$ — gives

P(\text{output heads} \mid \text{stop}) = \frac{p(1-p)}{p(1-p) + (1-p)p} = \frac{1}{2}.

The bias cancels because it appears identically in both surviving outcomes. This is von Neumann's trick.

Expected number of flips. Each round costs 2 flips and succeeds with probability

q = 2p(1-p).

The number of rounds is geometric with mean $1/q$ , so

E[\text{flips}] = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}.

Sanity check. At $p = 1/2$ this gives 4 flips — we waste half of our rounds on HH/TT. As $p \to 0$ or $p \to 1$ the cost blows up, which is right: a nearly deterministic coin rarely produces a mixed pair.

> What the interviewer is listening for. State the procedure, then prove fairness by showing the $p$ cancels — candidates who assert symmetry without writing the conditional probability usually get pushed. Expect a follow-up on how to avoid discarding flips (Peres's iterated extractor gets you close to the entropy bound $H(p)$ ).

题目

解析

Solution