math.PRAug 20, 2026
SaveInformation on trajectories: martingales and random times
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 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.
Figures & tables
Figure 1: Each classical inequality leaves a residual the path-space calculus names and measures. All four residuals are drawn in nats on a common axis. The pathwise PAC-Bayes slack (a) is the divergence to the running Gibbs tilt: identically zero at the Bayes posterior at every step, growing for a prior-anchored posterior as the tilt departs the prior, and decaying for a greedy one as the tilt concentrates. A Gaussian test martingale evaluated at the time of its running maximum incurs the peeking penalty (b) . It passes the entire Ville budget nats at by step and keeps growing, while the anticipation it measures saturates at nats—below the one nat a continuous path would incur, short by the overshoot of a discrete walk. Taking logarithms through Doob’s inequality (c) turns its sharp constant into an additive budget of nats. The martingale spends the logarithm of its maximal-to-terminal norm ratio and leaves the rest; the budget vanishes as . This is the one residual here that is not a relative entropy, and Section 5 resolves it. Pooling test martingales (d) tightens Ville’s bound by the crossing form of the multi-way coincidence divergence, , with the first time the pooled process reaches . It grows in both the crossing level and the bettor count (logarithmic axes), reaching tens of nats as independent disagreement accumulates. Bootstrap intervals lie within the markers except in the deepest tail.
Figure 2: The free energy rises exactly where the antonym exercise leaves a choice. It is flat through every slot the exercise determines. The completions of a small open-weights language model (Qwen2.5-0.5B) stay coincident through the determined slots and branch at the free ones. Both panels describe that one run on a shared token axis. (a) The coincidence tree: a path read left to right is one completion, and edge width tracks the number of copies sharing that prefix. The posed item is answered near-unanimously— copies take soft and the second admissible sense easy —and the frame tokens “of” and “is” are taken by every surviving copy. The two shaded slots are the ones the exercise leaves free: the continuation after the answer, and the next word to ask about. A lineage that picks a word is then determined again by its own choice, giving big small , small big and left right ; the remaining continuations at each contested slot are folded into a wedge. (b) The coincidence free energy of the same tree, the case of Proposition 3.6 , where is the probability that two independent copies share the prefix at , estimated over all prefixes by the unbiased pair-collision estimator with a bootstrap interval over completions (band). Its two risers are exactly the two shaded slots of (a), costing and nats, while the determined slots cost between and ; the exponential of a riser is the effective number of equally likely words at that slot. Color grades each slot by what its token costs, from committed to contested.
Figure 3: The master identity sits at the peak of a free-energy landscape, and every classical relaxation steps down from it by an amount that widens a confidence band. (a) The identity ( 4.3 ) drawn as a Donsker–Varadhan free-energy landscape. Along the exponential-tilt family the variational objective, energy minus relative-entropy cost, is unimodal in the tilt and attains its supremum at the Gibbs tilt. The value there equals the log-expectation of the exponential process: zero for the exact conditional log-CGF ( 4.2 ), and below zero by exactly the cumulant gap ( 4.5 ) under a majorant. Shown for a Rademacher increment under the Hoeffding cumulant at , with dotted guides at the maximizing tilt and the value it attains. (b) What those steps cost, on a Bernoulli stream with true mean read at level . Four running-mean envelopes at one level: the exact relative-entropy tail inverted at a single pre-specified time (dashed) and uniformly over all times (solid blue), and the range-based Azuma–Hoeffding tail inverted uniformly (orange). The two shaded rings are the paper’s two named residuals, and they are orthogonal. The inner ring is the Ville anytime slack, the width that holding at every time costs over holding at one, of the band at and at . The outer ring is the relative-entropy residual, what a range-based reading discards against the exact tail, and at the same two horizons. The asymmetry of the exact envelopes is the variance-awareness the range-based reading throws away.
| Classical statement | Identity it relaxes | What it discards | Geometry |
|---|---|---|---|
| Ville | first-passage identity (Thm. 4.7 ) | the mean overshoot at the crossing; for a supermartingale also the predictable loss and the never-crossing mass | optional stopping |
| Azuma–Hoeffding | per-step relative-entropy sum ( B.2 ) | the event relaxation, the tilt’s sub-optimality, and the range-based cumulant majorant ( 4.13 ) | Gibbs / entropic |
| Bennett–Bernstein–Freedman | the same identity at a variance-aware cumulant | the same three, the majorant gap now keeping a proxy for the higher cumulants | Gibbs / entropic |
| Parameter mixtures (method of mixtures) | pathwise mixture identity, tail exact (Prop. B.8 ) | the overshoot at the crossing and the set on which the mixture crosses while the certificate never fires | Gibbs / entropic |
| Curved boundary of any form | discrete crossing law (Thm. 4.9 ) | a quadrature residual and an overshoot, both zero in continuous time and computable in advance | optional stopping |
| PAC-Bayes (martingale form) | pathwise Gibbs-tilt identity (Prop. B.8 ) | the divergence to the running tilt, zero at the Bayes posterior, then the Ville relaxation | Gibbs / entropic |
Table 1: The standard bounds as identities with named residuals, across the three geometries. Upper segment : the classical statement, the identity it relaxes, what it discards to get there, and the geometry in which that discard is the deficit of an optimizer; every entry points at the result that develops it. Lower segment (the power-mean certificate family of Section 5 ): each row is an inequality proved by a certificate dominating and supermartingale along the path. The certificate form ( 5.7 ) names the discarded quantities—a majorization deficit, an optional-stopping deficit, and an initial value—and “Evaluated” records whether this paper computes those quantities or only names them. The Burkholder–Davis–Gundy row is evaluated on a second axis, the cost of moving from a stopping time to a random time; in that row is a moderate convex function—increasing, vanishing at the origin, and with bounded by a constant multiple of . ; is the square function.
Figure 4: What evidence costs, in nats, along realized paths. A Gaussian stream read through the mixture of Proposition B.7 over a grid of tilts; the spend on a step is between consecutive optimal posteriors, and a milestone is the first crossing of by . Both panels are read against the same evidence level , so the pair gives what a level costs beside how often it is reached. Left: the fraction of all paths per effect size reaching each level, with Wilson intervals, against the level’s own bound. The null arm tracks below that bound throughout: crossing rates , , , and against , , , and , the last being four crossings where three are expected. Right: the cumulative spend to first reach each level, median and interquartile band, so the rise between two ticks is the information that next factor of evidence requires. Each level is drawn only where at least paths reached it, and the statistics are conditional on arrival, which is why the null and weak curves stop early: reaching a deep level under a weak signal selects the paths that moved fastest, and too few remain to summarize. The effect size decides how often a level is reached and barely touches what reaching it costs. At the deepest level the three arms differ -fold in the fraction arriving, while their median total spend differs by a factor of : nats under the null, at the weak effect and at the strong one.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: A boundary that moves in the natural coordinates is a flat level after the transform. (a) The drawdown of a symmetric walk below its running maximum , against the boundary (heavy) and the level sets foliating the region beneath it; crossing is entry into the shaded region. (b) The same level sets after the transform , drawn at the same abscissae: each one is horizontal, and the boundary is the level . The clock advances only while the drawdown is at zero, so a path meets the boundary in one vertical probe per record. The marked point is the path’s first crossing, which lands on the boundary in (a) and on in (b), and the path starts at the level the continuous-path idealization spends. The path drawn is one that crosses late; at this boundary most crossings happen at the first record, where the boundary sits only two steps above it.
Figure 6: The overshoot term recovers almost all of what Ville’s bound gives away. Each prediction of the crossing rate, divided by the rate observed on null replicates of a sequential likelihood ratio against the label-marginal null; is exact, and height above it is the multiplicative shortfall. At every level the two predictions are joined: the triangle is Ville’s , which overstates by up to , the circle is the identity read forward from the measured overshoot, and the connector between them is the part the overshoot term recovers. The identity sits on at of the levels, inside the shaded interval on the observed rate; the bound sits outside that interval at of them. One panel per stream, since the two level grids share no positions. The interval widens with the level because its width in this ratio is set by the number of crossings alone, and the deepest level plotted is the one of replicates reach.
Figure 7: A finite horizon falls short of the asymptotic crossing rate by exactly the mass still sitting on paths that have not crossed. Simulated drawdowns of a symmetric walk against , at five horizons from to steps. Circles are the crossing rate observed on those walks; squares give the finite-horizon identity’s prediction once the uncrossed mass is included, offset slightly in the horizon for legibility. The dotted segments are that uncollected mass, closing as the horizon grows. Intervals are : on the observed rate its own binomial interval, and on the prediction the interval of the residual, which is the uncertainty the comparison actually incurs. The residual is mean-zero and covers zero at every horizon.
Figure 8: The horizon leaves the first-passage deficit where it is; refining the step closes it, at the rate the increment scale sets. (a) sweeping the horizon at unit step leaves unmoved across a factor of , at every tilt; this sweep is run on the Gaussian family. (b) the deficit against the increment scale , on log-log, where it is a power law: dotted lines are the fitted decays, and a slope of is the overshoot reading. The Gaussian family sits on its fit at every tilt; the two-point family reads a shallower slope and, at , departs visibly from a single power law — the increment-distribution dependence Theorem 4.7 records, which is why the two families are reported separately and not pooled. Both panels are read at .
| within-family | cross-family | difference | |
|---|---|---|---|
| (control) | (control) | — | |
Table 2: Both pools show a pooling benefit; the architecturally diverse pool shows more of it at . Paired excess deficit by pool and ensemble size, stream orderings per cell, bootstrap intervals. The row is the control and is zero by construction.
More in this topic
Anytime-Valid Inference
Anytime-valid inference provides statistical tests and confidence bounds that remain valid under repeated monitoring, adaptive sampling, and data-dependent stopping.
See all 35 papers