Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T20:57:24.417Z Has data issue: false hasContentIssue false
  • English
  • Français

Von Mises' definition of random sequences reconsidered

Published online by Cambridge University Press:  12 March 2014

Michiel van Lambalgen
Michiel van Lambalgen*
Affiliation:
Department of Philosophy, Technical University of Delft, Delft, The, Netherlands
*
Department of Mathematics, University of Amsterdam, Amsterdam, The, Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

We review briefly the attempts to define random sequences (§0). These attempts suggest two theorems: one concerning the number of subsequence selection procedures that transform a random sequence into a random sequence (§§1–3 and 5); the other concerning the relationship between definitions of randomness based on subsequence selection and those based on statistical tests (§4).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 52 , Issue 3 , September 1987 , pp. 725 - 755
Copyright
Copyright © Association for Symbolic Logic 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alekseev, V. M. and Yakobson, M. V. [1], Symbolic dynamics and hyperbolic dynamical systems, Physics Reports, vol. 75 (1981), pp. 287–325.CrossRefGoogle Scholar
Bishop, E. and Cheng, H. [1], Constructive measure theory, Memoirs of the American Mathematical Society, no. 116 (1972).Google Scholar
Brudno, A. [1], Entropy and the complexity of the trajectories of a dynamical system, Transactions of the Moscow Mathematical Society, 1983, no. 2 (44), pp. 127–151.Google Scholar
Chaitin, G. J. [1], A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery, vol. 22 (1975), pp. 329–340.CrossRefGoogle Scholar
Chaitin, G. J. [2], Algorithmic information theory, IBM Journal of Research and Development, vol. 21 (1977), pp. 350–3509.CrossRefGoogle Scholar
Church, A. [1], On the concept of a random sequence, Bulletin of the American Mathematical Society, vol. 46(1940), pp. 130–135.CrossRefGoogle Scholar
Dies, J.-E. [1], Information et complexité, Annales de l'Institut Henri Poincaré, Section B: Calcul des Probabilitiés et Statistique, Nouvelle Série, vol. 12 (1976), pp. 365–390; vol. 14 (1978), pp. 113–118.Google Scholar
Feller, W. [1], Introduction to probability theory and its applications, Vol. I, Wiley, New York, 1968.Google Scholar
Feller, W. [2], Introduction to probability theory and its applications, Vol. II, Wiley, New York, 1971.Google Scholar
Ford, J. [1], How random is a coin toss? Physics Today, vol. 36 (1983), no. 4 (04), pp. 40–47.CrossRefGoogle Scholar
Gacs, P. [1], On the relation between descriptional complexity and algorithmic probability, Theoretical Computer Science, vol. 22 (1983), pp. 71–93.CrossRefGoogle Scholar
Gaifman, H. and Snir, M. [1], Probabilities over rich languages, randomness and testing, this Journal, vol. 47(1982), pp. 495–548.Google Scholar
Kakutani, S. [1], On the equivalence of infinite product measures, Annals of Mathematics, ser. 2, vol. 49 (1948), pp. 214–224.CrossRefGoogle Scholar
Kamae, T. [1], Subsequences of normal sequences, Israel Journal of Mathematics, vol. 16 (1973), pp. 121–149.CrossRefGoogle Scholar
Kamke, E. [1], Über neuere Begründungen der Wahrscheinlichkeitsrechnung, Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 42 (1932), pp. 14–27.Google Scholar
Kechris, A. [1], Measure and category in effective descriptive set theory, Annals of Mathematical Logic, vol. 5(1973), pp. 337–384.CrossRefGoogle Scholar
Kolmogorov, A. N. [1], On tables of random numbers, Sankhyā, Series A, vol. 25 (1963), pp. 369–376.Google Scholar
Kolmogorov, A. N. [2], Combinatorial foundations of information theory and the calculus of probabilities, Russian Mathematical Surveys, vol. 38 (1983), no. 4, pp. 29–40.CrossRefGoogle Scholar
Levin, L. A. [1], On the notion of a random sequence, Soviet Mathematics Doklady, vol. 14 (1973), pp. 1414–1416.Google Scholar
Levin, L. A. [2], Various measures of complexity for finite objects, Soviet Mathematics Doklady, vol. 17 (1976), pp. 522–526.Google Scholar
Lichtenberg, A. J. and Lieberman, M. A. [1], Regular and stochastic motion, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
Martin-Löf, P. [1], The definition of random sequences, Information and Control, vol. 9 (1966), pp. 606–619.CrossRefGoogle Scholar
Martin-Löf, P. [2], Complexity oscillations in infinite binary sequences, Zeitschrift für Wahrscheinlichkeits-theorie und Verwandte Gebiete, vol. 19 (1971), pp. 225–230.CrossRefGoogle Scholar
von Mises, R. [1], Grundlagen der Wahrscheinlichkeitsrechnung, Mathematische Zeitschrift, vol. 5 (1919), pp. 52–99.CrossRefGoogle Scholar
von Mises, R. [2], Wahrscheinlichkeit, Statistik und Wahrheit, Springer-Verlag, Vienna, 1928. (The English edition, Dover, New York, 1981, is cited as [2a].)CrossRefGoogle Scholar
von Mises, R. [3] (with Geiringer, H.), Mathematical theory of probability and statistics, Academic Press, New York, 1964.Google Scholar
Oxtoby, J. C. [1], Measure and category, 2nd ed., Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
Petersen, K. [1], Ergodic theory, Cambridge University Press, Cambridge, 1983.CrossRefGoogle Scholar
Sacks, G. [1], Measure theoretic uniformity in recursion theory and set theory, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 381–424.CrossRefGoogle Scholar
Schnorr, C. P. [1], Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, Berlin, 1971.CrossRefGoogle Scholar
Schnorr, C. P. [2], Process complexity and effective random tests, Journal of Computer and System Sciences, vol. 7 (1973), pp. 376–388.CrossRefGoogle Scholar
Tornier, E. [1], Comment, Mathematische Annalen, vol. 108 (1933), p. 320.Google Scholar
Ville, J. [1], Étude critique de la notion de collectif, Gauthier-Villars, Paris, 1939.Google Scholar
Wald, A. [1], Die Widerspruchsfreiheit des Kollektivbegriffs in der Wahrscheinlichkeitsrechnung, Ergebnisse eines Mathematischen Kolloquiums, vol. 8 (1938), pp. 38–72.Google Scholar