Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску

Концепция случайной последовательности имеет важное значение в теории вероятностей и статистике . Концепция в целом опирается на понятие последовательности из случайных величин и многих статистических дискуссий начинаются со слов «пусть X 1 , ..., X п независимые случайные величины ...». Тем не менее, как заявил Д.Х. Лемер в 1951 году: «Случайная последовательность - это расплывчатое понятие ... в котором каждый член непредсказуем для непосвященных и чьи цифры проходят определенное количество тестов, традиционных для статистиков». [1]

Аксиоматическая теория вероятностей намеренно избегает определения случайной последовательности. [2] Традиционная теория вероятностей не утверждает, является ли конкретная последовательность случайной, но обычно переходит к обсуждению свойств случайных величин и стохастических последовательностей, предполагая некоторое определение случайности. Школа Бурбаки считала высказывание «рассмотрим случайную последовательность» злоупотреблением языком . [3]

Ранняя история

Эмиль Борель был одним из первых математиков, которые официально рассмотрели случайность в 1909 году. [4] В 1919 году Ричард фон Мизес дал первое определение алгоритмической случайности, которое было вдохновлено законом больших чисел, хотя он использовал термин коллективный, а не случайный. последовательность. Используя концепцию невозможности игровой системы , фон Мизес определил бесконечную последовательность нулей и единиц как случайную, если она не подвержена смещению из-за свойства стабильности частоты, то есть частота нулей стремится к 1/2, а каждую подпоследовательность мы выбор из него "правильным" методом отбора тоже не предвзят. [5]

Критерий выбора подпоследовательности, наложенный фон Мизесом, важен, потому что, хотя 0101010101 ... не является смещенным, выбирая нечетные позиции, мы получаем 000000 ... что не случайно. Фон Мизес никогда полностью не формализовал свое определение правильного правила выбора для подпоследовательностей, но в 1940 году Алонзо Черч определил его как любую рекурсивную функцию, которая, прочитав первые N элементов последовательности, решает, хочет ли она выбрать элемент с номером  N  + 1. Черч был пионером в области вычислимых функций, и его определение опиралось на тезис Черча Тьюринга о вычислимости. [6] Это определение часто называют случайностью Мизеса – Черча .

Современные подходы

В течение 20 века были разработаны различные технические подходы к определению случайных последовательностей, и теперь можно выделить три различных парадигмы. В середине 1960-х годов А. Н. Колмогоров и Д. В. Лавленд независимо друг от друга предложили более разрешительное правило отбора. [7] [8] По их мнению, определение рекурсивной функции Черча было слишком ограничительным, поскольку оно читало элементы по порядку. Вместо этого они предложили правило, основанное на частично вычислимом процессе, который, прочитав любые N элементов последовательности, решает, хочет ли он выбрать другой элемент, который еще не был прочитан. Это определение часто называют стохастичностью Колмогорова – Ловленда . Но этот метод посчитали слишком слабым.Александр Шен, который показал, что существует стохастическая последовательность Колмогорова – Ловленда, которая не соответствует общему понятию случайности.

В 1966 году Пер Мартин-Лёф представил новое понятие, которое теперь обычно считается наиболее удовлетворительным понятием алгоритмической случайности . Его первоначальное определение касалось теории меры, но позже было показано, что ее можно выразить в терминах колмогоровской сложности . Колмогоровское определение случайной строки заключалось в том, что она является случайной, если не имеет описания короче, чем она сама, через универсальную машину Тьюринга . [9]

В настоящее время возникли три основные парадигмы работы со случайными последовательностями: [10]

  • Частота / мера теоретико- подход. Этот подход начался с работы Ричарда фон Мизеса и Алонсо Черча. В 1960-х годах Пер Мартин-Лёф заметил, что множества, кодирующие такие основанные на частотах стохастические свойства, представляют собой особый вид множеств с нулевой мерой , и что более общее и плавное определение может быть получено путем рассмотрения всех эффективно измеряемых нулевых множеств.
  • Сложность / сжимаемости подход. Эту парадигму отстаивал А. Н. Колмогоров, а также вклад Леонида Левина и Григория Чайтина . Для конечных последовательностей Колмогоров определяет случайность двоичной строки длины n как энтропию (или сложность Колмогорова ), нормированную на длину n . Другими словами, если колмогоровская сложность строки близка к n , она очень случайна; если сложность намного меньше n , это не так уж и случайно. Двойная концепция случайности - это сжимаемость: чем более случайна последовательность, тем менее сжимаема и наоборот.
  • Прогнозируемость подход. Эта парадигма принадлежит Клаусу П. Шнорру и использует несколько иное определение конструктивных мартингалов, чем мартингалы, используемые в традиционной теории вероятностей. [11] Шнорр показал, как существование избирательной стратегии ставок подразумевает существование правила отбора для смещенной подпоследовательности. Если для успеха в последовательности требуется только рекурсивный мартингейл, а не для конструктивного успеха в последовательности, тогда возникает концепция рекурсивной случайности. [ требуется дальнейшее объяснение ] Юнгге Ван показал [12] [13], что концепция рекурсивной случайности отличается от концепции случайности Шнорра.[ требуется дальнейшее объяснение ]

В большинстве случаев доказаны теоремы, связывающие три парадигмы (часто эквивалентность). [14]

См. Также

Ссылки

Примечания

  1. ^ «Что означает слово« Случайный »в математике и здравом смысле » Филиппа Дж. Дэвиса, 2006 г. ISBN  1-56881-270-1, страницы 180-182
  2. ^ Неизбежная случайность в дискретной математике Йожефом Беком 2009 ISBN 0-8218-4756-2 стр. 44 
  3. ^ Алгоритмы: основные идеи и приложения Владимира Андреевича Успенского, Алексея, Львовича Семенова 1993 Springer ISBN 0-7923-2210-X стр. 166 
  4. ^ Э. Борель, Ле probabilites denombrables и др Leurs приложения arithmetique Rend. Circ. Мат. Палермо, 27 (1909) 247–271
  5. ^ Лоран Бьенвеню «Стохастичность Колмогорова Лавленда» в STACS 2007: 24-й ежегодный симпозиум по теоретическим аспектам информатики Вольфгангом Томасом ISBN 3-540-70917-7 стр. 260 
  6. ^ Церковь, Алонсо (1940). «О понятии случайной последовательности». Бык. Амер. Математика. Soc . 46 (2): 130–136. DOI : 10.1090 / S0002-9904-1940-07154-X .
  7. ^ А. Н. Колмогоров, Три подхода к количественному определению информации Проблемы информации и передачи, 1 (1): 1–7, 1965.
  8. ^ DW Loveland, Новая интерпретация концепции случайной последовательности фон Мизеса Z. Math. Логик Grundlagen Math 12 (1966) 279–294
  9. ^ Введение в сложность Колмогорова и ее приложения Минг Ли, PMB Vitányi 1997 0387948686, страницы 149–151
  10. ^ Р. Дауни, Некоторые недавние достижения в области алгоритмической случайности в математических основах информатики 2004: Иржи Фиала, Вацлав Коубек 2004 ISBN 3-540-22823-3 стр. 44 
  11. ^ Шнорр, CP (1971). «Единый подход к определению случайной последовательности». Математическая теория систем . 5 (3): 246–258. DOI : 10.1007 / bf01694181 .
  12. ^ Юнгге Ван: Случайность и сложность. Кандидатская диссертация, 1996 г. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
  13. ^ Ван, Yongge (1999). «Разделение двух понятий случайности». Письма об обработке информации . 69 (3): 115–118. CiteSeerX 10.1.1.46.199 . DOI : 10.1016 / S0020-0190 (98) 00202-6 . 
  14. ^ Вольфганг Меркль, Колмогоров Лавленд Стохастичность в автоматах, языках и программировании: 29-й международный коллоквиум, ICALP 2002, Питер Видмайер и др. ISBN 3-540-43864-5 стр. 391 

Внешние ссылки

  • «Случайная последовательность» , Энциклопедия математики , EMS Press , 2001 [1994]
  • Видео по стабильности частоты. Почему люди не могут «угадать» случайным образом
  • Тесты на случайность Терри Риттера