Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / S (Simulation)

Let $Z_p={\sum }_x\tilde{p}(x)$ and $Z_q={\sum }_x\tilde{q}(x)$, both finite and positive as required for normalization. A sufficient envelope condition is $\boxed{M\ge \underset{x\in \Omega }{\sup }\tilde{p}(x)/\tilde{q}(x)}$ with finite $M>0$. Use independent proposals and independent uniforms on each trial. This guarantees an acceptance probability in $[0,1]$ for every state. Choose the smallest certified upper bound on that ratio, since increasing $M$ decreases the overall acceptance rate. The ratio must be bounded for this particular proposal to admit such an envelope.

For one proposal, $P(Y=x,\text{accept})=q(x)\tilde{p}(x)/(M\tilde{q}(x))=\tilde{p}(x)/(M{Z}_q)$. Summing gives total acceptance probability $a=Z_p/(M{Z}_q)>0$. Conditioning on acceptance therefore gives $P(Y=x\mid \text{accept})=\tilde{p}(x)/Z_p=p(x)$.

The first accepted result has this law too: the probability of $k-1$ failures followed by acceptance at $x$ is $(1-a{)}^{k-1}\tilde{p}(x)/(M{Z}_q)$. Sum the geometric series over $k\ge 1$ to obtain $\boxed{P(X=x)=p(x)}$. Positive acceptance probability also proves almost-sure termination.

Each $N_i$ is geometric on $\{1,2,\dots \}$ with success probability $a=Z_p/(M{Z}_q)$. HenceLinearity of expectation proves the estimator is unbiased. Moreover the joint probability factors:Thus $\boxed{N_i\text{ and }{X}_i\text{ are independent}}$, not merely uncorrelated. Fresh independent trials make the simulated cycles independent as well.

A fixed proposal-count budget does not bias the accepted values. For each trial, acceptance has probability $a$, and conditional on acceptance its label has law $p$ independently of the other trials. Conditional on the full accept/reject pattern among the first $N^{\ast }$ proposals, the successful labels are independent with common law $p$. Therefore $K\sim \mathrm{Binomial}(N^{\ast },a)$, and conditional on $K=k$, the $k$ retained samples are independent draws from $p$. When $K=0$ there is simply no sample. This concerns a budget fixed independently of the proposal values; it does not assert that an empirical average is defined on an empty output.

State-dependent execution times can bias the finite set of completed outputs. A simple counterexample takes $p=q$ uniform on two states and $M=1$, so every proposal is accepted. Suppose processing the first state takes one unit of time and processing the second takes two. Stop at a deadline between one and two units, discarding any unfinished computation. The only possible completed output is the first state; conditional on obtaining a sample, its law is concentrated there rather than uniform.

This demonstrates that a wall-clock cutoff can select outputs according to their processing cost, unlike the fixed proposal budget in (d). It does not imply a permanent asymptotic bias of averages over an indefinitely growing completed sequence: the finite-horizon stopping and censoring are the issue. Without assumptions relating runtime to states, exact finite-sample unbiasedness cannot be guaranteed.