General information
Latest issue
Impact factor
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Uspekhi Mat. Nauk:

Personal entry:
Save password
Forgotten password?

Uspekhi Mat. Nauk, 1990, Volume 45, Issue 1(271), Pages 105–162 (Mi umn4692)  

This article is cited in 39 scientific papers (total in 40 papers)

Can an individual sequence of zeros and ones be random?

V. A. Uspenskiia, A. L. Semenovb, A. Kh. Shen'c

a M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Science Counsil RAS on Complex Problem 'Cybernetics' RAS
c Institute for Information Transmission Problems, Russian Academy of Sciences

Full text: PDF file (4881 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 1990, 45:1, 121–189

Bibliographic databases:

MSC: 60Exx, 60Bxx, 11Y16, 68Q30, 11B68
Received: 10.07.1989

Citation: V. A. Uspenskii, A. L. Semenov, A. Kh. Shen', “Can an individual sequence of zeros and ones be random?”, Uspekhi Mat. Nauk, 45:1(271) (1990), 105–162; Russian Math. Surveys, 45:1 (1990), 121–189

Citation in format AMSBIB
\by V.~A.~Uspenskii, A.~L.~Semenov, A.~Kh.~Shen'
\paper Can an individual sequence of zeros and ones be random?
\jour Uspekhi Mat. Nauk
\yr 1990
\vol 45
\issue 1(271)
\pages 105--162
\jour Russian Math. Surveys
\yr 1990
\vol 45
\issue 1
\pages 121--189

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Jack H. Lutz, “Almost everywhere high nonuniform complexity”, Journal of Computer and System Sciences, 44:2 (1992), 220  crossref
    2. Homer S. White, “Algorithmic complexity of points in dynamical systems”, Ergod Th Dynam Sys, 13:4 (1993)  crossref  mathscinet  zmath
    3. Jack H. Lutz, Elvira Mayordomo, “Measure, Stochasticity, and the Density of Hard Languages”, SIAM J Comput, 23:4 (1994), 762  crossref  mathscinet  zmath  isi
    4. V. A. Uspensky, A. Shen, “Relations between varieties of kolmogorov complexities”, Math Systems Theory, 29:3 (1996), 271  crossref  mathscinet  zmath  isi  elib
    5. Tyll Krüger, Serge Troubetzkoy, “Complexity, randomness, discretization: Some remarks on a program of J. Ford”, Physica D: Nonlinear Phenomena, 105:1-3 (1997), 97  crossref
    6. V. V. V'yugin, “On the Longest Head-Run in an Individual Random Sequence”, Theory Probab Appl, 42:3 (1998), 541  crossref  mathscinet  isi
    7. V. V. V'yugin, “Effective Convergence in Probability and an Ergodic Theorem forIndividual Random Sequences”, Theory Probab Appl, 42:1 (1998), 39  crossref  mathscinet  isi
    8. V.V. V'yugin, “Ergodic theorems for individual random sequences”, Theoretical Computer Science, 207:2 (1998), 343  crossref
    9. V.V. V'yugin, “Non-stochastic infinite and finite sequences”, Theoretical Computer Science, 207:2 (1998), 363  crossref
    10. Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky, “Mathematical metaphysics of randomness”, Theoretical Computer Science, 207:2 (1998), 263  crossref
    11. Jack H. Lutz, David L. Schweizer, “Feasible reductions to kolmogorov-loveland stochastic sequences”, Theoretical Computer Science, 225:1-2 (1999), 185  crossref
    12. M. Minozzo, “Purely Game-theoretic Random Sequences: I. Strong Law of Large Numbers and Law of the Iterated Logarithm”, Theory Probab Appl, 44:3 (2000), 511  crossref  mathscinet  isi  elib
    13. V. V. V'yugin, “Nonrobustness Property of the Individual Ergodic Theorem”, Problems Inform. Transmission, 37:2 (2001), 108–119  mathnet  crossref  mathscinet  zmath
    14. J.-C. Dubacq, B. Durand, E. Formenti, “Kolmogorov complexity and cellular automata classification”, Theoretical Computer Science, 259:1-2 (2001), 271  crossref
    15. V. V. V'yugin, “Problems of Robustness for Universal Coding Schemes”, Problems Inform. Transmission, 39:1 (2003), 32–46  mathnet  crossref  mathscinet  zmath
    16. V. V. V'yugin, V. P. Maslov, “On Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity”, Problems Inform. Transmission, 39:4 (2003), 380–394  mathnet  crossref  mathscinet  zmath
    17. An. Muchnik, A. Semenov, M. Ushakov, “Almost periodic sequences”, Theoretical Computer Science, 304:1-3 (2003), 1  crossref
    18. Bruno Durand, Vladimir Kanovei, Vladimir A. Uspensky, Nikolai Vereshchagin, “Do stronger definitions of randomness exist?”, Theoretical Computer Science, 290:3 (2003), 1987  crossref
    19. Wolfgang Merkle, “The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences”, J. symb. log, 68:04 (2003), 1362  crossref
    20. A.B. Nobel, “Some Stochastic Properties of Memoryless Individual Sequences”, IEEE Trans Inform Theory, 50:7 (2004), 1497  crossref  mathscinet  isi  elib
    21. V. V. V'yugin, V. P. Maslov, “Theorems on Concentration for the Entropy of Free Energy”, Problems Inform. Transmission, 41:2 (2005), 134–149  mathnet  crossref  mathscinet  zmath  elib  elib
    22. V. V. V'yugin, V. P. Maslov, “Distribution of Investments in the Stock Market, Information Types, and Algorithmic Complexity”, Problems Inform. Transmission, 42:3 (2006), 251–261  mathnet  crossref  mathscinet  elib  elib
    23. Boris Ryabko, Jaakko Astola, Alex Gammerman, “Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series”, Theoretical Computer Science, 359:1-3 (2006), 440  crossref
    24. Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank Stephan, “Kolmogorov–Loveland randomness and stochasticity”, Annals of Pure and Applied Logic, 138:1-3 (2006), 183  crossref
    25. Fabio Benatti, “Entropy and algorithmic complexity in quantum information theory”, Nat Comput, 6:2 (2007), 133  crossref  mathscinet  zmath
    26. K. Yu. Gorbunov, “Estimation of the Number of Elements in a Covering of an Arbitrary Randomness Test by Frequency Tests”, Problems Inform. Transmission, 43:1 (2007), 48–56  mathnet  crossref  mathscinet  isi  elib
    27. B. Ya. Ryabko, “Application of Data Compression Methods to Nonparametric Estimation of Characteristics of Discrete-Time Stochastic Processes”, Problems Inform. Transmission, 43:4 (2007), 367–379  mathnet  crossref  mathscinet  zmath  isi  elib  elib
    28. Hayato Takahashi, “On a definition of random sequences with respect to conditional probability”, Information and Computation, 206:12 (2008), 1375  crossref
    29. Ludwig Staiger, “On Oscillation-free ε-random Sequences”, Electronic Notes in Theoretical Computer Science, 221 (2008), 287  crossref
    30. A. A. Muchnik, “Algorithmic randomness and splitting of supermartingales”, Problems Inform. Transmission, 45:1 (2009), 54–64  mathnet  crossref  mathscinet  zmath  isi
    31. Vladimir V. V’yugin, “On calibration error of randomized forecasting algorithms”, Theoretical Computer Science, 410:19 (2009), 1781  crossref
    32. Fabio Benatti, “Quantum Algorithmic Complexities and Entropy”, Open Syst. Inf. Dyn, 16:01 (2009), 1  crossref
    33. V. V. V'yugin, “On universal algorithms for adaptive forecasting”, Problems Inform. Transmission, 47:2 (2011), 166–189  mathnet  crossref  mathscinet  isi
    34. Boris Ryabko, Daniil Ryabko, “Constructing perfect steganographic systems”, Information and Computation, 209:9 (2011), 1223  crossref
    35. Hayato Takahashi, “Algorithmic randomness and monotone complexity on product space”, Information and Computation, 209:2 (2011), 183  crossref
    36. Joel Ratsaby, “An empirical study of the complexity and randomness of prediction error sequences”, Communications in Nonlinear Science and Numerical Simulation, 16:7 (2011), 2832  crossref
    37. Uspensky V.A., V'yugin V.V., “Development of the algorithmic information theory in Russia”, Journal of Communications Technology and Electronics, 56:6 (2011), 739–747  crossref  isi
    38. V. A. Barvinok, V. I. Bogdanovich, A. N. Plotnikov, “K voprosu o predelnom raspredelenii serii v sluchainoi dvoichnoi posledovatelnosti”, Vestn. Sam. gos. tekhn. un-ta. Ser. Fiz.-mat. nauki, 4(29) (2012), 56–71  mathnet  crossref
    39. O. V. Usatenko, S. S. Melnik, S. S. Apostolov, N. M. Makarov, A. A. Krokhin, “Iterative method for generating correlated binary sequences”, Phys. Rev. E, 90:5 (2014)  crossref
    40. N. N. Grigoreva, A. F. Lyakhov, “Matematicheskii analiz effektivnosti sortirovki slozhnogo zheleznodorozhnogo sostava”, Matem. obr., 2014, no. 2(70), 23–35  mathnet
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:2117
    Full text:779
    First page:8

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018