The Treachery of Certificates: Ceci n’est pas une supermartingale
To prove that a stochastic system exhibits a desired behavior with high probability (for example, that it reaches a target while avoiding danger) it often suffices to produce a single function on its states satisfying a few pointwise inequalities: a supermartingale certificate. Finding such a function is the hard part; checking one is easy, which is why neural networks, as flexible function-searchers, have become a natural tool for the job.
But a certificate is a static object — a function you can write down — while the object that actually carries the proof is a stochastic process: its dynamic interpretation as it rides the system’s randomness. These are not the same thing, and the passage between them is not canonical: one function can induce many supermartingales, depending on how we stop, shift, or time-compensate it. We’ll build both objects from scratch, make the construction explicit, and see why conflating them — a common slip, even among practitioners — is exactly where soundness is won or lost.