Testing randomness online. (English) Zbl 07473938

Summary: 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. An important variety of online testing is change detection, where the use of conformal martingales leads to conformal versions of the CUSUM and Shiryaev-Roberts procedures; these versions work in the nonparametric setting where the data is assumed IID according to a completely unknown distribution before the change. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or, in the case of change detection, the frequency of false alarms for various procedures based on conformal martingales. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.


62-XX Statistics


Azure; UCI-ml
Full Text: DOI arXiv


[1] Balasubramanian, V. N., Ho, S.-S. and Vovk, V., eds. (2014). Conformal Prediction for Reliable Machine Learning: Theory, Adaptations, and Applications. Elsevier, Amsterdam. · Zbl 1290.68003
[2] Bartels, R. (1982). The rank version of von Neumann’s ratio test for randomness. J. Amer. Statist. Assoc. 77 40-46. · Zbl 0482.62032
[3] Bernoulli, J. (1713). Ars Conjectandi. Thurnisius, Basel.
[4] Bhattacharya, P. K. (1994). Some aspects of change-point analysis. In Change-Point Problems (South Hadley, MA, 1992). Institute of Mathematical Statistics Lecture Notes—Monograph Series 23 28-56. IMS, Hayward, CA. · Zbl 1157.62331 · doi:10.1214/lnms/1215463112
[5] Caeiro, F. and Mateus, A. (2014). An R implementation of several randomness tests. AIP Conf. Proc. 1618 531-534.
[6] Cournot, A.-A. (1843). Exposition de la Théorie des Chances et des Probabilités. Hachette, Paris. · Zbl 0174.51702
[7] Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley Interscience, Hoboken, NJ. · Zbl 1140.94001
[8] Doob, J. L. (1953). Stochastic Processes. Wiley, New York. · Zbl 0053.26802
[9] Du, W., Polunchenko, A. S. and Sokolov, G. (2017). On robustness of the Shiryaev-Roberts change-point detection procedure under parameter misspecification in the post-change distribution. Comm. Statist. Simulation Comput. 46 2185-2206. · Zbl 1364.62214 · doi:10.1080/03610918.2015.1039131
[10] Dua, D. and Graff, C. UCI machine learning repository (2020). The \[\mathtt{Absenteeism}\mathtt{at}\mathtt{work}\] dataset was donated by Andrea Martiniano, Ricardo Pinto Ferreira, and Renato Jose Sassi.
[11] Fedorova, V., Nouretdinov, I., Gammerman, A. and Vovk, V. (2012). Plug-in martingales for testing exchangeability on-line. In Proceedings of the Twenty Ninth International Conference on Machine Learning (J. Langford and J. Pineau, eds.) 1639-1646. Omnipress, Helsinki.
[12] Grünwald, P., de Heide, R. and Koolen, W. M. (2020). Safe testing. Technical report. Available at arXiv:1906.07801 [math.ST].
[13] Herbster, M. and Warmuth, M. K. (1998). Tracking the best expert. Mach. Learn. 32 151-178. · Zbl 0912.68165
[14] Ho, S.-S. and Wechsler, H. (2010). A martingale framework for detecting changes in data streams by testing exchangeability. IEEE Trans. Pattern Anal. Mach. Intell. 32 2113-2127.
[15] Jeffreys, H. (1961). Theory of Probability, 3rd ed. Clarendon Press, Oxford. · Zbl 0116.34904
[16] Kelly, J. L. Jr. (1956). A new interpretation of information rate. Bell Syst. Tech. J. 35 917-926. · doi:10.1002/j.1538-7305.1956.tb03809.x
[17] Keysers, D. M. (2000). Approaches to invariant image object recognition. Master’s thesis, Lehrstuhl für Informatik VI, Mathematisch-Naturwissenschaftliche Fakultät, Rheinisch-Westfälische Technische Hochschule Aachen, Aachen, Germany.
[18] Kolmogoroff, A. (1933). Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer, Berlin. English translation: Foundations of the Theory of Probability. Chelsea, New York, 1950.
[19] Kolmogorov, A. N. (1963). On tables of random numbers. Sankhyā Ser. A 25 369-376. · Zbl 0126.33203
[20] Kolmogorov, A. N. (1965). Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1 1-7. · Zbl 0271.94018
[21] Kolmogorov, A. N. (1968). Logical basis for information theory and probability theory. IEEE Trans. Inf. Theory IT-14 662-664. · Zbl 0167.47601 · doi:10.1109/tit.1968.1054210
[22] Kolmogorov, A. N. (1983). Combinatorial foundations of information theory and the calculus of probabilities. Russian Math. Surveys 38 29-40. · Zbl 0597.60002
[23] Kolmogorov, A. N. and Shiryaev, A. N. (1960). Применение марковских прощессов к обнаружению разлащок произвощственного прощесса. Доклащ на VI Совещании по теории вероятностей и математической статистике, Vilnius.
[24] Lehmann, E. L. (1975). Nonparametrics: Statistical Methods Based on Ranks. Holden-Day, Inc., San Francisco, CA. · Zbl 0354.62038
[25] Lehmann, E. L. and Romano, J. P. (2005). Testing Statistical Hypotheses, 3rd ed. Springer Texts in Statistics. Springer, New York. · Zbl 1076.62018
[26] Martin-Löf, P. (1966). The definition of random sequences. Inf. Control 9 602-619. · Zbl 0244.62008
[27] McDonald, D. (1990). A cusum procedure based on sequential ranks. Naval Res. Logist. 37 627-646. · Zbl 0722.62064
[28] Page, E. S. (1954). Continuous inspection schemes. Biometrika 41 100-115. · Zbl 0056.38002 · doi:10.1093/biomet/41.1-2.100
[29] Pollak, M. (1987). Average run lengths of an optimal method of detecting a change in distribution. Ann. Statist. 15 749-779. · Zbl 0632.62080 · doi:10.1214/aos/1176350373
[30] Poor, H. V. and Hadjiliadis, O. (2009). Quickest Detection. Cambridge Univ. Press, Cambridge. · Zbl 1271.62015
[31] Popper, K. R. (1982). The Open Universe. Hutchinson, London.
[32] Robbins, H. (1955). A remark on Stirling’s formula. Amer. Math. Monthly 62 26-29. · Zbl 0068.05404 · doi:10.2307/2308012
[33] Roberts, S. W. (1966). A comparison of some control chart procedures. Technometrics 8 411-430. · doi:10.2307/1266688
[34] Schervish, M. J. (1995). Theory of Statistics. Springer Series in Statistics. Springer, New York. · Zbl 0834.62002 · doi:10.1007/978-1-4612-4250-5
[35] Shafer, G. (2019). The language of betting as a strategy for statistical and scientific communication (with discussion). J. R. Stat. Soc. Ser. A. To appear. Available at arXiv:1903.06991 [math.ST].
[36] Shafer, G. and Vovk, V. (2006). The sources of Kolmogorov’s Grundbegriffe. Statist. Sci. 21 70-98. · Zbl 1426.01011 · doi:10.1214/088342305000000467
[37] Shafer, G. and Vovk, V. (2019). Game-Theoretic Foundations for Probability and Finance. Wiley, Hoboken, NJ. · Zbl 1422.91026
[38] Shewhart, W. A. (1931). Economic Control of Quality of Manufactured Product. Van Nostrand, New York.
[39] Shiryaev, A. N. (1963). Optimal methods in quickest detection problems. Theory Probab. Appl. 8 22-46. · Zbl 0213.43804
[40] Shiryaev, A. N. (2010). Quickest detection problems: Fifty years later. Sequential Anal. 29 345-385. · Zbl 1203.62137 · doi:10.1080/07474946.2010.520580
[41] Shiryaev, A. N. (2019). Probability-2, 3rd ed. Graduate Texts in Mathematics 95. Springer, New York. · Zbl 1472.60001
[42] Shiryaev, A. N. (2019). Stochastic Disorder Problems. Probability Theory and Stochastic Modelling 93. Springer, Cham. · Zbl 1426.93002 · doi:10.1007/978-3-030-01526-8
[43] Siegmund, D., Yakir, B. and Zhang, N. R. (2011). Detecting simultaneous variant intervals in aligned sequences. Ann. Appl. Stat. 5 645-668. · Zbl 1223.62166 · doi:10.1214/10-AOAS400
[44] Simard, P., LeCun, Y. and Denker, J. (1993). Efficient pattern recognition using a new transformation distance. Adv. Neural Inf. Process. Syst. 5 50-58.
[45] van Erven, T., Grünwald, P., de Rooij, S. and Jandhyala, V. K. (2012). Catching up faster by switching sooner: A predictive approach to adaptive estimation with an application to the AIC-BIC dilemma (with discussion). J. R. Stat. Soc. Ser. B 74 361-417. · Zbl 1411.62073 · doi:10.1111/j.1467-9868.2011.01025.x
[46] Ville, J. (1939). Étude Critique de la Notion de Collectif. Gauthier-Villars, Paris. · Zbl 0021.14505
[47] Volkhonskiy, D., Burnaev, E., Nouretdinov, I., Gammerman, A. and Vovk, V. (2017). Inductive conformal martingales for change-point detection. Proc. Mach. Learn. Res. 60 132-153. COPA 2017.
[48] von Mises, R. (1919). Grundlagen der Wahrscheinlichkeitsrechnung. Math. Z. 5 52-99. · doi:10.1007/BF01203155
[49] Vovk, V. (1986). On the concept of the Bernoulli property. Russian Math. Surveys 41 247-248. Russian original: О понятии бернуллиевости. Another English translation with proofs: arXiv:1612.08859 [math.ST], December 2016. · Zbl 0624.60022
[50] Vovk, V. (2021). Supplement to “Testing randomness online.” https://doi.org/10.1214/20-STS817SUPP
[51] Vovk, V., Gammerman, A. and Shafer, G. (2005). Algorithmic Learning in a Random World. Springer, New York. · Zbl 1105.68052
[52] Vovk, V. and Wang, R. (2020). Combining \(p\)-values via averaging. Biometrika 107 791-808. · Zbl 1457.62078 · doi:10.1093/biomet/asaa027
[53] Vovk, V. and Wang, R. (2020). E-values: Calibration, combination, and applications. Ann. Statist. To appear. Available at arXiv:1912.06116 [math.ST]. · Zbl 1475.62087
[54] Vovk, V. G. and V’yugin, V. V. (1993). On the empirical validity of the Bayesian method. J. Roy. Statist. Soc. Ser. B 55 253-266. · Zbl 0788.62006
[55] Wald, A. (1945). Sequential tests of statistical hypotheses. Ann. Math. Stat. 16 117-186. · Zbl 0060.30207 · doi:10.1214/aoms/1177731118
[56] Wald, A. (1947). Sequential Analysis. Wiley, New York. · Zbl 0029.15805
[57] Wald, A. and Wolfowitz, J. (1943). An exact test for randomness in the non-parametric case based on serial correlation. Ann. Math. Stat. 14 378-388. · Zbl 0060.30206 · doi:10.1214/aoms/1177731358
[58] Wald, A. and Wolfowitz, J. (1948). Optimum character of the sequential probability ratio test. Ann. Math. Stat. 19 326-339. · Zbl 0032.17302 · doi:10.1214/aoms/1177730197
[59] Zhang, X., Lu, P., Martens, J., Ericson, G. and Sharkey, K. (2020). Time Series Anomaly Detection Module in Microsoft Azure. Microsoft, Seattle, WA. Online documentation
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.