Two-Sided Random Walks
A random walk can move away from its target, so progress made on one step may be lost on the next. Our first program moves two places toward a target or one place away, using a fair coin to choose the direction.
We bound the expected number of flips needed to reach the target, then ask whether related walks terminate with probability one when choices are adversarial or steps depend on parity.
Positive Driftβ
The procedure drift_walk starts at init_x and stops when x >= init_n.
A fair coin flip increases x by two or decreases it by one.
At zero, the downward step leaves x unchanged.
With the @ert annotation, each tick 1 counts one flip.
The coproc specification bounds the expected number of flips from above by 2 * ((init_n + 1) - init_x).
Verified@ert
coproc drift_walk(init_x: UInt, init_n: UInt) -> (x: UInt, n: UInt)
pre 2 * ((init_n + 1) - init_x)
post 0
{
x = init_x
n = init_n
// The invariant bounds the expected number of remaining coin flips.
// Its expected decrease covers the one tick charged per iteration.
// The extra one in n + 1 permits overshooting the target by one.
// At exit, the invariant is nonnegative and covers the zero postexpectation.
@invariant(2 * ((n + 1) - x))
while x < n {
var up: Bool = flip(0.5)
if up {
x = x + 2
} else {
x = x - 1
}
tick 1 // Count the single coin flip in this iteration.
}
}
The @invariant annotation supplies I = 2 * ((n + 1) - x).
The n + 1 in I allows for a final step to overshoot the target by one.
The expected cost including the tick is at most
At exit, bounds post 0.
Demonic Choiceβ
The demonically fair walk, implemented by demonic_walk, starts at init_x and stops at zero.
A fair coin decides whether to decrease x by one or make a demonic choice between increasing it by one and staying put.
With pre 1, post 1, and the @ast annotation, Caesar proves almost-sure termination under every resolution of the demonic choice.
Verified@wp
proc demonic_walk(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 under either demonic choice.
@ast(true, x, v, 0.5, 1)
while x > 0 {
var down: Bool = flip(0.5)
if down {
x = x - 1
} else {
if \cap {
x = x + 1
} else {}
}
}
}
The variant x decreases by one with probability .
Its expected value is at most
Choosing to stay put gives a smaller expectation, so either demonic choice satisfies the expected-value condition.
This walk also models a recursive process in which x counts pending calls [McIver et al. 2018, Β§5.2].
A call either returns or is replaced by one or two further calls, with the number of new calls chosen demonically.
Parity-Dependent Stepsβ
The final walk uses different steps at even and odd positions.
The procedure parity_walk starts at any nonnegative integer init_x and stops at ten.
At even positions it moves down or up by two with equal probability. At odd positions it moves up by one without flipping a coin.
Caesar again proves almost-sure termination with pre 1, post 1, and the @ast annotation.
Verified@wp
proc parity_walk(init_x: UInt) -> (x: UInt)
pre 1
post 1
{
x = init_x
// Measure the distance from ten, adding three at odd positions.
// Its expected value does not increase, and a decrease of at least two has probability at least 0.5.
// The additional three covers the deterministic step from an odd to an even position.
@ast(true, 3 * ite(x % 2 != 0, 1, 0) + ite(x >= 10, x - 10, 10 - x), v, 0.5, 2)
while x != 10 {
if x % 2 == 0 {
var down: Bool = flip(0.5)
if down {
x = x - 2
} else {
x = x + 2
}
} else {
x = x + 1
}
}
}
- Odd positions: the term
3 * ite(x % 2 != 0, 1, 0)compensates for a step away from ten. It drops by three at the next even position, so the variant decreases by at least two. - Even positions: a decrease by two has probability at least , and the expected variant does not increase.
See Alsoβ
- One-Sided Random Walks studies walks that never move away from the target.
- Escaping Spline is another two-sided walk, with upward steps and a state-dependent probability of jumping directly to zero.
- Rabinβs Mutual-Exclusion Algorithm illustrates a probability bound whose proof leaves termination open.
Referencesβ
-
McIver et al. (2018). A New Proof Rule for Almost-Sure Termination. POPL.
The demonically fair random walk illustrates termination under every resolution of the demonic choice.
(Section 5.2)