Случайная последовательность
Понятие случайной последовательности имеет важное значение в теории вероятностей и статистике . Эта концепция обычно опирается на понятие последовательности случайных , величин и многие статистические дискуссии начинаются со слов «пусть X 1 ,..., X n будут независимыми случайными величинами...». Однако, как заявил в 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]
См. также
[ редактировать ]- Случайность
- История случайности
- Генератор случайных чисел
- Семь состояний случайности
- Статистическая случайность
Ссылки
[ редактировать ]- Серджио Б. Волчан Что такое случайная последовательность? Американский математический ежемесячник , Vol. 109, 2002, стр. 46–63.
Примечания
[ редактировать ]- ^ «Что подразумевается под словом «случайный» в книге «Математика и здравый смысл » Филипа Дж. Дэвиса, 2006 г. ISBN 1-56881-270-1 страницы 180-182
- ^ Неизбежная случайность в дискретной математике , Йожеф Бек, 2009 г. ISBN 0-8218-4756-2 стр. 44
- ^ Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X стр. 166
- ^ Э. Борель, Счетные вероятности и их арифметические приложения Ренд. Цирк. Мачта. Палермо 27 (1909) 247–271
- ^ Лоран Бьенвеню «Стохастичность Колмогорова Лавленда» в STACS 2007: 24-й ежегодный симпозиум по теоретическим аспектам информатики Вольфганга Томаса ISBN 3-540-70917-7 стр. 260
- ^ Черч, Алонсо (1940). «О понятии случайной последовательности» . Бык. амер. Математика. Соц . 46 (2): 130–136. дои : 10.1090/S0002-9904-1940-07154-X .
- ^ А. Н. Колмогоров, Три подхода к количественному определению информации. Проблемы информации и передачи, 1 (1): 1–7, 1965.
- ^ Д. У. Лавленд, Новая интерпретация концепции случайной последовательности фон Мизеса Z. Math. Logik Grundlagen Math 12 (1966) 279–294
- ^ Введение в колмогоровскую сложность и ее приложения, автор Мин Ли, PMB Vitány, 1997, 0387948686, страницы 149–151.
- ^ Р. Дауни, Некоторый недавний прогресс в области алгоритмической случайности в математических основах информатики, 2004 г.: Иржи Фиала, Вацлав Коубек, 2004 г. ISBN 3-540-22823-3 стр. 44
- ^ Шнорр, CP (1971). «Единый подход к определению случайной последовательности». Теория математических систем . 5 (3): 246–258. дои : 10.1007/bf01694181 . S2CID 8931514 .
- ^ Юнге Ван: Случайность и сложность. Кандидатская диссертация, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf.
- ^ Ван, Юнге (1999). «Разделение двух концепций случайности». Письма об обработке информации . 69 (3): 115–118. CiteSeerX 10.1.1.46.199 . дои : 10.1016/S0020-0190(98)00202-6 .
- ^ Вольфганг Меркл, Колмогоров Лавленд. Стохастичность в автоматах, языках и программировании: 29-й международный коллоквиум, ICALP 2002, Питер Видмайер и др. ISBN 3-540-43864-5 стр. 391
Внешние ссылки
[ редактировать ]- «Случайная последовательность» , Энциклопедия математики , EMS Press , 2001 [1994]
- Видео о стабильности частоты. Почему люди не могут «угадывать» случайно
- Тесты на случайность Терри Риттера