Случайная последовательность - Random sequence

Фортуна, Богиня случая, изображенная Тадеуш Кунце, 1754 (Национальный музей в Варшава ).

Концепция случайная последовательность имеет важное значение в теория вероятности и статистика. В основе концепции обычно лежит понятие последовательность из случайные переменные и многие статистические дискуссии начинаются со слов "пусть Икс1,...,Иксп быть независимыми случайными величинами ... ". Д. Х. Лемер заявил в 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-х годах Пер Мартин-Лёф заметил, что множества, кодирующие такие частотные стохастические свойства, представляют собой особый вид измерять ноль множества, и что более общее и гладкое определение может быть получено путем рассмотрения всех нулевых множеств с эффективной мерой.
  • В сложность / сжимаемость подход. Эту парадигму отстаивал А. Н. Колмогоров вместе с вкладами Левина и Григорий Чайтин. Для конечных случайных последовательностей Колмогоров определил «случайность» как энтропию, т.е. Колмогоровская сложность, строки длины K нулей и единиц как близость ее энтропии к K, то есть, если сложность строки близка к K, она очень случайна, а если сложность намного ниже K, она не так уж случайна.
  • В предсказуемость подход. Эта парадигма возникла из-за Клаус П. Шнорр и использует несколько иное определение конструктивного мартингалы чем мартингалы, используемые в традиционной теории вероятностей.[11] Шнорр показал, как существование избирательной стратегии ставок подразумевает существование правила отбора для смещенной подпоследовательности. Если для успеха в последовательности требуется только рекурсивный мартингал, а не для конструктивного успеха в последовательности, то можно получить концепцию рекурсивной случайности. Юнгге Ван показал[12][13] эта концепция рекурсивной случайности отличается от концепций случайности Шнорра.

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

Важно понимать, что для каждого из приведенных выше определений для бесконечных последовательностей, если добавить миллиард нулей в начало случайной последовательности, новая последовательность все равно будет считаться случайной. Следовательно, любое применение этих концепций к практическим задачам должно осуществляться с осторожностью.[15]

Смотрите также

использованная литература

Заметки

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

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