Skip to main content

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 1/(x+1)1/(x+1) and otherwise increases x by one. Does the loop still terminate with probability one?

Escaping splineAn incoming arrow marks the initial position one. From each positive position x, one iteration jumps to zero with probability 1/(x+1), or advances to x+1 with probability x/(x+1), and zero ends the execution.0123½⅔¾½⅓¼…

The Program​

The procedure starts at the nonnegative integer init_x and repeats this step while x is positive.

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

Almost-sure termination specification and @ast annotation
Expected: 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 probability 1/(x+1).

  • Expected variant: one iteration does not increase its expected value:

    1x+1β‹…0+xx+1β‹…(x+1)=x.\frac{1}{x+1}\cdot 0+\frac{x}{x+1}\cdot(x+1)=x.

The functions 1/(v+1) and 1 are positive and nonincreasing for vβ‰₯0v\ge0, 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 m>0m>0, let TT count the loop iterations. Executing more than nn iterations requires nn consecutive increments:

Pr⁑(T>n)=∏k=0nβˆ’1m+km+k+1=mm+n(nβ‰₯0).\Pr(T>n)=\prod_{k=0}^{n-1}\frac{m+k}{m+k+1}=\frac{m}{m+n} \qquad(n\ge 0).

Summing these probabilities gives the expected number of iterations:

E[T]=βˆ‘n=0∞Pr⁑(T>n)=βˆ‘n=0∞mm+n=∞.\mathbb{E}[T]=\sum_{n=0}^{\infty}\Pr(T>n) =\sum_{n=0}^{\infty}\frac{m}{m+n}=\infty.

The harmonic series diverges, so the loop is not positively almost-surely terminating for m>0m>0.

See Also​

References​