📊 statistics

Betting on Moments: Legendre Jumper Martingales for Online Exchangeability Testing

This paper introduces a family of conformal test martingales based on shifted Legendre polynomials that extend the Simple Jumper to detect higher-order distributional deviations, offering scalable variants like the Variational and Composite Legendre Jumpers to overcome computational costs and adapt to unknown shift timescales in online exchangeability testing.

Original authors: Johan Hallberg Szabadváry

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johan Hallberg Szabadváry

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out if a stream of data is behaving "normally" or if something suspicious is happening. In statistics, this "normal" behavior is called exchangeability. It basically means the data is a fair, random shuffle where the future looks just like the past. If the data starts acting weird (maybe the numbers suddenly get more spread out, or they start clustering in weird spots), your detective job is to spot that change as quickly as possible.

The paper introduces a new family of "detective tools" called Legendre Jumper Martingales. Think of these as betting machines that accumulate "wealth" (evidence) whenever the data breaks the rules of randomness.

Here is a breakdown of how they work, using simple analogies:

1. The Old Detective: The "Simple Jumper"

Before this paper, the best tool was the Simple Jumper. Imagine this detective has a very simple strategy: they only bet on whether the average number is too high or too low.

The Problem: If the data stays centered around the same average but suddenly becomes chaotic (the numbers jump wildly up and down, or they get squished into the middle), this detective misses it completely. They are like a security guard who only checks if someone is wearing a red hat, but ignores if they are running around screaming.

2. The New Detective: The "Simple Legendre Jumper"

The authors upgraded the detective by giving them a more sophisticated set of eyes. Instead of just looking at the average, they can now look at the shape of the data.

The Analogy: Imagine the data is a pile of sand. The old detective only checked if the pile was too tall or too short. The new detective can also check if the pile is too wide (variance), if it's leaning to one side (skewness), or if it has weird bumps (kurtosis).
How it works: They use special mathematical shapes called Legendre Polynomials. Think of these as different "lenses" or "filters." One lens looks for wide spreads, another for leaning piles, and so on. By betting on these shapes, the detective can catch changes the old one missed.

3. The "All-in-One" Detective: The "Product Legendre Jumper"

What if the data is doing everything wrong at once? It's chaotic, leaning, and bumpy all at the same time?

The Idea: The authors created a detective that bets on all these shapes simultaneously. It combines the lenses into one super-powerful tool.
The Catch (The "Jumping Tax"): To do this, the detective has to keep track of every possible combination of shapes at once. If you have 5 different shapes to check, the number of combinations explodes. It's like trying to remember every possible outfit combination for 5 different people at once. The detective gets so bogged down trying to check every single possibility that they move very slowly. The authors call this the "Jumping Tax"—you pay a heavy price in speed and memory to get this power.

4. The Smart Detective: The "Variational Legendre Jumper"

To fix the "Jumping Tax," the authors invented a smarter way to think.

The Analogy: Instead of one giant detective trying to remember every outfit combination, imagine a team of specialists. One person watches the width, another watches the lean, and another watches the bumps. They work independently but share their findings to make a final decision.
The Result: This team (the Variational Legendre Jumper) is almost as powerful as the giant "All-in-One" detective but runs incredibly fast. It cuts the memory cost from "exponential" (impossible for big problems) to "linear" (easy to handle). It's like swapping a supercomputer that crashes for a sleek laptop that gets the job done.

5. The Safety Net: The "Composite Legendre Jumper"

In the real world, you never know how fast the data is going to change. Sometimes it changes instantly; sometimes it drifts slowly.

The Problem: If you set your detective to move fast, they might get confused by slow changes. If you set them to move slow, they might miss a sudden crash.
The Solution: The Composite Legendre Jumper is like hiring a whole squad of detectives, each with a different speed setting. They all bet together, and the system automatically leans on the ones that are working best at that moment.
The Bonus: This squad also has a "wealth floor." Even if the data is perfectly normal and no one is making money, the system guarantees you don't lose everything. It ensures you always have a safety net.

What Did They Find?

The authors tested these tools on a real-world dataset about wine quality (red vs. white wines).

The Result: When the data was shuffled randomly (normal), all tools stayed calm. But when the data was sorted by wine type (creating a sudden shift), the new tools (especially the Variational and Composite versions) caught the change much faster and stronger than the old "Simple Jumper."
The Winner: The Composite Legendre Jumper is recommended as the "default" choice. It's the Swiss Army Knife of the group: it handles unknown speeds, catches complex changes, and never lets you go broke.

In short: The paper gives us better tools to spot when data stops behaving randomly. They made these tools smarter (checking for complex patterns), faster (avoiding the "tax" of too many combinations), and safer (guaranteeing a minimum score), making them much better at catching real-world data shifts.

Technical Summary: Betting on Moments – Legendre Jumper Martingales for Online Exchangeability Testing

Problem Statement

In conformal prediction, the validity of prediction sets relies on the assumption of exchangeability, which implies that the sequence of p-values generated by a conformal transducer is independent and identically distributed (IID) according to a uniform distribution on $[0, 1]$ . Violations of this assumption indicate distributional shifts.

While conformal test martingales (CTMs) are used to test for exchangeability online, the standard Simple Jumper (SJ) martingale (Vovk et al., 2022) has a critical limitation: it employs a linear betting function based on the first-degree shifted Legendre polynomial. Consequently, the SJ is geometrically constrained to detecting shifts in the mean (location) of the p-values. It fails to accumulate significant wealth when the distribution shift preserves the mean but alters higher-order moments, such as variance, skewness, or kurtosis. Furthermore, attempts to combine multiple betting strategies often suffer from the "jumping tax," where capital is diluted across an exponentially growing state space, severely hindering detection speed.

Methodology

The paper proposes a family of conformal test martingales based on shifted Legendre polynomials ( $\tilde{P}_k$ ), which are orthogonal on the interval $[0, 1]$ . These polynomials serve as the basis for betting functions capable of detecting deviations in specific moments of the p-value distribution.

1. Simple Legendre Jumper (SLJ)

The SLJ generalizes the Simple Jumper by replacing the linear betting function with a shifted Legendre polynomial of arbitrary degree $k$ :
$f^{(k)}_\epsilon(p) = 1 + \epsilon \tilde{P}_k(p)$
where $\epsilon$ is a parameter selected from a discrete grid.

Mechanism: For $k=1$ , it recovers the standard SJ (detecting mean shifts). For $k=2$ , it detects variance changes; for $k=3$ , skewness; and so on.
Limitation: Betting exclusively on a single degree $k$ causes the martingale to miss dominant shifts in other moments, leading to suboptimal evidence accumulation.

2. Product Legendre Jumper (PLJ)

To capture complex, multimodal deviations simultaneously, the PLJ combines betting functions of multiple degrees $K$ into a single product:
$f^K_\epsilon(p) = \frac{\prod_{k \in K} (1 + \epsilon_k \tilde{P}_k(p))}{Z(\epsilon)}$
where $Z(\epsilon)$ is a normalization constant required for $|K| \ge 3$ to ensure the integral of the betting function equals 1.

The "Jumping Tax": The PLJ maintains a Markov chain over the joint state space $\mathcal{E} = \prod_{k \in K} \mathcal{E}_k$ . As the number of degrees $|K|$ increases, the state space size grows exponentially ( $|\mathcal{E}| = g^{|K|}$ ). The "jumping tax" refers to the dilution of capital: when the environment shifts, the jumping mechanism distributes new capital uniformly across this massive state space, delaying the concentration of wealth on the optimal betting strategy.

3. Variational Legendre Jumper (VLJ)

To resolve the exponential scaling of the PLJ, the authors introduce the Variational Legendre Jumper, inspired by mean-field approximations in variational inference.

Decoupling: Instead of a single Markov chain over the product space, the VLJ runs $|K|$ independent sub-jumpers (one for each degree $k \in K$ ).
Consensus: At each step, the VLJ computes a consensus parameter $\bar{\epsilon}_k$ for each degree based on the wealth-weighted mean of the sub-jumper's state.
Global Bet: The global martingale updates using the normalized product of the betting functions evaluated at these consensus parameters.
Complexity: This reduces the computational cost from exponential $O(g^{|K|})$ to linear $O(|K| \cdot g)$ , making high-order moment testing computationally feasible with minimal loss in statistical power.

4. Composite Legendre Jumper

Following the framework of Vovk et al. (2022), the Composite Legendre Jumper averages the base martingale (SLJ, PLJ, or VLJ) over a grid of jumping rates $J \in \{10^{-4}, \dots, 1\}$ .

Robustness: This ensures robustness when the timescale of the distributional shift is unknown.
Wealth Floor: The inclusion of $J=1$ guarantees that the martingale never drops below $1/|\mathcal{E}|$ , providing an absolute wealth floor under exchangeability that fixed-rate variants lack.

Key Contributions

Generalization of Betting Functions: The introduction of the Simple Legendre Jumper, which extends the linear betting function of the Simple Jumper to arbitrary-degree shifted Legendre polynomials, enabling the detection of variance, skewness, and higher-order moment deviations.
Addressing the Jumping Tax: The development of the Product Legendre Jumper to capture joint deviations, followed by the Variational Legendre Jumper, which factorizes the joint adaptation problem via mean-field approximation. This successfully reduces the state space scaling from exponential to linear while maintaining statistical power.
Composite Robustness: The integration of these methods into a Composite Legendre Jumper, which mixes over jumping rates to provide automatic adaptation to unknown shift timescales and a guaranteed wealth floor.
Empirical Validation: Demonstration on a real-world classification task (Wine Quality dataset) showing that combined methods (PLJ and VLJ) consistently outperform single-degree martingales under distributional shifts, while the variational approximation incurs negligible loss compared to the exact product.

Results

The authors evaluated the proposed methods on the Wine Quality dataset using a conformal nearest-neighbor classifier under four data orderings: shuffled (exchangeable), abrupt change-points (Red $\to$ White, White $\to$ Red), and original order.

Exchangeability: Under shuffled data, all martingales remained near zero or declined slightly, confirming they do not raise false alarms.
Distributional Shift: Under non-exchangeable orderings, the Product and Variational Legendre Jumpers with $K=\{1, 2, 3\}$ consistently achieved the highest final log-martingale values, outperforming the single-degree Simple Legendre Jumper ( $k=1$ ) by 30%–60% in log-scale evidence.
Single-Degree Failure: Martingales betting exclusively on variance ( $k=2$ ) or skewness ( $k=3$ ) performed poorly when the shift involved multiple moments, accumulating orders of magnitude less evidence than the combined approaches.
Efficiency vs. Power: The Variational Legendre Jumper (VLJ) matched the performance of the Product Legendre Jumper (PLJ) almost exactly but required significantly fewer states (e.g., 15 states vs. 125 states for $K=\{1, 2, 3\}$ ).
Composite Superiority: The Composite Legendre Jumper decisively outperformed fixed-rate variants under distributional shifts (e.g., reaching $\log_{10} M_n \approx 100$ vs. fixed-rate $\approx 90$ ) and prevented the slow accumulation of losses seen in fixed-rate martingales under exchangeability.

Significance and Claims

The paper claims that the Composite Legendre Jumper should be the default choice for practitioners when the timescale of distributional shifts is unknown. It offers a robust solution that:

Detects complex, multimodal deviations from uniformity that linear betting functions miss.
Avoids the "curse of dimensionality" associated with joint betting strategies through variational factorization.
Provides a theoretical and practical wealth floor, ensuring stability under the null hypothesis.

The authors note that while the variational approximation performs empirically on par with the exact product, the theoretical bounds on the loss of statistical power due to mean-field factorization remain an open problem. They also suggest that future work could explore data-driven selection of polynomial degrees (analogous to Ledwina's approach for Neyman's smooth test) to further optimize efficiency. The implementation is available in the Python package online-cp.