Exchangeability

A sequence of random variables (Z_1, Z_2, ..., Z_n) is exchangeable if, for any permutation (\pi) of the indices ({1, ..., n}), the joint probability distribution remains identical:

(P(Z_1, ..., Z_n) = P(Z_{\pi(1)}, ..., Z_{\pi(n)}))

This means the ordering of the data points carries no information. The sequence is symmetric and the individual observations are statistically indistinguishable before observing their values.

Exchangeability is a strictly weaker condition than the independent and identically distributed (IID) assumption.

• IID implies Exchangeability: Any sequence of IID random variables is automatically exchangeable because the joint distribution factorizes into identical marginals.
• Exchangeability does not imply IID: Exchangeable sequences can exhibit dependence. A classic example is drawing balls from an urn without replacement—the draws are exchangeable but not independent.

This makes conformal prediction robust to certain types of dependencies that violate the IID assumption.

De Finetti's Theorem provides the foundational representation for infinite exchangeable sequences. It states that an infinite sequence of binary random variables is exchangeable if and only if it can be represented as a mixture of IID sequences conditioned on a latent parameter.

Formally: (P(Z_1, ..., Z_n) = \int \prod_{i=1}^n P(Z_i | \theta) dF(\theta))

This means exchangeable data can be viewed as IID data drawn from a random, unknown distribution. The theorem justifies Bayesian modeling and provides the theoretical link between exchangeability and conditional independence.

Exchangeability is the sole assumption required for the marginal coverage guarantee in split conformal prediction. The proof relies on the fact that, under exchangeability, the rank of a new test point's nonconformity score among the calibration scores is uniformly distributed.

• The calibration set and the test point must be exchangeable.
• This ensures the empirical quantile computed on the calibration set is a valid threshold for the test point.
• Violations of exchangeability, such as distribution shift or temporal drift, break this rank symmetry and invalidate the coverage guarantee.

Real-world data frequently violates exchangeability, requiring careful handling:

• Temporal Dependence: Time series data with autocorrelation breaks permutation invariance because the order encodes critical information.
• Distribution Shift: When (P_{train}(X,Y) \neq P_{test}(X,Y)), the calibration and test points are no longer drawn from the same mixture distribution.
• Spatial Correlation: Geospatial data where nearby observations are correlated violates the symmetry assumption.

Adaptive conformal inference and weighted conformal prediction are designed to provide approximate validity under these specific violations.

Statistical tests can assess whether a dataset plausibly satisfies exchangeability before applying conformal prediction:

• Permutation Tests: Directly test the null hypothesis of exchangeability by comparing a test statistic on the observed sequence to its distribution under random permutations.
• Runs Tests: Detect non-random patterns in a binary sequence that would indicate a lack of symmetry.
• Rank-Based Diagnostics: In conformal prediction, tracking the empirical coverage rate over sequential batches can reveal violations if the rate deviates systematically from the target level.

A failure to reject exchangeability does not prove it holds, but provides empirical support for the validity of the conformal guarantee.

A stronger assumption than exchangeability where data points are drawn independently from the same fixed distribution. While IID data is always exchangeable, exchangeable data need not be independent. For example, sampling without replacement from a finite population yields exchangeable but dependent draws. Standard conformal prediction requires only exchangeability, making it more broadly applicable than methods demanding strict independence.

The core statistical promise of conformal prediction: P(Y_test ∈ C(X_test)) ≥ 1 - α, where C(X_test) is the prediction set and α is the user-specified error rate. This guarantee holds exactly under the exchangeability assumption, regardless of the underlying model or data distribution. It is a marginal guarantee, meaning coverage is averaged over the randomness in both the calibration and test points.

A common violation of exchangeability where the distribution of input features P(X) changes between training and test time, while the conditional label distribution P(Y|X) remains stable. Standard conformal prediction fails under covariate shift. Weighted conformal prediction addresses this by re-weighting calibration samples using the likelihood ratio between test and training input densities to restore valid coverage.

A sequential prediction setting where data arrives in a stream and the exchangeability assumption is deliberately relaxed. Adaptive conformal inference (ACI) dynamically adjusts the quantile threshold over time in response to observed coverage errors. This maintains long-run empirical coverage without requiring the data-generating process to be stationary, making it suitable for time-series and non-stationary environments.

A technique that applies conformal calibration independently within pre-defined categories to achieve conditional coverage guarantees. Named after the painter Piet Mondrian for its grid-like partitioning of the feature space, this method ensures validity for each distinct group (e.g., each class label) by computing separate nonconformity quantiles per category, addressing the limitations of marginal-only guarantees.

An adaptation of conformal prediction to sequential data where temporal dependencies break exchangeability. Common approaches use a sliding window of the most recent observations as the calibration set, implicitly assuming local exchangeability within the window. More sophisticated methods employ sequential testing frameworks or fit explicit models of distribution drift to maintain valid prediction intervals over time.