Simulation: making randomness you want out of randomness you have

PROB · Chapter 613 min readAsked at Jane Street, Optiver, SIG, Two Sigma

Assumes Recursive expected value and the re-roll family.

After this lesson you should be able to

  • Turn a uniform into any distribution by inverting its CDF.
  • Build a fair coin from a biased one, and a d7 from a d6.
  • State the Monte Carlo error rate and name two ways to reduce it.

Two related families of question show up. One asks you to manufacture one kind of randomness from another — a fair coin from a biased one, a seven-sided die from a six-sided one — and is really about symmetry and expected waiting times. The other asks how accurate a simulation is, and is really about 1/n1/\sqrt{n}.

Equation 6.1

The inverse transform

Feed a uniform through the inverse CDF and you get the distribution you wanted. This is the general answer to "how would you sample from this?", and it is why a uniform generator is all a library needs.

U∼Unif(0,1) ⇒ F−1(U)∼FU \sim \text{Unif}(0,1) \ \Rightarrow \ F^{-1}(U) \sim F
F−1F^{-1}
The quantile function. For a discrete law it is a lookup down the cumulative table.
−1λln⁡U-\tfrac{1}{\lambda}\ln U
The exponential case, which is worth knowing by heart.
MethodNeedsFails when
Inverse transformA computable F−1F^{-1}The CDF has no closed-form inverse — the normal, for instance
Rejection samplingA proposal density that dominates the targetThe acceptance rate is low, which wastes draws
Box–MullerTwo uniformsNothing much — it is the standard normal recipe
Table 6.2 · Three ways to sample. Box–Muller turns two uniforms into two independent standard normals via −2ln⁡U1cos⁡(2πU2)\sqrt{-2\ln U_1}\cos(2\pi U_2) and the matching sine. It exists precisely because the normal CDF has no elementary inverse.

Derivation 6.3

A fair coin from a biased one

Von Neumann’s trick. The bias is unknown and need not be measured.

  1. Flip twice. HT→heads, TH→tails, HH or TT→discard\text{Flip twice. HT} \to \text{heads}, \ \text{TH} \to \text{tails}, \ \text{HH or TT} \to \text{discard}

    Pair the flips and read only the mixed outcomes.

  2. P(HT)=p(1−p)=P(TH)P(\text{HT}) = p(1-p) = P(\text{TH})

    The two mixed outcomes are equally likely whatever pp is — that symmetry is the whole idea.

  3. E[flips]=22p(1−p)=1p(1−p)\mathbb{E}[\text{flips}] = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}
a fair bit, at an expected cost of 1/(p(1−p)) flips\text{a fair bit, at an expected cost of } 1/\big(p(1-p)\big) \text{ flips}
Flip a biased coin twiceHeads70%Heads — discard70%49%Tails — call it heads30%21%Tails30%Heads — call it tails70%21%Tails — discard30%9%
Figure 6.4 · Why the trick works without knowing the bias. Drawn at p=0.7p = 0.7, but the argument never uses the number. The two highlighted paths both have probability p(1−p)p(1-p), whatever pp is, because multiplication commutes — so conditioning on "the pair disagreed" gives a fair bit from a coin you never had to measure.

Symmetry is the tool, not arithmetic. Notice that nothing in the von Neumann argument requires knowing pp. That is the point: you are not correcting for the bias, you are finding two outcomes that the bias treats identically and ignoring everything else. The same instinct solves the d7-from-a-d6 problem — roll twice for 36 equally likely outcomes, use 35 of them in seven groups of five, and re-roll on the thirty-sixth — and it is why "find the symmetry, discard the rest" is the first thing to try on any construction question.

The rest of this lesson is in Premium

You have read the opening. 14 more sections follow, including 6 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Arithmetic that survives a clock in full, free.