 Deadline truncation bias in rejection sampling

Stopping after a fixed number of rejection sampling proposals preserves the target law of accepted labels, conditional on the number accepted. Stopping instead after a fixed amount of elapsed computing time can change the finite-sample law if processing costs depend on the proposed state. The deadline may censor precisely the expensive states.

For an exact counterexample, let both target and proposal be uniform on two states, so every proposal is accepted. Let processing cost be one time unit for the first state and two for the second. Stop between one and two units and retain only finished proposals. Conditional on obtaining an output, the first state is the only possible value, despite its target probability being one half. This proves that a runtime cutoff need not be an unbiased stopping rule for the realized finite output. It does not imply asymptotic bias of the indefinitely growing completed sequence; it identifies a finite-horizon censoring effect.