= One-sided normal approximation for a rejection proposal budget
{title2=$n\simeq[\{z\sqrt{M-1}+\sqrt{z^2(M-1)+4MN}\}/2]^2$}
For <rejection sampling> with acceptance <probability> $1/M$, $M>1$, the accepted count in $n$ trials has <binomial distribution>, mean $n/M$ and <variance> $n(M-1)/M^2$. To obtain at least $N$ acceptances with approximate <probability> $1-\delta$, use the <standard normal distribution> <quantile> $z=\Phi^{-1}(1-\delta)$. The <central limit theorem> without continuity correction gives $n-MN\geq z\sqrt{n(M-1)}$. Solving this <quadratic inequality> in $\sqrt n$ gives the displayed threshold, rounded upward. It exceeds the average stopping cost $MN$ because it allows for fluctuations in the accepted count. For $M=1$, the count is deterministic and $n=N$ exactly. Exact coverage uses the <binomial distribution> tail rather than the approximation.
Back to article page
