Testing randomness

Abstract

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.

34 pages, 1 table, 4 figures

References in corpus (4)

• E-values: Calibration, combination, and applications
• The Sources of Kolmogorov's Grundbegriffe
• Plug-in martingales for testing exchangeability on-line
• Inductive Conformal Martingales for Change-Point Detection

Cited by in corpus (16)

• Testing for Outliers with Conformal p-values
• Hypothesis testing with e-values
• Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control
• Retrain or not retrain: Conformal test martingales for change-point detection
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Exchangeability, Conformal Prediction, and Rank Tests
• Conformal testing in a binary model situation
• Testing for concept shift online
• Tracking the risk of a deployed model and detecting harmful distribution shifts
• Conformal testing: binary case with Markov alternatives
• Protected probabilistic classification
• Enhancement of prediction algorithms by betting
• Leave-One-Out-, Bootstrap- and Cross-Conformal Anomaly Detectors
• Comment on Glenn Shafer's "Testing by betting"
• Sequential Monte-Carlo testing by betting
• Testing exchangeability: fork-convexity, supermartingales, and e-processes