Escaping Spline
The escaping spline becomes less likely to stop after each unsuccessful attempt [McIver et al. 2018].
While its position x is positive, each iteration jumps to zero with probability and otherwise increases x by one.
Does the loop still terminate with probability one?
The Programβ
The procedure starts at the nonnegative integer init_x and repeats this step while x is positive.
proc escaping_spline(init_x: UInt) -> (x: UInt) {
x = init_x
while x > 0 {
var stop: Bool = flip(1 / (x + 1))
if stop {
x = 0
} else {
x = x + 1
}
}
}
If init_x is zero, the loop performs no iterations.
Verificationβ
With the @wp annotation and postexpectation 1, the weakest preexpectation is the termination probability.
Caesar verifies pre 1, establishing almost-sure termination (termination with probability one) for every init_x.
The @ast annotation uses variant x:
Verified@wp
proc escaping_spline(init_x: UInt) -> (x: UInt)
pre 1
post 1
{
x = init_x
@ast(
/* invariant: */ true,
/* variant: */ x,
/* variable: */ v,
/* prob(v): */ 1/(v+1),
/* decrease(v): */ 1
)
while x > 0 {
For the highlighted annotation, Caesar checks:
-
Progress: for positive integer
x, the jump to zero decreases the variant by at least one with probability1/(x+1). -
Expected variant: one iteration does not increase its expected value:
The functions 1/(v+1) and 1 are positive and nonincreasing for , with 1/(v+1) <= 1.
Expected Number of Iterationsβ
Almost-sure termination alone does not imply a finite expected number of iterations. For this loop, the separate calculation below shows that the expected number is infinite whenever the initial value is positive.
Starting at , let count the loop iterations. Executing more than iterations requires consecutive increments:
Summing these probabilities gives the expected number of iterations:
The harmonic series diverges, so the loop is not positively almost-surely terminating for .
See Alsoβ
- One-Sided Random Walks starts with a constant probability of making progress.
- Two-Sided Random Walks studies other members of this family, with steps toward or away from a target and adversarial choices.
Referencesβ
-
McIver et al. (2018). A New Proof Rule for Almost-Sure Termination. POPL.
Proves almost-sure termination of the escaping spline using a state-dependent probability of progress.
(Section 5.4)