Finite Expected Runtime Does Not Compose
A generator starts with a counter of one, doubles it on every flip of a fair coin, and returns it after the first heads. A countdown decrements its input to zero. Each program has finite expected runtime for every fixed input. Running the countdown on the generator's output has infinite expected runtime [Kaminski et al. 2016].
The counter is unbounded, and we count one tick per flip or decrement.
With @ert and post 0, the specifications bound the expected tick count.
The Two Programs
The Generator
Caesar verifies that the generator takes at most two coin flips on average.
Verified@ert
coproc generator() -> (stake: UInt)
pre 2
post 0
{
stake = 1
var more: Bool = true
@invariant(2 * [more])
while more {
tick 1
more = flip(0.5)
stake = 2 * stake
}
}
The Countdown
The countdown takes one tick for each unit of its input, and Caesar verifies the upper bound.
Verified@ert
coproc countdown(init_stake: UInt) -> (stake: UInt)
pre init_stake
post 0
{
stake = init_stake
@invariant(stake)
while stake > 0 {
tick 1
stake = stake - 1
}
}
Their Composition
Caesar verifies that every natural number is a lower bound on the expected runtime of the composed program. The expected runtime is therefore infinite.
Verified@ert
proc composition(target: UInt) -> (stake: UInt)
pre target
post 0
{
stake = 1
var more: Bool = true
@omega_invariant(n, ite(more, stake * (n ⊓ target), stake))
while more {
tick 1
more = flip(0.5)
stake = 2 * stake
}
@omega_invariant(n, n ⊓ stake)
while stake > 0 {
tick 1
stake = stake - 1
}
}
Stopping on flip has probability and leaves decrements, so each possible stopping time contributes tick to the expected countdown cost. The generator's omega invariant adds these contributions, and the countdown's supplies the cost when the generator stops. The target appears only in the proof, so every bound applies to the same program.
The composition terminates almost surely because the first heads arrives with probability one and every resulting countdown is finite.
References
-
Kaminski et al. (2016). Weakest Precondition Reasoning for Expected Run-Times of Probabilistic Programs.
Introduces the failure of finite expected runtimes to compose and develops expected-runtime reasoning. The extended version gives a composition example in Example 6.