Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 3 / a

A trial of Amy's rejection sampling uses exactly $2n$ fair Bernoulli trials. Exactly $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ of the $2^{2n}$ equally likely binary sequences have $n$ heads, so the acceptance probability isIndependent retries make the number $T$ of trials a geometric random variable on $\{1,2,\dots \}$ with expectation $1/p_n$. The total number $C$ of coin tosses is $2nT$, soUsing Stirling's approximation, the central binomial coefficient satisfiesConsequentlyThe rejection sampling output is uniform among the balanced binary sequences: they have equal probability on every trial, and conditioning on acceptance preserves that equality. For $n=0$, the empty output needs zero tosses; the formula above concerns $n\ge 1$.