= Solution
\b[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 truncation bias in rejection sampling>[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.
Back to article page
