Алгоритмически случайная последовательность - Algorithmically random sequence

Интуитивно алгоритмически случайная последовательность (или же случайная последовательность) это последовательность двоичных цифр, которые появляются^{[требуется разъяснение ]} случайный для любого алгоритма, работающего на (без префиксов или без) универсальная машина Тьюринга. Это понятие можно применять аналогично к последовательностям любого конечного алфавита (например, десятичных цифр). Случайные последовательности являются ключевыми объектами изучения в алгоритмическая теория информации.

Поскольку иногда рассматриваются различные типы алгоритмов, от алгоритмов с определенными границами времени их работы до алгоритмов, которые могут задавать вопросы машина оракула, существуют разные представления о случайности. Самый распространенный из них известен как Случайность Мартина-Лёфа (K-случайность или же 1-случайность), но также существуют более сильные и более слабые формы случайности. Термин «алгоритмически случайный», используемый для обозначения конкретной одиночной (конечной или бесконечной) последовательности без пояснений, обычно означает «несжимаемая» или, в случае, если последовательность бесконечна и префикс алгоритмически случайна (т. Е. K-несжимаемая), «Мартин-Лёф-Чайтин случайный».

Важно устранить неоднозначность алгоритмической случайности со стохастической случайностью. В отличие от алгоритмической случайности, которая определена для вычислимых (и, следовательно, детерминированных) процессов, стохастическая случайность обычно называется свойством последовательности, которая, как априори известно, генерируется (или является результатом) независимый идентично распределен равновероятный случайный процесс.

Поскольку бесконечные последовательности двоичных цифр можно отождествить с действительными числами в единичном интервале, случайные двоичные последовательности часто называют (алгоритмически) случайные действительные числа. Кроме того, бесконечные двоичные последовательности соответствуют характеристическим функциям наборов натуральных чисел; поэтому эти последовательности можно рассматривать как наборы натуральных чисел.

Класс всех случайных (двоичных) последовательностей Мартина-Лёфа обозначается RAND или MLR.

История

Первое подходящее определение случайной последовательности было дано Пер Мартин-Лёф в 1966 году. Более ранние исследователи, такие как Рихард фон Мизес попытался формализовать понятие тест на случайность чтобы определить случайную последовательность как такую, которая прошла все тесты на случайность; однако точное понятие теста на случайность осталось неясным. Ключевой вывод Мартина-Лёфа заключался в использовании теория вычислений формально определить понятие теста на случайность. Это контрастирует с идеей случайности в вероятность; В этой теории ни один конкретный элемент пространства выборки нельзя назвать случайным.

С самого начала было показано, что случайность Мартина-Лёфа допускает множество эквивалентных характеристик - в терминах сжатие, тесты на случайность и играть в азартные игры - которые внешне мало похожи на исходное определение, но каждое из них удовлетворяет нашему интуитивному представлению о свойствах, которыми должны обладать случайные последовательности: случайные последовательности должны быть несжимаемыми, они должны проходить статистические тесты на случайность, и должно быть трудно зарабатывать деньги делать ставки на них. Существование этих множественных определений случайности Мартина-Лёфа и стабильность этих определений при различных моделях вычислений свидетельствуют о том, что случайность Мартина-Лёфа является фундаментальным свойством математики, а не случайностью конкретной модели Мартина-Лёфа. Тезис о том, что определение случайности Мартина-Лёфа «правильно» отражает интуитивное понятие случайности, был назван Тезис Мартина-Лёфа – Чайтина; он чем-то похож на Тезис Черча – Тьюринга.^[1]

Три эквивалентных определения

Первоначальное определение случайной последовательности Мартином-Лёфом было в терминах конструктивных нулевых покрытий; он определил последовательность как случайную, если она не содержится ни в одном таком покрытии. Григорий Чайтин, Леонид Левин и Клаус-Питер Шнорр доказал характеристику с точки зрения алгоритмическая сложность: последовательность случайна, если существует равномерная граница сжимаемости ее начальных сегментов. Шнорр дал третье эквивалентное определение в терминах мартингалы. Книга Ли и Витаньи Введение в колмогоровскую сложность и ее приложения стандартное введение в эти идеи.

Алгоритмическая сложность (Чайтин 1969, Шнорр 1973, Левин 1973): Алгоритмическая сложность (также известная как (без префиксов) Колмогоровская сложность или сложность размера программы) можно рассматривать как нижнюю границу алгоритмической сжимаемости конечной последовательности (символов или двоичных цифр). Каждой такой последовательности он присваивает ш натуральное число К (Вт) который интуитивно измеряет минимальную длину компьютерной программы (написанной на каком-то фиксированном языке программирования), которая не требует ввода и выводит ш при запуске. Сложность должна быть без префиксов: за программой (последовательность 0 и 1) следует бесконечная строка нулей, а длина программы (при условии, что она останавливается) включает количество нулей справа от программа, которую читает универсальная машина Тьюринга. Дополнительное требование необходимо, потому что мы можем выбрать такую длину, чтобы длина кодировала информацию о подстроке. Учитывая натуральное число c и последовательность шмы говорим, что ш является cнесжимаемый если ${displaystyle K (w) geq | w | -c}$ .

Бесконечная последовательность S случайна по Мартину-Лёфу тогда и только тогда, когда существует постоянная c так что все S 'конечный префиксы находятся cнесжимаемый.

Конструктивные нулевые покрытия (Мартин-Лёф, 1966 г.): Это оригинальное определение Мартина-Лёфа. Для конечной двоичной строки ш мы позволяем C_ш обозначить цилиндр, созданный ш. Это набор всех бесконечных последовательностей, начинающихся с ш, который является базовым открытым набором в Канторовское пространство. В товар мера μ (C_ш) цилиндра, порожденного ш определяется как 2^−|ш|. Каждое открытое подмножество пространства Кантора представляет собой объединение счетной последовательности непересекающихся основных открытых множеств, а мера открытого множества - это сумма мер любой такой последовательности. An эффективный открытый набор - открытое множество, представляющее собой объединение последовательности основных открытых множеств, определяемых рекурсивно перечислимый последовательность двоичных строк. А конструктивное нулевое покрытие или же эффективная мера 0 набор рекурсивно перечислимая последовательность ${displaystyle U_ {i}}$ эффективных открытых множеств таких, что ${displaystyle U_ {i + 1} subteq U_ {i}}$ и ${displaystyle mu (U_ {i}) leq 2 ^ {- i}}$ для каждого натурального числа я. Каждое эффективное нулевое покрытие определяет ${displaystyle G_ {delta}}$ множество меры 0, а именно пересечение множеств ${displaystyle U_ {i}}$ .

Последовательность определяется как случайная по Мартину-Лёфу, если она не содержится ни в каком ${displaystyle G_ {delta}}$ набор определяется конструктивным нулевым покрытием.

Конструктивные мартингалы (Шнорр 1971): А мартингейл это функция ${displaystyle d: {0,1} ^ {*} o [0, infty)}$ такой, что для всех конечных строк ш, ${displaystyle d (w) = (d (w ^ {smallfrown} 0) + d (w ^ {smallfrown} 1)) / 2}$ , куда ${displaystyle a ^ {smallfrown} b}$ это конкатенация струн а и б. Это называется «условием справедливости»: если мартингейл рассматривается как стратегия ставок, то указанное выше условие требует, чтобы игрок играл против справедливых коэффициентов. Мартингейл d говорят преуспевать в последовательности S если ${displaystyle limsup _ {n o infty} d (Supharpoonright n) = infty,}$ куда ${displaystyle Supharpoonright n}$ это первый п кусочки S. Мартингейл d является конструктивный (также известен как слабо вычислимый, полувычислимый снизу), если существует вычислимая функция ${displaystyle {widehat {d}}: {0,1} ^ {*} imes mathbb {N} o {mathbb {Q}}}$ так что для всех конечных двоичных строк ш

${displaystyle {widehat {d}} (w, t) leq {widehat {d}} (w, t + 1)$ для всех положительных целых чисел т,
${displaystyle lim _ {t o infty} {widehat {d}} (ш, т) = д (ш).}$

Последовательность является случайной по Мартин-Лёфу тогда и только тогда, когда на ней не удается создать конструктивный мартингал.

Толкование определений

Характеризация сложности Колмогорова передает интуицию, что случайная последовательность несжимаема: никакой префикс не может быть произведен программой намного короче префикса.

Характеристика нулевого покрытия передает интуицию, что случайное действительное число не должно обладать каким-либо свойством, которое является "необычным". Каждый набор тактов 0 можно рассматривать как необычное свойство. Последовательность не может лежать ни в каких наборах меры 0, потому что каждое одноточечное множество имеет меру 0. Идея Мартина-Лёфа заключалась в том, чтобы ограничить определение мерой 0 множеств, которые эффективно описываются; определение эффективного нулевого покрытия определяет счетную коллекцию эффективно описываемых наборов меры 0 и определяет последовательность как случайную, если она не лежит ни в одном из этих конкретных наборов меры 0. Поскольку объединение счетного набора множеств с мерой 0 имеет меру 0, это определение немедленно приводит к теореме о том, что существует множество случайных последовательностей с мерой 1. Обратите внимание, что если мы отождествляем пространство Кантора двоичных последовательностей с интервалом [0,1] действительных чисел, мера на пространстве Кантора согласуется с Мера Лебега.

Характеристика мартингейла подсказывает интуицию, что ни одна эффективная процедура не может делать деньги, делая ставки против случайной последовательности. Мартингейл d это стратегия ставок. d читает конечную строку ш и ставит деньги на следующий бит. Он ставит некоторую долю своих денег на то, что следующий бит будет равен 0, а затем оставшуюся часть своих денег делает ставку на то, что следующий бит будет 1. d удваивает деньги, которые он вложил в то, что действительно произошло, и теряет остаток. d(ш) - это сумма денег, которую он получил после просмотра строки ш. Поскольку ставка сделана после просмотра строки ш можно рассчитать из значений d(ш), d(ш0), и d(ш1), расчет имеющейся у него суммы эквивалентен расчету ставки. Характеристика мартингейла говорит о том, что никакая стратегия ставок, реализуемая на любом компьютере (даже в слабом смысле конструктивных стратегий, которые не обязательно вычислимый ) можно делать деньги, делая ставки на случайную последовательность.

Свойства и примеры случайных последовательностей Мартина-Лёфа

Вероятность остановки Чайтина Ω является примером случайной последовательности.
RAND^c (в дополнять RAND) является мера 0 подмножество множества всех бесконечных последовательностей. Это подразумевается тем фактом, что каждое конструктивное нулевое покрытие покрывает множество меры 0, есть только счетно много конструктивные нулевые покрытия, и счетное объединение множеств меры 0 имеет меру 0. Это означает, что RAND является подмножеством меры 1 множества всех бесконечных последовательностей.
Каждая случайная последовательность нормальный.
Имеется конструктивное нулевое покрытие RAND^c. Это означает, что все эффективные тесты на случайность (то есть конструктивные нулевые покрытия) в некотором смысле подпадают под эту категорию. универсальный тест на случайность, так как любая последовательность, которая проходит этот единственный тест на случайность, будет проходить все тесты на случайность. (Мартин-Лёф, 1966 г.)
Существует универсальный конструктивный мартингейл d. Этот мартингейл универсален в том смысле, что при любом конструктивном мартингале d, если d преуспевает в последовательности, тогда d преуспевает и в этой последовательности. Таким образом, d успешен в каждой последовательности в RAND^c (но с тех пор d конструктивен, он не преуспевает ни в одной последовательности в RAND). (Шнорр, 1971)
Класс RAND - это ${displaystyle Sigma _ {2} ^ {0}}$ подмножество пространства Кантора, где ${displaystyle Sigma _ {2} ^ {0}}$ относится ко второму уровню арифметическая иерархия. Это потому, что последовательность S находится в RAND тогда и только тогда, когда есть некоторое открытое множество в универсальном эффективном нулевом покрытии, которое не содержит S; это свойство можно определить с помощью ${displaystyle Sigma _ {2} ^ {0}}$ формула.
Есть случайная последовательность, которая ${displaystyle Delta _ {2} ^ {0}}$ , то есть вычислимым относительно оракула для проблемы остановки. (Шнорр, 1971) Чейтин Ω является примером такой последовательности.
Нет случайной последовательности разрешимый, вычислимо перечислимый, или же совместно вычислимо-перечислимый. Поскольку они соответствуют ${displaystyle Delta _ {1} ^ {0}}$ , ${displaystyle Sigma _ {1} ^ {0}}$ , и ${displaystyle Pi _ {1} ^ {0}}$ уровни арифметическая иерархия, это означает, что ${displaystyle Delta _ {2} ^ {0}}$ это самый низкий уровень в арифметической иерархии, на котором можно найти случайные последовательности.
Каждая последовательность Приводимый по Тьюрингу к некоторой случайной последовательности. (Кучера 1985/1989, Гач 1986). Таким образом, существуют случайные последовательности сколь угодно высокого Степень Тьюринга.

Относительная случайность

Поскольку каждое из эквивалентных определений случайной последовательности Мартина-Лёфа основано на том, что вычислимо с помощью некоторой машины Тьюринга, естественно спросить, что можно вычислить с помощью машины Тьюринга. машина оракула. Для фиксированного оракула А, последовательность B которая не только случайна, но и фактически удовлетворяет эквивалентным определениям вычислимости относительно А (например, нет мартингейла, конструктивного по отношению к оракулу А преуспевает на B) называется случайным относительно А. Две последовательности, хотя сами по себе случайны, могут содержать очень похожую информацию, и поэтому ни одна из них не будет случайной по отношению к другой. Каждый раз, когда есть Редукция Тьюринга от одной последовательности к другой вторая последовательность не может быть случайной относительно первой, точно так же, как вычислимые последовательности сами по себе неслучайны; в частности, это означает, что Ω Чайтина не является случайным относительно проблема остановки.

Важный результат, относящийся к относительной случайности: ван Ламбальген теорема, которая утверждает, что если C это последовательность, составленная из А и B путем чередования первого бита А, первая часть B, вторая часть А, вторая часть Bи так далее, то C алгоритмически случайна тогда и только тогда, когда А алгоритмически случайна, и B алгоритмически случайна относительно А. Близким следствием является то, что если А и B оба являются случайными, тогда А случайна относительно B если и только если B случайна относительно А.

Сильнее случайности Мартина-Лёфа

Относительная случайность дает нам первое понятие, которое сильнее случайности Мартина-Лёфа, то есть случайность относительно некоторого фиксированного оракула. А. Для любого оракула это, по крайней мере, так же сильно, а для большинства оракулов это строго сильнее, так как будут случайные последовательности Мартина-Лёфа, которые не являются случайными относительно оракула. А. Важные оракулы часто рассматриваются как проблема остановки, ${displaystyle emptyset '}$ , а пй прыжок оракул ${displaystyle emptyset ^ {(n)}}$ , поскольку эти оракулы могут отвечать на конкретные вопросы, которые возникают естественным образом. Последовательность, которая случайна относительно оракула ${displaystyle emptyset ^ {(n-1)}}$ называется п-случайный; следовательно, последовательность 1-случайна, если и только если она случайна по Мартину-Лёфу. Последовательность, которая п-случайно на каждый п называется арифметически случайным. В п-случайные последовательности иногда возникают при рассмотрении более сложных свойств. Например, существует только счетное количество ${displaystyle Delta _ {2} ^ {0}}$ наборы, поэтому можно подумать, что они не должны быть случайными. Однако вероятность остановки Ω является ${displaystyle Delta _ {2} ^ {0}}$ и 1-случайный; только после достижения 2-случайности случайный набор не может быть ${displaystyle Delta _ {2} ^ {0}}$ .

Слабее, чем случайность Мартина-Лёфа

Кроме того, есть несколько понятий случайности, которые слабее, чем случайность Мартина-Лёфа. Некоторые из них - слабая 1-случайность, случайность Шнорра, вычислимая случайность, частичная вычислимая случайность. Юнге Ван показал ^[2] что случайность Шнорра отличается от вычислимой случайности. Кроме того, известно, что случайность Колмогорова-Ловленда не сильнее случайности Мартина-Лёфа, но неизвестно, действительно ли она слабее.

На противоположном конце спектра случайности находится понятие K-тривиальное множество. Эти наборы антислучайны в том смысле, что весь начальный сегмент является логарифмически сжимаемым (т. Е. ${displaystyle K (w) leq K (| w |) + b}$ для каждого начального отрезка w), но они не вычислимы.

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

дальнейшее чтение

Дауни, Род; Hirschfeldt, Denis R .; Нис, Андре; Тервейн, Себастьян А. (2006). «Калибровка случайности». Вестник символической логики. 12 (3/4): 411–491. CiteSeerX 10.1.1.135.4162. Дои:10.2178 / bsl / 1154698741. Архивировано из оригинал на 02.02.2016.
Гач, Петер (1986). «Каждая последовательность сводится к случайной» (PDF). Информация и контроль. 70 (2/3): 186–192. Дои:10.1016 / с0019-9958 (86) 80004-3.
Кучера, А. (1985). "Мера,⁰
₁-классы и полные расширения ПА ». Неделя теории рекурсии. Конспект лекций по математике. 1141. Springer-Verlag. С. 245–259. Дои:10.1007 / BFb0076224. ISBN 978-3-540-39596-6.

Кучера, А. (1989). «Об использовании диагонально нерекурсивных функций». Исследования по логике и основам математики. 129. Северная Голландия. С. 219–239.

Левин, Л. (1973). «О понятии случайной последовательности». Советская математика - Доклады. 14: 1413–1416.

Li, M .; Витани, П. М. Б. (1997). Введение в колмогоровскую сложность и ее приложения (Второе изд.). Берлин: Springer-Verlag.

Мартин-Лёф, П. (1966). «Определение случайных последовательностей». Информация и контроль. 9 (6): 602–619. Дои:10.1016 / с0019-9958 (66) 80018-9.
Нис, Андре (2009). Вычислимость и случайность. Oxford Logic Guides. 51. Оксфорд: Издательство Оксфордского университета. ISBN 978-0-19-923076-1. Zbl 1169.03034.

Шнорр, К. П. (1971). «Единый подход к определению случайной последовательности». Математическая теория систем. 5 (3): 246–258. Дои:10.1007 / BF01694181. S2CID 8931514.

Шнорр, Клаус П. (1973). «Сложность процесса и эффективные случайные тесты». Журнал компьютерных и системных наук. 7 (4): 376–388. Дои:10.1016 / s0022-0000 (73) 80030-3.

Чайтин, Грегори Дж. (1969). «О длине программ для вычисления конечных двоичных последовательностей: статистические соображения». Журнал ACM. 16 (1): 145–159. Дои:10.1145/321495.321506. S2CID 8209877.

Вилле, Дж. (1939). Этюд с критикой коллекционного понятия. Париж: Готье-Виллар.

[1] Жан-Поль Делахайе, Случайность, непредсказуемость и отсутствие порядка, в Философия вероятности, п. 145-167, Springer 1993.

[2] Юнгге Ван: случайность и сложность. Кандидатская диссертация, 1996 г., http://webpages.uncc.edu/yonwang/papers/thesis.pdf

[1]

[2]