
Suppose you want a sampler to return one of two answers, 00 or 11. You could ask the original question and discard every other answer. Or you could change the formula so that only those two answers survive when you read off its first two bits. In this example, the first procedure gives 00 five chances in six. The second gives it one in two. Where did the extra weight go?
Filter the original draws
Start with the Boolean formula (x ∨ ¬x) ∧ (y ∨ ¬y). It accepts all four two-bit strings. The target gives each string probability 1/4. Define a sampler that, on this input, gives 00 probability 5/8 and gives each of 01, 10 and 11 probability 1/8. These probabilities are part of the example.
Keep only draws of 00 or 11. Together they carry 6/8 of the original probability. Five of those six eighths belong to 00, so its share among the retained draws is (5/8)/(6/8) = 5/6. Filtering preserves the original five-to-one odds between the two answers.
Sample the modified formula
Keep the two original clauses. Append (¬x ∨ y) ∧ (x ∨ ¬y) to require the first two bits to agree, then append the single clause (a₁ ∨ a₂ ∨ … ∨ a₁₂) to require at least one of twelve auxiliary bits to be 1. Each way of filling in the auxiliary bits is called an extension of the original answer. Of the 4,096 possible twelve-bit strings, only the all-zero string fails. That leaves 4,095 extensions for 00 and another 4,095 for 11.
Here the sampler’s dependence on its input matters. Define the same sampler to draw uniformly from the 8,190 full solutions when it receives the formula written above. A different encoding can admit exactly the same solutions and still be a different input to this sampler. Read off the first two bits and ignore the twelve auxiliary bits. Exactly 4,095 of the 8,190 solutions begin with 00, giving it probability 1/2. The gap from 5/6 is 1/3.
The equal counts explain the half share once we specify a uniform draw. The five-to-one odds came from a different fact about the sampler, its behaviour on the original input. To carry those odds through a change of formula requires a condition relating the sampler’s behaviour on the two inputs.
Where the sampling theorems draw the line
In their 2020 paper on Barbarik2, Kuldeep S. Meel, Yash Pote and Sourav Chakraborty define subquery consistency for a particular procedure, called a kernel, that constructs modified formulas. Their Theorem 1 gives an acceptance guarantee for a sufficiently close sampler. The rejection guarantee for a sufficiently far sampler also requires subquery consistency for the paper’s kernel. The original sampler here already fails the close condition at ε = 1/20. Its ℓ₁ distance from the target is 3/4, above the threshold of η = 7/10 chosen for this example. The toy uses a simpler formula, and leaves the sampler’s behaviour on the paper’s actual kernel outputs unspecified. Its calculation therefore gives no verdict on what Barbarik2 would return. Definition 9 and Theorem 1, NeurIPS 2020
The 2022 Barbarik3 result uses total variation distance and assumes specific ways to query the target distribution and the sampler. Total variation is half the ℓ₁ distance here, so the same original distribution is only 3/8 from the target. It falls below the same numerical threshold of 7/10 under that definition. Section 2 and Theorem 1, NeurIPS 2022
For someone checking a sampler, the distinction is practical. Counting completions answers a question about the formula. To use a modified query as a substitute for filtering the original draws, you also need a reason to expect the odds between the retained answers to survive the change.
Evidence and AI assistance
Richard George Davis’s Ledger example (v0.1.0, 19 November 2026) specifies one formula, one pair and two sampling laws. It illustrates a known assumption. All probabilities follow from those stipulations, with no measurements of a running sampler. Worked example · Source map
AI assisted with the Ledger construction, source mapping and drafting. A separate AI reviewer checked its arithmetic and interpretation of the cited results. OpenAI GPT models accessed through Codex also assisted with drafting and source checks for this article. The record contains no human specialist or peer review.



Loading published comments…