RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


УМН, 1990, том 45, выпуск 1(271), страницы 105–162 (Mi umn4692)  

Эта публикация цитируется в 39 научных статьях (всего в 40 статьях)

Может ли (индивидуальная) последовательность нулей и единиц быть случайной?

В. А. Успенскийa, А. Л. Семёновb, А. Х. Шеньc

a Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
b Научный совет по комплексной проблеме "Кибернетика" РАН
c Институт проблем передачи информации РАН

Аннотация: Традиционная теория вероятностей не выделяет среди элементов вероятностного пространства “случайные”. Это возможно сделать лишь с использованием методов теории алгоритмов. В статье изучаются три подхода – количественный, сложностной и частотный – к определению понятия индивидуального случайного объекта. Основные результаты изложены с полными доказательствами.
Библиогр. 67 назв.

Полный текст: PDF файл (4881 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Mathematical Surveys, 1990, 45:1, 121–189

Реферативные базы данных:

MSC: 60Exx, 60Bxx, 11Y16, 68Q30, 11B68
Поступила в редакцию: 10.07.1989

Образец цитирования: В. А. Успенский, А. Л. Семёнов, А. Х. Шень, “Может ли (индивидуальная) последовательность нулей и единиц быть случайной?”, УМН, 45:1(271) (1990), 105–162; Russian Math. Surveys, 45:1 (1990), 121–189

Цитирование в формате AMSBIB
\RBibitem{UspSemShe90}
\by В.~А.~Успенский, А.~Л.~Семёнов, А.~Х.~Шень
\paper Может ли (индивидуальная) последовательность нулей и~единиц быть случайной?
\jour УМН
\yr 1990
\vol 45
\issue 1(271)
\pages 105--162
\mathnet{http://mi.mathnet.ru/umn4692}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1050929}
\zmath{https://zbmath.org/?q=an:0702.03038}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?1990RuMaS..45..121U}
\transl
\jour Russian Math. Surveys
\yr 1990
\vol 45
\issue 1
\pages 121--189
\crossref{https://doi.org/10.1070/RM1990v045n01ABEH002321}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1990EF57400004}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn4692
  • http://mi.mathnet.ru/rus/umn/v45/i1/p105

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


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

    Эта публикация цитируется в следующих статьяx:
    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  mathnet  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  mathnet  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  mathnet  crossref  mathscinet  isi  elib
    13. В. В. Вьюгин, “О неустойчивости индивидуальной эргодической теоремы”, Пробл. передачи информ., 37:2 (2001), 27–39  mathnet  mathscinet  zmath; V. V. V'yugin, “Nonrobustness Property of the Individual Ergodic Theorem”, Problems Inform. Transmission, 37:2 (2001), 108–119  crossref
    14. J.-C. Dubacq, B. Durand, E. Formenti, “Kolmogorov complexity and cellular automata classification”, Theoretical Computer Science, 259:1-2 (2001), 271  crossref
    15. В. В. Вьюгин, “Проблемы устойчивости универсальных схем сжатия информации”, Пробл. передачи информ., 39:1 (2003), 36–52  mathnet  mathscinet  zmath; V. V. V'yugin, “Problems of Robustness for Universal Coding Schemes”, Problems Inform. Transmission, 39:1 (2003), 32–46  crossref
    16. В. В. Вьюгин, В. П. Маслов, “Об экстремальных соотношениях между аддитивными функциями потерь и колмогоровской сложностью”, Пробл. передачи информ., 39:4 (2003), 71–87  mathnet  mathscinet  zmath; 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  crossref
    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. В. В. Вьюгин, В. П. Маслов, “Теоремы о концентрации для энтропии и свободной энергии”, Пробл. передачи информ., 41:2 (2005), 72–88  mathnet  mathscinet  zmath  elib; V. V. V'yugin, V. P. Maslov, “Theorems on Concentration for the Entropy of Free Energy”, Problems Inform. Transmission, 41:2 (2005), 134–149  crossref  elib
    22. В. В. Вьюгин, В. П. Маслов, “Распределение инвестиций на фондовом рынке, информационные типы и алгоритмическая сложность”, Пробл. передачи информ., 42:3 (2006), 97–108  mathnet  mathscinet  elib; 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  crossref  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. К. Ю. Горбунов, “Оценка числа элементов покрытия произвольного теста на случайность частотными тестами”, Пробл. передачи информ., 43:1 (2007), 56–66  mathnet  mathscinet  elib; 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  crossref  isi
    27. Б. Я. Рябко, “Применение методов сжатия данных для непараметрического оценивания характеристик случайных процессов с дискретным временем”, Пробл. передачи информ., 43:4 (2007), 109–123  mathnet  mathscinet  zmath  elib; 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  crossref  isi  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. Ан. А. Мучник, “Алгоритмическая случайность и разбиение супермартингалов”, Пробл. передачи информ., 45:1 (2009), 60–70  mathnet  mathscinet  zmath; An. A. Muchnik, “Algorithmic randomness and splitting of supermartingales”, Problems Inform. Transmission, 45:1 (2009), 54–64  crossref  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. В. В. Вьюгин, “Об универсальных алгоритмах адаптивного прогнозирования”, Пробл. передачи информ., 47:2 (2011), 90–116  mathnet  mathscinet; V. V. V'yugin, “On universal algorithms for adaptive forecasting”, Problems Inform. Transmission, 47:2 (2011), 166–189  crossref  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. В. А. Барвинок, В. И. Богданович, А. Н. Плотников, “К вопросу о предельном распределении серий в случайной двоичной последовательности”, Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 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. Н. Н. Григорьева, А. Ф. Ляхов, “Математический анализ эффективности сортировки сложного железнодорожного состава”, Матем. обр., 2014, № 2(70), 23–35  mathnet
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:2417
    Полный текст:900
    Литература:101
    Первая стр.:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019