One-Sided Random Walks
Obtaining several successes from repeated independent trials may take arbitrarily many attempts. Our countdown models this with a fair coin: a counter records how many heads are still needed, decreasing on heads and staying unchanged on tails [McIver et al. 2018].
Does the countdown reach zero with probability one, and is the expected number of flips finite? We prove both properties, then derive numerical bounds for two related walks.
Countdown with Pausesβ
The procedure countdown starts at the nonnegative integer init_x and stops at zero, when all required heads have occurred.
Each iteration makes one coin flip.
Almost-Sure Terminationβ
With pre 1, post 1, and the @ast annotation, Caesar proves that the countdown reaches zero with probability one.
The @wp annotation selects the calculus in which post 1 measures the termination probability.
Verified@wp
proc countdown(init_x: UInt) -> (x: UInt)
pre 1
post 1
{
x = init_x
// The variant x is nonnegative.
// Each iteration decreases it by at least one with probability 0.5.
// Its expected value does not increase.
@ast(true, x, v, 0.5, 1)
while x > 0 {
var step: Bool = flip(0.5)
if step {
x = x - 1
} else {}
}
}
The variant is x.
For , one iteration decreases it by one with probability , and its expected value is
These establish the progress and expected-value conditions of the almost-sure termination rule.
Positive Almost-Sure Terminationβ
The countdown charges reward 1 per flip, and Caesar verifies that the expected number of flips is at most 3 * init_x + 1.
The @past annotation proves positive almost-sure termination and supplies this upper bound for the @ert coproc.
Verified@ert
coproc countdown(init_x: UInt) -> (x: UInt)
pre 3 * init_x + 1
post 0
{
x = init_x
// The ranking expression 3 * x + 1 decreases by 0.5 in expectation after paying for the flip.
// The threshold 1 bounds the expression from below while x > 0 and from above at exit.
@past(3 * x + 1, 0.5, 1)
while x > 0 {
reward 1
On heads, the ranking superinvariant 3 * x + 1 drops by .
After charging for the flip, its expected decrease is .
It is above the threshold while the loop is active and equals at exit.
Expected Number of Coin Flips to Reach a Targetβ
We now count up to a target instead of counting down to zero.
The procedure forward_walk starts at init_x and stops when x >= init_n.
Each fair coin flip either increases x by one or leaves it unchanged.
With the @ert annotation, each tick 1 counts one flip.
The coproc specification bounds the expected number of flips by 2 * (init_n - init_x).
Subtraction on UInt stops at zero, so the bound is zero if the target has already been reached.
Verified@ert
coproc forward_walk(init_x: UInt, init_n: UInt) -> (x: UInt, n: UInt)
pre 2 * (init_n - init_x)
post 0
{
x = init_x
n = init_n
// Twice the remaining distance bounds the expected number of coin flips.
@invariant(2 * (n - x))
while x < n {
var step: Bool = flip(0.5)
if step {
x = x + 1
} else {}
tick 1
}
}
The @invariant annotation supplies I = 2 * (n - x) as a bound on the expected number of coin flips still needed.
Its expected decrease covers the current tick 1:
At exit the invariant is zero, matching post 0.
Expected Number of Coin Flips with Steps of One or Twoβ
The final countdown has no pauses: a biased coin flip decreases x by one with probability and by two with probability .
It stops when x is zero or one, and each flip still counts as one tick.
The coproc specification bounds the expected number of flips by .
Verified@ert
coproc countdown(init_x: UInt) -> (x: UInt)
pre 0.6 * init_x
post 0
{
x = init_x
// The invariant bounds the expected number of remaining coin flips by 0.6 * x.
// Each iteration decreases it by one in expectation, accounting for one coin flip.
// At exit, it is nonnegative and covers the zero postexpectation.
@invariant(0.6 * x)
while x >= 2 {
var short_step: Bool = flip(1/3)
if short_step {
x = x - 1
} else {
x = x - 2
}
tick 1 // Count the single coin flip in this iteration.
}
}
The @invariant annotation supplies , which covers the tick because
At exit, bounds post 0.
See Alsoβ
- Geometric Loop is the countdown with pauses when one head is required, counting tails before that head rather than all coin flips.
- Two-Sided Random Walks includes steps away from the target and adversarial choices.
Referencesβ
-
McIver et al. (2018). A New Proof Rule for Almost-Sure Termination. POPL.
The negative-binomial loop is the countdown with pauses verified using the
(Section 5.1)@astannotation. -
SchrΓΆer et al. (2023). A Deductive Verification Infrastructure for Probabilistic Programs. OOPSLA.
The benchmark
(Table 2)linear01is the countdown with steps of one or two.