Information on trajectories: martingales and random times
2026-08-20 • Information Theory
Information TheoryMachine Learning
AI summaryⓘ
The authors study how information flows along paths of nonnegative martingales, a type of mathematical process used to model randomness. They derive exact formulas that connect these processes to well-known probability bounds like Ville's inequality and PAC-Bayes bounds. Their work shows what parts of the information these classical bounds ignore and explains this in terms of entropy and divergences. They also explore how these ideas change when considering random stopping times, introducing a new penalty concept for anticipating the future. Finally, they describe how combining multiple models can improve testing performance through geometric mixtures of martingales.
Nonnegative martingaleInformation flowConcentration inequalitiesVille's inequalityPAC-Bayes boundsRelative entropyBregman divergenceOptional stoppinge-processGeometric mixture
Authors
Akshay Balsubramani
Abstract
Accounting for information flow on the path space of trajectories of a nonnegative martingale yields exact variational identities for it, even at arbitrary random times. This recovers the widely used classical concentration inequalities, from Ville to PAC-Bayes, and measures what each one discards. The tail a bound controls is itself a relative entropy, resolved by the chain rule into per-step conditional divergences. The discarded slack has an exact form in each of three geometries: a Gibbs tilt for the Azuma-Hoeffding and PAC-Bayes bounds, the crossing itself for Ville's and for pooled tests, and a dominating certificate for the $L^p$ maximal bound. That certificate's optional-stopping deficit resolves per step into Bregman divergences of the running maximum. On a path-time space, the same identity gains one factor that prices anticipation: an arbitrary random time carries an e-process ``peeking penalty.'' The partition function can be read as a coalescent--a prefix-sharing probability of independent copies--and geometric mixtures of test martingales gain a pooling benefit for multi-model safe testing.