= Solution
A trial of Amy's <rejection sampling> uses exactly $2n$ fair <Bernoulli trials>. Exactly $\binom{2n}{n}$ of the $2^{2n}$ equally likely <binary sequences> have $n$ heads, so the acceptance <probability> is
$$
p_n=\frac{\binom{2n}{n}}{2^{2n}}.
$$
Independent retries make the number $T$ of trials a <geometric random variable> on $\{1,2,\ldots\}$ with <expectation> $1/p_n$. The total number $C$ of coin tosses is $2nT$, so
$$
\boxed{\mathbb EC=\frac{2n\,2^{2n}}{\binom{2n}{n}}.}
$$
Using <Stirling's approximation>, the <central binomial coefficient> satisfies
$$
\binom{2n}{n}
\sim\frac{\sqrt{4\pi n}(2n/e)^{2n}}{2\pi n(n/e)^{2n}}
=\frac{4^n}{\sqrt{\pi n}}.
$$
Consequently
$$
\boxed{\mathbb EC\sim2\sqrt\pi\,n^{3/2}.}
$$
The <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\geq1$.
Back to article page
