Information on trajectories: martingales and random times

Core Contribution§

This paper derives exact variational identities for a nonnegative martingale $M_t$ by tracking information flow on its path space. The central object is a relative entropy between the martingale's path measure and a reference measure, resolved via the chain rule into per-step conditional divergences. The identity takes the form

$$\mathbb{E}_{\mathcal{F}_\tau}[\log M_\tau] = \sum_{t=1}^{\tau} \mathbb{E}[ D_{\mathrm{KL}}(Q_{t} \,\|\, P_{t} \mid \mathcal{F}_{t-1}) ] + \text{slack},$$

where the slack is nonnegative and has an exact, geometry-dependent expression.

Three Geometries of Slack§

The paper shows that classical bounds discard different, exactly identified quantities:

• Gibbs tilt (Azuma-Hoeffding, PAC-Bayes): The slack equals a cumulant-generating function difference, measured as a tilt in the exponential family. This is the extra mass that a Gaussian or Bernoulli tail bound loses compared to the true martingale.
• Crossing term (Ville's inequality, pooled tests): For Ville's bound, the slack is exactly the indicator that the martingale ever exceeds a threshold—the crossing event itself. This reveals that Ville's inequality is tight exactly when the crossing happens, and loose otherwise.
• Bregman certificate ($L^p$ maximal bound): For the $L^p$ maximal inequality, the optional-stopping deficit decomposes per step into Bregman divergences of the running maximum $\bar{M}_t = \max_{s \le t} M_s$:

$$\text{deficit} = \sum_{t=1}^{\tau} B_{\phi}(\bar{M}_t \,\|\, \bar{M}_{t-1}), \quad \phi(x) = x^p.$$

This gives a fine-grained, additive explanation of why the maximal bound loses mass.

Random Times and Peeking Penalty§

A major novelty is the extension to arbitrary random times $\tau$, not just stopping times. The authors introduce an e-process—a nonnegative process with expected value at most 1 under the null—that quantifies the cost of "peeking" at the data before choosing $\tau$. On a path-time space, the identity gains an extra multiplicative factor

$$\text{peeking penalty} = \exp\!\left( \sum_{t=1}^{\tau} \log \frac{p_t(\text{observed path})}{p_t(\text{conditional path})} \right),$$

which prices the anticipation of the random time.

Coalescent Interpretation and Pooling Benefit§

The partition function of the martingale is shown to have a coalescent representation: it equals the probability that two independent copies of the process share the same prefix up to a random time. This yields a natural interpretation for geometric mixtures of test martingales used in safe multi-model testing—each model's e-process contributes, but the mixture enjoys a pooling benefit that reduces the effective number of tests.

Implementation Sketch§

The identities are inherently pathwise and can be computed online. The following Python snippet illustrates how to compute the per-step Bregman divergence for the $L^p$ maximal bound and the peeking penalty for a simple binomial martingale.

import torch

p = 2.0
q = 0.5
M = torch.tensor([1.0])
M_bar = torch.tensor([1.0])
bregman_total = 0.0
peeking_penalty = 1.0

# Observed and conditional probabilities for a coin flip
p_observed = torch.tensor([0.7])   # e.g., after peeking
p_conditional = torch.tensor([0.5]) # null model

for t in range(10):
    # martingale increment (multiplicative)
    eps = torch.randn(1) * 0.1
    M = M * (1 + eps)
    M_bar = torch.maximum(M_bar, M)
    # Bregman divergence for phi(x)=x^p
    phi_grad = p * M_bar**(p-1)
    bregman = phi_grad * (M_bar - M) - (M_bar**p - M**p)
    bregman_total += bregman.item()
    # peeking penalty update
    peeking_penalty *= (p_observed / p_conditional).item()

print(f"Total Bregman deficit: {bregman_total}")
print(f"Peeking penalty: {peeking_penalty}")

This code is illustrative; the full framework applies to continuous-time processes and general filtrations.

Significance§

This work is primarily mathematical, but has direct implications for anytime-valid inference, safe multi-model testing, and for understanding the exact slack in widely used concentration inequalities. The explicit decomposition guides practitioners in choosing which bound to use based on the geometry of their martingale, and it provides a principled way to construct tighter e-processes when random stopping is involved.