Binomial count and iid values in fixed-budget rejection sampling ($N\sim \mathrm{Bin}(n,1/M)$)

For n independent proposals and an envelope constant $M$, each rejection decision succeeds with probability $1/M$. The accepted count is Bin(n,1/M). Conditional on any acceptance pattern, the accepted values have independent target density f; summing over patterns preserves that product law conditional on the count. The empty-output probability is $(1-1/M{)}^n$.

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\ge 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.

Conditional iid accepted values have the ordinary target-sample CLT at scale $\sqrt{N}$. Since $N/n\to 1/M$, the same estimator has asymptotic variance $M{\mathrm{Var}}_f\varphi$ at scale $\sqrt{n}$. The centered count has limiting variance $(1/M)(1-1/M)$. Any fixed convention on an empty output is asymptotically negligible.