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
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.
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 tails followed by heads has probability . 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.
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 and tails gives .
Their average is , 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.
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].
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.
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 .
The eleventh unfolding is still below the proposed bound.
The twelfth refutes it.
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.
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
-
Kaminski et al. (2016). Weakest Precondition Reasoning for Expected Run-Times of Probabilistic Programs.
Explains why arbitrarily long executions can have finite expected runtimes and analyzes the coupon collector.
(Sections 1, 7.2) -
Batz et al. (2021). Latticed k-Induction with an Application to Probabilistic Programs. CAV.
The geometric loop demonstrates an upper bound that requires two-step induction.
(Example 2) -
Hark et al. (2020). Aiming Low Is Harder: Induction for Lower Bounds in Probabilistic Program Verification. POPL.
The paper proves the lower bound by optional stopping.
(Example 39)