Skip to main content

Continuous Tortoise–Hare Race

A tortoise advances one unit per round, while a hare flips a fair coin to decide whether to move. When the hare moves, its jump is sampled uniformly from the continuous interval [0,10][0,10]. The race ends when the hare is ahead after both have moved [Batz et al. 2025]. We want an upper bound on the expected final round count.

Reusing this encoding

Caesar checks the encoding, whose soundness relies on the conditions below. Check these conditions when adapting the encoding to another continuous program.

The Program​

The program starts at positions init_h and init_t, counts completed rounds in count, and approximates the hare's continuous jumps using eight intervals.

Race with an upper approximation of continuous sampling
Expected: Verified
@wp
coproc tortoise_hare(init_h: UReal, init_t: UReal) -> (count: UReal)
pre 3.38 * ((init_t - init_h) + 2)
post count
{
var h: UReal = init_h
var t: UReal = init_t
count = 0

// Bound the final round count by rounds so far plus a bound for the remaining gap.
@invariant(ite(h <= t, count + 3.38 * ((t - h) + 2), count))
while h <= t {
var choice: Bool = flip(0.5)
if choice {
var inc: UReal
var N: UInt = 8
var j: UInt = unif(0, 7)
// Upper Riemann sum: choose any point in the sampled interval.
cohavoc inc
coassume !?(j / N <= inc && inc <= (j + 1) / N)
h = h + 10 * inc
} else {}
t = t + 1
count = count + 1
}
}

For init_h <= init_t, the pre clause bounds the expected final count by 3.38 * ((init_t - init_h) + 2). If the hare starts ahead, the loop is skipped and the count is zero. Under @wp, nonterminating runs contribute zero, so this bound does not prove termination.

Continuous Sampling​

Suppose the hare starts a round at 0 and the tortoise moves from 2 to 3. The hare must jump more than 3 units to end the race. The highlighted interval [2.5,3.75][2.5,3.75] contains jumps that lead to both outcomes.

The hare's jump intervals and the finish thresholdThe hare starts at zero and the tortoise advances from two to three. If the hare moves, its possible jump distances from zero to ten are divided into eight equal intervals. The highlighted interval from 2.5 to 3.75 contains both jumps that leave the race running and jumps longer than three that end it.Jump distance if the hare movesTortoise at 302.53.7510ContinueFinish

The hare's jump is ten times a draw from [0,1][0,1]. The encoding divides that interval into eight equal parts.

Upper Riemann approximation of the hare's jump
var inc: UReal
var N: UInt = 8
var j: UInt = unif(0, 7)
// Upper Riemann sum: choose any point in the sampled interval.
cohavoc inc
coassume !?(j / N <= inc && inc <= (j + 1) / N)
h = h + 10 * inc

The unif(0, 7) draw chooses each interval with probability 1/81/8. Then cohavoc and coassume take the supremum over all values in the selected interval. For a measurable expectation ff, this gives the upper sum

∫01f(u) du≤18⋅∑j=07sup⁡u∈[j/8,(j+1)/8]f(u).\int_0^1 f(u)\,du \le \frac18\cdot\sum_{j=0}^{7} \sup_{u\in[j/8,(j+1)/8]} f(u).

The supremum accounts for every possible move within an interval, including jumps that change whether the race continues.

Soundness Conditions​

The paper's source programs use the following constructs, expressed here in HeyVL notation [Batz et al. 2025, Definition 4.1]:

  • Assignments to UReal variables, sequential composition, if, and while.
  • Probabilistic choice, written as flip(p) followed by if, with fixed rational p∈[0,1]p\in[0,1].
  • Continuous uniform draws from [0,1][0,1] using the encoding above, and hard observations written as assert ?(b).

Assignments, guards, and postexpectations must be measurable. The race meets this requirement through polynomial arithmetic and comparisons, with postexpectation count.

Verification​

Let II denote the expectation in the @invariant annotation. While h <= t, its term 3.38 * ((t - h) + 2) bounds the expected rounds still to come, in addition to those already counted.

Let CC be the original continuous loop and BB its body after the sampling encoding above. Caesar checks the following inequality whenever h <= t:

vp⁡⟦B⟧(I)≤I.\operatorname{vp}\llbracket B\rrbracket(I)\le I.

At loop exit, I=countI=\mathtt{count}, giving the required postexpectation. The factor 3.38 satisfies these checks with eight intervals [Batz et al. 2025, Table 2].

The paper's upper-bound theorem [Batz et al. 2025, Theorem 6.2(1)] then gives

wp⁡⟦C⟧(count)≤I.\operatorname{wp}\llbracket C\rrbracket(\mathtt{count})\le I.

See Also​

References​