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 . 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.
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.
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 contains jumps that lead to both outcomes.
The hare's jump is ten times a draw from . The encoding divides that interval into eight equal parts.
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 .
Then cohavoc and coassume take the supremum over all values in the selected interval.
For a measurable expectation , this gives the upper sum
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
URealvariables, sequential composition,if, andwhile. - Probabilistic choice, written as
flip(p)followed byif, with fixed rational . - Continuous uniform draws from 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 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 be the original continuous loop and its body after the sampling encoding above.
Caesar checks the following inequality whenever h <= t:
At loop exit, , 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
See Also
- Two-Sided Random Walks bounds round counts for a walk with discrete steps.
- The continuous-programs article introduces the general encoding and further case studies.
References
-
Batz et al. (2025). Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back. OOPSLA 2025.
Develops sound Riemann approximations and gives the race's analysis, bound, and HeyVL encoding.
(Sections 9.2.3–9.3 and Appendix C.24)