= Solution
Apply independent uniforms to the $n$ proposals, and let $I_i$ indicate acceptance. Each $I_i$ is Bernoulli with success probability $p=1/M$, and the indicators are independent because the pairs $(X_i,U_i)$ are independent. Hence
$$
\boxed{N=\sum_{i=1}^nI_i\sim\operatorname{Bin}(n,1/M),\qquad
\mathbb EN=\frac nM,\qquad\operatorname{Var}(N)=\frac nM\left(1-\frac1M\right).}
$$
For a fixed acceptance pattern, the values at accepted positions are independent with density $f$, by the single-trial conditional density calculation. The same product law holds for every pattern of a given size. Consequently, conditional on $N=m$, the ordered accepted observations have joint density $\prod_{j=1}^mf(y_j)$. This is the <binomial count and iid values in fixed-budget rejection sampling>; the count provides no information about those target values.
There is a finite-sample empty-output event, with probability $(1-1/M)^n$. Any estimator dividing by $N$ must be defined separately on $N=0$.
Back to article page
