Skip to main content

Geometric Loop

The geometric loop makes independent flips of a fair coin until the first heads. It can make arbitrarily many flips, yet the expected number is finite [Kaminski et al. 2016]. How many tails occur on average before the first heads?

The Program​

Unannotated HeyVL program
proc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool) {
count = init_count
running = init_running
while running {
var stop: Bool = flip(0.5)
if stop {
running = false
} else {
count = count + 1
}
}
}

Each flip showing tails increments count, while heads sets running to false. If init_running is false, the loop performs no flips and returns init_count unchanged. An active loop terminates with probability one.

Geometric loop starting with count zero and running trueAn incoming arrow marks count zero with running true. Each fair coin flip either advances along the upper row and increments count on tails, or moves to the stopped state at the same count on heads. The chain continues to arbitrarily large counts.012012½½½½½½countrunningstopped……

Starting with count = 0 and running = true, the expected counter is one, as the verification below establishes. The expected number of all flips is two, since it also includes the final heads. One tick 1 per flip would measure that second quantity.

Exactly kk tails followed by heads has probability 2−(k+1)2^{-(k+1)}. Every additional flip showing tails halves the probability of that outcome.

Verification​

Caesar first bounds the expected counter from above using Park induction, then verifies a simpler candidate with two-step induction. The later variants prove a matching lower bound and refute an incorrect upper bound. Each specification uses @wp to select least fixed point semantics, where nontermination contributes zero.

Park Induction​

For Park induction, the @invariant annotation bounds the expected final counter by count + [running]. The term [running] bounds the expected number of tails still to come.

Upper-bound specification and Park induction
Expected: Verified
@wp
coproc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
pre init_count + [init_running]
post count
{
count = init_count
running = init_running
// An active loop adds at most one flip showing tails in expectation.
@invariant(count + [running])
while running {

From an active state with count = c, heads gives invariant value cc and tails gives c+2c+2. Their average is 12⋅c+12⋅(c+2)=c+1\tfrac12\cdot c+\tfrac12\cdot(c+2)=c+1, the invariant's value before the iteration. At exit, the invariant equals the postexpectation count.

Two-Step Induction​

The simpler candidate count + 1 does not check whether the loop is still running.

Upper-bound specification and @k_induction annotation
Expected: Verified
@wp
coproc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
pre init_count + 1
post count
{
count = init_count
running = init_running
// The second guard check uses post count when running is false.
@k_induction(2, count + 1)
while running {

Its average value grows by one half after one iteration, because even after heads it still adds one to the counter. Park induction therefore fails for this candidate.

Two-step induction, selected by the @k_induction(2, count + 1) annotation, checks the loop guard again. On the heads branch, the loop has finished, so it uses the postexpectation count instead of the candidate [Batz et al. 2021, Example 2]. If the loop starts inactive, this upper bound is one above the unchanged counter.

Optional Stopping​

The proc specification gives the matching lower bound, using the same expectation count + [running]. A subinvariant alone is insufficient, so the @ost annotation checks additional side conditions [Hark et al. 2020, Example 39].

Lower-bound specification and @ost annotation
Expected: Verified
@wp
proc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
pre init_count + [init_running]
post count
{
count = init_count
running = init_running
// count + [running] changes by -1 after heads and +1 after tails.
// Its expectation is unchanged, and at termination it equals count.
// 2 * [running] bounds the expected number of remaining coin flips.
// Each active iteration changes the subinvariant by exactly 1 in absolute value.
@ost(count + [running], 2 * [running], 1, count)
while running {
  • The second argument, 2 * [running], bounds the expected number of remaining coin flips by two for an active loop and zero otherwise.
  • The third argument, 1, bounds each iteration's absolute change to the subinvariant.

The upper and lower bounds match for every initial count and value of running. In particular, an active loop starting at zero has expected count one.

Refuting the Upper Bound init_count + 0.99​

Finite unrolling can also reject a proposed bound without first computing the exact expectation [Batz et al. 2021, Example 2]. The next variant proposes the upper bound init_count + 0.99.

Incorrect specification and @unroll annotation
Expected: Counter-example to property found
@wp
coproc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
pre init_count + 0.99
post count
{
count = init_count
running = init_running
// Unexplored executions contribute zero to the lower approximation.
// With init_count == 0 and init_running == true, it is 509/512 > 0.99.
@unroll(12, 0)
while running {

For an active loop starting at zero, the @unroll(12, 0) annotation gives the lower approximation 509/512>0.99509/512>0.99. The eleventh unfolding is still below the proposed bound. The twelfth refutes it.

Finite unrolling refutes the geometric loop's bound of 0.99Starting with count zero and running true, the lower approximation is 251/256 after ten unfoldings, 1013/1024 after eleven, and 509/512 after twelve. The twelfth approximation is the first to exceed 0.99. The vertical axis is zoomed to the interval from 0.98 to one.0.990.981.00Lower approximation101112509/512Unfoldings

Recursive Formulation​

The same coin-flipping process can be written using recursive calls in place of the loop. Each call uses the procedure specification to bound the expected number of tails still to come.

Recursive specification
Expected: Verified
@wp
coproc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
pre init_count + [init_running]
post count
{
count = init_count
running = init_running
if running {
var stop: Bool = flip(0.5)
if stop {
running = false
} else {
count = count + 1
}
// Apply the same specification to the recursive call with the updated arguments.
count, running = geometric(count, running)
} else {}
}

An inactive call returns the counter unchanged, while an active call increases it by at most one in expectation over the entire recursive execution. The verified upper bound is the same as for Park induction.

See Also​

  • Coupon Collector bounds the expected number of draws needed to collect each new coupon.
  • One-Sided Random Walks generalizes waiting for one head to several required heads and bounds the total number of coin flips.

References​