Skip to main content

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 1/n1/n. We develop and verify three samplers:

  1. Binary sampling builds an integer from a fixed number of bits.
  2. Slow Dice Roller rejects out-of-range results and starts over.
  3. 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 m∈Nm\in\mathbb N 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.

Binary sampling without proof annotations
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 k∈Nk\in\mathbb N such that k<2mk<2^m, and let CC be sample_bits(m). We prove Pr⁡(C returns k)=1/2m\Pr(C\text{ returns }k)=1/2^m.

Upper Bound​

The @wp coproc specification checks wp⁡⟦C⟧([result=k])≤1/2m\operatorname{wp}\llbracket C\rrbracket([\mathtt{result}=k])\le1/2^m. The example's helper function pow2(m) represents 2m2^m.

Binary sampler: upper probability bound
Expected: 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 2left2^{\mathtt{left}} equally likely completions of result, yielding the invariant

I(result,left)=[result⋅2left≤k<(result+1)⋅2left]⋅12left.I(\mathtt{result},\mathtt{left})=[\mathtt{result}\cdot2^{\mathtt{left}}\le k<(\mathtt{result}+1)\cdot2^{\mathtt{left}}] \cdot\frac1{2^{\mathtt{left}}}.

For left>0\mathtt{left}>0, the loop body BB selects one of the interval's two halves:

wp⁡⟦B⟧(I)=12⋅I(2⋅result,left−1)+12⋅I(2⋅result+1,left−1)=I(result,left)(the halves partition the interval).\begin{aligned} &\operatorname{wp}\llbracket B\rrbracket(I)\\ ={}&\tfrac12\cdot I(2\cdot\mathtt{result},\mathtt{left}-1)\\ &+\tfrac12\cdot I(2\cdot\mathtt{result}+1,\mathtt{left}-1)\\ ={}&I(\mathtt{result},\mathtt{left}) &&\text{(the halves partition the interval)}. \end{aligned}

The initial and final values are

I(0,m)=12m,I(result,0)=[result=k].I(0,m)=\frac1{2^m}, \qquad I(\mathtt{result},0)=[\mathtt{result}=k].

Park induction therefore gives the specified upper bound.

Lower Bound​

Since BB terminates, wlp⁡⟦B⟧(I)=I\operatorname{wlp}\llbracket B\rrbracket(I)=I for left>0\mathtt{left}>0. Park coinduction gives wlp⁡⟦C⟧([result=k])≥1/2m\operatorname{wlp}\llbracket C\rrbracket([\mathtt{result}=k])\ge1/2^m.

Binary sampler: lower probability bound
Expected: 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 mm to zero, so the loop terminates after exactly mm iterations. The @ast annotation checks wp⁡⟦C⟧(1)=1\operatorname{wp}\llbracket C\rrbracket(1)=1 using left\mathtt{left} as its variant:

Binary sampler: termination
Expected: 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

12m≤wlp⁡⟦C⟧([result=k])=wp⁡⟦C⟧([result=k])≤12m.\frac1{2^m} \le\operatorname{wlp}\llbracket C\rrbracket([\mathtt{result}=k]) =\operatorname{wp}\llbracket C\rrbracket([\mathtt{result}=k]) \le\frac1{2^m}.

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.

Slow Dice Roller without proof annotations
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 k∈Nk\in\mathbb N with k<nk<n, and let CC be the initialized sampler. The preparation loop gives width=2bits≥n\mathtt{width}=2^{\mathtt{bits}}\ge n, so the binary sampler draws each candidate with probability 1/width1/\mathtt{width}. We prove that wp⁡⟦C⟧([result=k])=1/n\operatorname{wp}\llbracket C\rrbracket([\mathtt{result}=k])=1/n.

Upper Bound​

The outer loop has invariant

I={1/n,¬done,[result=k],done.I=\begin{cases} 1/n,&\neg\mathtt{done},\\ [\mathtt{result}=k],&\mathtt{done}. \end{cases}

For its body AA, with done = false, binary sampling gives

wp⁡⟦A⟧(I)=1width+(1−nwidth)⋅1n=1n.\begin{aligned} \operatorname{wp}\llbracket A\rrbracket(I) &=\frac1{\mathtt{width}} +\left(1-\frac n{\mathtt{width}}\right)\cdot\frac1n\\ &=\frac1n. \end{aligned}

Park induction therefore gives wp⁡⟦C⟧([result=k])≤1/n\operatorname{wp}\llbracket C\rrbracket([\mathtt{result}=k])\le1/n.

Slow Dice Roller: upper probability bound
Expected: 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 AA terminates after bits flips, the same invariant gives wlp⁡⟦C⟧([result=k])≥1/n\operatorname{wlp}\llbracket C\rrbracket([\mathtt{result}=k])\ge1/n by Park coinduction.

Slow Dice Roller: matching lower bound
Expected: 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 TT be the total number of coin flips. Caesar checks E[T]≤2⋅n\mathbb E[T]\le2\cdot n by counting each flip with reward 1:

Slow Dice Roller: finite expected number of flips
Expected: Verified
@wp
coproc slow_expected_bits_all_inputs(n: UInt) -> (result: UInt)
pre !?(n >= 1)
pre 2*n
post 0

For n≥2n\ge2, every attempt uses at least one flip, so nontermination implies T=∞T=\infty. The finite expectation gives Pr⁡(C diverges)≤Pr⁡(T=∞)=0\Pr(C\text{ diverges})\le\Pr(T=\infty)=0. For n=1n=1, it returns immediately.

Exact Probability​

Almost-sure termination gives the equality in

1n≤wlp⁡⟦C⟧([result=k])=wp⁡⟦C⟧([result=k])≤1n.\frac1n \le\operatorname{wlp}\llbracket C\rrbracket([\mathtt{result}=k]) =\operatorname{wp}\llbracket C\rrbracket([\mathtt{result}=k]) \le\frac1n.

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 0≤c<v0\le c<v. 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.

Unannotated HeyVL program
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.

Fast Dice Roller with n = 5ReturnedContinues
  1. After flip 2
    1. 0
    2. 1
    3. 2
    4. 3
  2. After flip 3
    1. 0
    2. 1
    3. 2
    4. 3
    5. 4
    6. 5→0
    7. 6→1
    8. 7→2
  3. After flip 4
    1. 0
    2. 1
    3. 2
    4. 3
    5. 4
    6. 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 nn and every k∈{0,…,n−1}k\in\{0,\ldots,n-1\}, we want

Pr⁡(Fast Dice Roller returns k)=1n.\Pr(\text{Fast Dice Roller returns }k)=\frac1n.

For n=1n=1, the program returns zero immediately. For n≥2n\ge2, 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 0,1,20,1,2 form a prefix of length three. For a range of size vv, the prefix of length tt is the part to the left of the cut.

0,…,t−1⏟prefix∣t,…,v−1.\underbrace{0,\ldots,t-1}_{\text{prefix}}\quad\big|\quad t,\ldots,v-1.

Imagine one run from each value to the left of the cut. Add their chances of returning kk. The HeyVL function prefix(n, v, t, k), written F(v,t)F(v,t), is a candidate for that total. For 0≤t≤v<n0\le t\le v<n, the endpoint values are

F(v,0)=0,F(v,v)=vn.F(v,0)=0,\qquad F(v,v)=\frac{v}{n}.

In the figure, the starts 0,1,20,1,2 produce the first six tiles on flip 3. For 0<t<v0<t<v, let w=2⋅vw=2\cdot v be the doubled range size and s=2⋅ts=2\cdot t the number of updated values from the prefix. Then 2⋅F(v,t)2\cdot F(v,t) equals

{F(w,s),w<n,[k<s],s<n≤w,1+F(w−n,s−n),n≤s.\begin{cases} F(w,s), & w<n,\\ [k<s], & s<n\le w,\\ 1+F(w-n,s-n), & n\le s. \end{cases}

The two outcomes from each of the first tt starting values cover 0,…,s−10,\ldots,s-1, with weight 1/21/2 per branch. When w<nw<n, all these values continue. When w≥nw\ge n, values below nn return, and the rest form a new prefix after subtracting nn.

The recurrence also holds at both endpoints. At t=0t=0, there are no contributions. At t=vt=v, the first case gives w/nw/n, and the case with returns gives 1+(w−n)/n=w/n1+(w-n)/n=w/n. Both equal 2⋅F(v,v)2\cdot F(v,v).

Each recursive call doubles the positive gap v−tv-t while keeping the range size below nn. Caesar checks that the natural-number rank n−(v−t)n-(v-t) decreases, so the definition is well-founded.

The Loop Invariant​

To reason about one running state with 0≤c<v<n0\le c<v<n, take the difference of the two prefix sums that differ by the starting value cc.

D(v,c)=F(v,c+1)−F(v,c).D(v,c)=F(v,c+1)-F(v,c).

Write w=2⋅vw=2\cdot v for the doubled range size and dd for the accumulator after appending the bit. For 0≤d<w0\le d<w, define the value contributed by that branch as

Sw(d)={D(w,d),w<n,[d=k],d<n≤w,D(w−n,d−n),n≤d.S_w(d)= \begin{cases} D(w,d), & w<n,\\ [d=k], & d<n\le w,\\ D(w-n,d-n), & n\le d. \end{cases}

A continuing prefix occupies the first ss values of its new range, of size uu. Summing D(u,j)D(u,j) over those values cancels all intermediate terms and leaves F(u,s)−F(u,0)=F(u,s)F(u,s)-F(u,0)=F(u,s). Combining that sum with any return indicators gives the recurrence in the following form for 0≤t≤v0\le t\le v.

2⋅F(v,t)=∑d=02⋅t−1Sw(d).2\cdot F(v,t)=\sum_{d=0}^{2\cdot t-1}S_w(d).

Subtract the equation at t=ct=c from the one at t=c+1t=c+1. The only terms left are Sw(2⋅c)S_w(2\cdot c) for bit zero and Sw(2⋅c+1)S_w(2\cdot c+1) for bit one, so

D(v,c)=Sw(2⋅c)+Sw(2⋅c+1)2.D(v,c)=\frac{S_w(2\cdot c)+S_w(2\cdot c+1)}{2}.

The actual invariant applies the same shift and scale to the running value and to the return indicator.

Running(1+F(v,c+1))−F(v,c)2,At exitQ=1+[result=k]2.\begin{aligned} \text{Running}\quad &\frac{(1+F(v,c+1))-F(v,c)}{2},\\ \text{At exit}\quad &Q=\frac{1+[\mathtt{result}=k]}{2}. \end{aligned}

The transformation x↦(1+x)/2x\mapsto(1+x)/2 preserves the average of the two branches, so the invariant before an iteration equals its expected value after the iteration. Since FF takes values in [0,1][0,1], adding one makes 1+F(v,c+1)1+F(v,c+1) at least F(v,c)F(v,c), so HeyVL's unsigned subtraction leaves the numerator intact. Dividing by two puts the invariant in [0,1][0,1], as required for the lower bound under wlp.

Upper bound and loop invariant
Expected: 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 QQ. 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 t=0t=0 and t=vt=v. The loop calls them at t=ct=c and t=c+1t=c+1 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 n=5n=5, k=0k=0, and v=4v=4, the first two starting values yield 0,…,30,\ldots,3 on flip 3. The branch that produces zero contributes 1/21/2 to F(4,2)F(4,2). From the additional start c=2c=2, bit zero returns 44 and bit one recycles 55 to width 33 and accumulator 00. The recycled state has D(3,0)=F(3,1)−F(3,0)=1/2D(3,0)=F(3,1)-F(3,0)=1/2, since its next bit returns zero or one.

F(4,2)=12,F(4,3)=1+1/22=34,D(4,2)=34−12=0+1/22=14.\begin{aligned} F(4,2)&=\frac12,\\ F(4,3)&=\frac{1+1/2}{2}=\frac34,\\ D(4,2)&=\frac34-\frac12\\ &=\frac{0+1/2}{2}=\frac14. \end{aligned}

Almost-Sure Termination​

At each continuing loop head, 0≤c<v<n0\le c<v<n. Appending a bit bb changes the positive difference v−cv-c to 2⋅(v−c)−b2\cdot(v-c)-b, and recycling leaves that difference unchanged. A zero bit either ends the loop or doubles v−cv-c.

The @ast annotation uses the variant n−(v−c)n-(v-c), taken to be zero on exit. It checks that the variant never increases and decreases by at least one with probability at least 1/21/2 [McIver et al. 2018].

Almost-sure termination
Expected: 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 n≥2n\ge2, the initial difference is D(1,0)=F(1,1)−F(1,0)=1/nD(1,0)=F(1,1)-F(1,0)=1/n. 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 (1+1/n)/2(1+1/n)/2. For the initialized sampler CC, this gives

1+1/n2≤wlp⁡⟦C⟧(Q)=wp⁡⟦C⟧(Q)(almost-sure termination)≤1+1/n2.\begin{aligned} \frac{1+1/n}{2} &\le \operatorname{wlp}\llbracket C\rrbracket(Q)\\ &= \operatorname{wp}\llbracket C\rrbracket(Q) &&\text{(almost-sure termination)}\\ &\le \frac{1+1/n}{2}. \end{aligned}

The expected value of QQ is (1+Pr⁡(C returns k))/2(1+\Pr(C\text{ returns }k))/2, since QQ gives 11 on a match and 1/21/2 on every other return. It follows that Pr⁡(C returns k)=1/n\Pr(C\text{ returns }k)=1/n.

See Also​

  • Reservoir Sampling proves uniform selection from a stream using a state-dependent replacement probability.
  • Assertions can discard unwanted samples through conditioning.

References​