Fast Dice Roller
Given a positive natural number n, we want to use fair coin flips to return each integer from 0 through n - 1 with probability .
We develop and verify three samplers:
- Binary sampling builds an integer from a fixed number of bits.
- Slow Dice Roller rejects out-of-range results and starts over.
- Fast Dice Roller reuses the randomness in rejected results [Lumbroso 2013, §1].
Sampling from a Power-of-Two Range
Program
Three fair coin flips give eight equally likely bit strings, 000 through 111, representing the integers zero through seven.
Let be the number of coin flips.
Starting from result = 0, each flip doubles result and adds the new bit.
The counter left records the remaining flips.
proc sample_bits(m: UInt) -> (result: UInt)
{
result = 0
var left: UInt = m
while left > 0 {
var bit: Bool = flip(1/2)
result = 2 * result + ite(bit, 1, 0)
left = left - 1
}
}
Verification
Fix such that , and let be sample_bits(m).
We prove .
Upper Bound
The @wp coproc specification checks .
The example's helper function pow2(m) represents .
Verified@wp
coproc uniform_bits_upper(m: UInt, k: UInt) -> (result: UInt)
pre !?(k < pow2(m))
pre 1 / pow2(m)
post [result == k]
{
result = 0
var left: UInt = m
@invariant(
[result * pow2(left) <= k && k < (result + 1) * pow2(left)]
* (1 / pow2(left))
)
The remaining left bits give equally likely completions of result, yielding the invariant
For , the loop body selects one of the interval's two halves:
The initial and final values are
Park induction therefore gives the specified upper bound.
Lower Bound
Since terminates, for . Park coinduction gives .
Verified@wlp
proc uniform_bits_lower(m: UInt, k: UInt) -> (result: UInt)
pre ?(k < pow2(m))
pre 1 / pow2(m)
post [result == k]
Termination
The counter left decreases from to zero, so the loop terminates after exactly iterations.
The @ast annotation checks using as its variant:
Verified@wp
proc uniform_bits_terminates(m: UInt) -> (result: UInt)
pre 1
post 1
{
result = 0
var left: UInt = m
@ast(true, left, variant_value, 1, 1)
Exact Probability
Termination gives the equality in
Slow Dice Roller
Program
To sample from zero through five, draw a three-bit number and accept it if it is below six.
On six or seven, discard the attempt and start over.
This rejection sampling extends the binary sampler to any positive range size n.
The program first computes width, the smallest power of two at least n, and bits, the number of flips needed to sample that range.
Each attempt resets result to zero, samples bits fair bits, and accepts if result < n.
proc slow_dice_roller(n: UInt) -> (result: UInt)
{
var width: UInt = 1
var bits: UInt = 0
while width < n {
width = 2 * width
bits = bits + 1
}
result = 0
var done: Bool = false
while !done {
result = 0
var left: UInt = bits
while left > 0 {
var bit: Bool = flip(1/2)
result = 2 * result + ite(bit, 1, 0)
left = left - 1
}
if result < n {
done = true
} else {}
}
}
Verification
Fix with , and let be the initialized sampler. The preparation loop gives , so the binary sampler draws each candidate with probability . We prove that .
Upper Bound
The outer loop has invariant
For its body , with done = false, binary sampling gives
Park induction therefore gives .
Verified@wp
coproc slow_probability_upper(n: UInt, k: UInt) -> (result: UInt)
pre !?(n >= 1 && k < n)
pre 1/n
post [result == k]
{
var width: UInt = 1
var bits: UInt = 0
@invariant(
!?(n >= 1 && k < n && width == pow2(bits) && width >= bits + 1 && bits <= n)
⊔ (1/n)
)
while width < n {
width = 2 * width
bits = bits + 1
}
result = 0
var done: Bool = false
@invariant(
!?(n >= 1 && k < n && width >= n && width == pow2(bits))
⊔ ite(done, [result == k], 1/n)
)
Lower Bound
Since terminates after bits flips, the same invariant gives by Park coinduction.
Verified@wlp
proc slow_probability_lower(n: UInt, k: UInt) -> (result: UInt)
pre ?(n >= 1 && k < n)
pre 1/n
post [result == k]
Termination
Preparation terminates because width starts at one and doubles until it reaches n.
Let be the total number of coin flips.
Caesar checks by counting each flip with reward 1:
Verified@wp
coproc slow_expected_bits_all_inputs(n: UInt) -> (result: UInt)
pre !?(n >= 1)
pre 2*n
post 0
For , every attempt uses at least one flip, so nontermination implies . The finite expectation gives . For , it returns immediately.
Exact Probability
Almost-sure termination gives the equality in
Fast Dice Roller
Program
Suppose we want one of five outcomes, 0 through 4.
Three fair flips produce the eight candidates 0 through 7 with equal probability.
Slow Dice Roller accepts 0 through 4 and starts over on 5, 6, or 7.
Fast Dice Roller subtracts 5 from a rejected value, leaving one of 0, 1, or 2.
Conditional on rejection, those three values are equally likely, so the sampler can keep the value it already has and build on that smaller range [Lumbroso 2013, §1].
One fresh bit doubles the range from three values to six, enough to try accepting again.
In the program, v is the size of the current range and c is the value held by this run, with .
Each flip doubles v and changes c to twice its old value plus the new bit.
When the doubled range has at least n values, the sampler returns if c < n and otherwise subtracts n from both v and c.
For n = 1, it returns zero without flipping a coin.
proc fdr(n: UInt) -> (result: UInt)
{
var v: UInt = 1
var c: UInt = 0
var done: Bool = n == 1
result = 0
while !done {
v = 2 * v
var bit: Bool = flip(1/2)
c = 2 * c + ite(bit, 1, 0)
if v >= n {
if c < n {
result = c
done = true
} else {
v = v - n
c = c - n
}
} else {}
}
}
Each strip shows one value for every equally likely bit sequence that reaches that flip.
On a recycled tile, the value after the arrow is the starting value of c for the next flip.
n = 5ReturnedContinues- After flip 2
- 0
- 1
- 2
- 3
- After flip 3
- 0
- 1
- 2
- 3
- 4
- 5→0
- 6→1
- 7→2
- After flip 4
- 0
- 1
- 2
- 3
- 4
- 5→0
If the sampler returns on flip 3, each of the five outputs is equally likely because each has one green tile on that strip. The same holds if it returns on flip 4.
Verification
For every positive and every , we want
For , the program returns zero immediately. For , Caesar checks an upper bound, a lower bound, and almost-sure termination. The two bounds use the same loop invariant and imply equality once termination is established.
Prefix Sums
In the figure's “After flip 2” row, the first three tiles form a prefix of length three. For a range of size , the prefix of length is the part to the left of the cut.
Imagine one run from each value to the left of the cut.
Add their chances of returning .
The HeyVL function prefix(n, v, t, k), written , is a candidate for that total.
For , the endpoint values are
In the figure, the starts produce the first six tiles on flip 3. For , let be the doubled range size and the number of updated values from the prefix. Then equals
The two outcomes from each of the first starting values cover , with weight per branch. When , all these values continue. When , values below return, and the rest form a new prefix after subtracting .
The recurrence also holds at both endpoints. At , there are no contributions. At , the first case gives , and the case with returns gives . Both equal .
Each recursive call doubles the positive gap while keeping the range size below . Caesar checks that the natural-number rank decreases, so the definition is well-founded.
The Loop Invariant
To reason about one running state with , take the difference of the two prefix sums that differ by the starting value .
Write for the doubled range size and for the accumulator after appending the bit. For , define the value contributed by that branch as
A continuing prefix occupies the first values of its new range, of size . Summing over those values cancels all intermediate terms and leaves . Combining that sum with any return indicators gives the recurrence in the following form for .
Subtract the equation at from the one at . The only terms left are for bit zero and for bit one, so
The actual invariant applies the same shift and scale to the running value and to the return indicator.
The transformation preserves the average of the two branches, so the invariant before an iteration equals its expected value after the iteration.
Since takes values in , adding one makes at least , so HeyVL's unsigned subtraction leaves the numerator intact.
Dividing by two puts the invariant in , as required for the lower bound under wlp.
Verified@wp
coproc fdr_probability_upper(n: UInt, k: UInt) -> (result: UInt)
pre !?(n >= 1 && k < n)
pre (1 + 1/n)/2
post (1 + [result == k]) * (1/2)
{
var v: UInt = 1
var c: UInt = 0
var done: Bool = n == 1
result = 0
@invariant(
!?(n >= 1 && k < n && v >= 1 && c < v && (done || v < n))
⊔ ite(done, (1 + [result == k]) * (1/2),
((1 + prefix(n, v, c+1, k)) - prefix(n, v, c, k))/2)
)
In the annotation, the Boolean condition describes the valid states, and ite(done, ...) selects the exit or running expression above.
The @wp coproc checks the upper bound on the expectation of .
The @wlp proc in the full source checks the matching lower bound with the same invariant value on valid states.
The recurrence helpers in the full source are checked separately, including at and . The loop calls them at and to supply exactly the two equations used in the subtraction. Their specifications pass the invariant value through each call, and their empty bodies leave the sampler state unchanged.
Five-outcome example
For , , and , the first two starting values yield on flip 3. The branch that produces zero contributes to . From the additional start , bit zero returns and bit one recycles to width and accumulator . The recycled state has , since its next bit returns zero or one.
Almost-Sure Termination
At each continuing loop head, . Appending a bit changes the positive difference to , and recycling leaves that difference unchanged. A zero bit either ends the loop or doubles .
The @ast annotation uses the variant , taken to be zero on exit.
It checks that the variant never increases and decreases by at least one with probability at least [McIver et al. 2018].
Verified@wp
proc fdr_terminates(n: UInt) -> (result: UInt)
pre ?(n >= 1)
pre 1
post 1
{
var v: UInt = 1
var c: UInt = 0
var done: Bool = n == 1
result = 0
@ast(
done || (c < v && v < n),
n - (v - c),
_,
1/2,
1
)
Exact Probability from the Caesar Bounds
For , the initial difference is .
Under wp, divergence contributes zero to the expectation, and under wlp it contributes one.
Almost-sure termination makes that contribution zero under both calculi, so the upper and lower bounds meet at .
For the initialized sampler , this gives
The expected value of is , since gives on a match and on every other return. It follows that .
See Also
- Reservoir Sampling proves uniform selection from a stream using a state-dependent replacement probability.
- Assertions can discard unwanted samples through conditioning.
References
-
Lumbroso (2013). Optimal Discrete Uniform Generation from Coin Flips, and Applications.The original algorithm and its correctness proof. (Section 1)
-
McIver et al. (2018). A New Proof Rule for Almost-Sure Termination. POPL.The almost-sure termination rule used by the fast sampler.