# Testing randomness

arXiv: https://arxiv.org/abs/1906.09256 · HTML: https://mlsanity.com/paper/1906.09256/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2019.

## Built on by (most cited first, 30 of 34)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Tracking the risk of a deployed model and detecting harmful distribution shifts](https://mlsanity.com/paper/2110.06177/) (2021)
- [Retrain or not retrain: Conformal test martingales for change-point detection](https://mlsanity.com/paper/2102.10439/) (2021)
- [E-detectors: a nonparametric framework for sequential change detection](https://mlsanity.com/paper/2203.03532/) (2022)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [Martingale Methods for Sequential Estimation of Convex Functionals and Divergences](https://mlsanity.com/paper/2103.09267/) (2021)
- [WATCH: Adaptive Monitoring for AI Deployments via Weighted-Conformal Martingales](https://mlsanity.com/paper/2505.04608/) (2025)
- [Recommendation Systems with Distribution-Free Reliability Guarantees](https://mlsanity.com/paper/2207.01609/) (2022)
- [On Continuous Monitoring of Risk Violations under Unknown Shift](https://mlsanity.com/paper/2506.16416/) (2025)
- [A unified framework for bandit multiple testing](https://mlsanity.com/paper/2107.07322/) (2021)
- [Online Distribution Shift Detection via Recency Prediction](https://mlsanity.com/paper/2211.09916/) (2022)
- [Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern](https://mlsanity.com/paper/2305.11640/) (2023)
- [Theoretical guarantees for change localization using conformal p-values](https://mlsanity.com/paper/2510.08749/) (2025)
- [Conformal testing in a binary model situation](https://mlsanity.com/paper/2104.01885/) (2021)
- [Leave-One-Out-, Bootstrap- and Cross-Conformal Anomaly Detectors](https://mlsanity.com/paper/2402.16388/) (2024)
- [Testing For Distribution Shifts with Conditional Conformal Test Martingales](https://mlsanity.com/paper/2602.13848/) (2026)
- [Combining Evidence Across Filtrations](https://mlsanity.com/paper/2402.09698/) (2024)
- [Diagnostic Runtime Monitoring with Martingales](https://mlsanity.com/paper/2407.21748/) (2024)
- [Distribution-free changepoint localization after sequential change detection](https://mlsanity.com/paper/2606.01256/) (2026)
- [Protected probabilistic classification](https://mlsanity.com/paper/2107.01726/) (2021)
- [Enhancement of prediction algorithms by betting](https://mlsanity.com/paper/2105.08669/) (2021)
- [Conformal Changepoint Localization and Root Cause Analysis with Corrupted Observations](https://mlsanity.com/paper/2607.26481/) (2026)
- [CURA: Certified Runtime Alarms for Computer-Use Agents](https://mlsanity.com/paper/2608.27808/) (2026)
- [Conformal testing: binary case with Markov alternatives](https://mlsanity.com/paper/2111.01885/) (2021)
- [Efficient Learning Under Density Shift in Incremental Settings Using Cram'er-Rao-Based Regularization](https://mlsanity.com/paper/2502.12949/) (2025)
- [Adapting to Fragmented and Evolving Data: A Fisher Information Perspective](https://mlsanity.com/paper/2507.18996/) (2025)
- [Deceptive Risk Minimization: Out-of-Distribution Generalization by Deceiving Distribution Shift Detectors](https://mlsanity.com/paper/2509.12081/) (2025)
- [Detecting Object Tracking Failure via Sequential Hypothesis Testing](https://mlsanity.com/paper/2602.12983/) (2026)

## Abstract (arXiv)

The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeability, which postulates that the distribution of the observations is invariant with respect to their permutations. This paper reviews known methods of testing the two hypotheses concentrating on the online mode of testing, when the observations arrive sequentially. All known online methods for testing these hypotheses are based on conformal martingales, which are defined and studied in detail. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or the frequency of false alarms for various procedures based on conformal martingales, including conformal versions of the CUSUM and Shiryaev-Roberts procedures. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.