The Price of Early Stopping in Exact Sampling

Some exact samplers can return a sample before reading any unknown input coordinate. We ask what it costs, in expected queries, to make such no-query returns as likely as possible. Inputs have n unit-cost coordinates, and samplers must be exact at every feasible input. At a fixed target input we compare the least expected cost OPT with the least cost OPT0 among samplers that also attain the maximal no-query probability. Over n-coordinate families, the worst ratio OPT0/OPT lies between floor((n+1)^2/4)/n and (n+1)^2/(4n). The bounds coincide for odd n, so the worst price grows as n/4. The upper bound rearranges terminal query sets cyclically while preserving every conditional output constraint; two-output families with continuous probabilities bounded away from zero attain the lower bound. For categorical distributions with weights in independent positive intervals the price is at most two, and a three-weight family shows that it can exceed one. When a single sampler is evaluated under a uniform prior, a separate construction has a price linear in n, although an exact sampler using at most two queries exists. Only coordinate revelations are charged.