Skip to main content

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.

Countdown from threeAn incoming arrow marks the initial counter value three. The chain runs downward to zero, with probability one half of decreasing and probability one half of taking the self-loop at each positive counter value.3210Β½Β½Β½Β½Β½Β½

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.

Almost-sure termination annotation
Expected: 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 x>0x>0, one iteration decreases it by one with probability 1/21/2, and its expected value is

12β‹…(xβˆ’1)+12β‹…x=xβˆ’12≀x.\tfrac12\cdot(x-1)+\tfrac12\cdot x=x-\tfrac12\le x.

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.

Positive almost-sure termination and an upper bound on flips
Expected: 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 33. After charging for the flip, its expected decrease is 12β‹…3βˆ’1=12\tfrac12\cdot 3 - 1 = \tfrac12. It is above the threshold K=1K=1 while the loop is active and equals KK 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.

Expected number of coin flips: specification and invariant
Expected: 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:

1+12β‹…(Iβˆ’2)+12β‹…I=I.1+\tfrac12\cdot(I-2)+\tfrac12\cdot I=I.

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 1/31/3 and by two with probability 2/32/3. 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 0.6β‹…init_x0.6\cdot\mathtt{init\_x}.

Expected number of coin flips: specification and invariant
Expected: 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 I(x)=0.6β‹…xI(x)=0.6\cdot x, which covers the tick because

1+13β‹…I(xβˆ’1)+23β‹…I(xβˆ’2)=I(x)(xβ‰₯2).1+\tfrac13\cdot I(x-1)+\tfrac23\cdot I(x-2)=I(x) \qquad(x\ge2).

At exit, I(x)β‰₯0I(x)\ge0 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​