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

редактировать

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

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

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

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

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

Содержание

1 История
2 Три эквивалентных определения
3 Интерпретация определений
4 Свойства и примеры случайных последовательностей Мартина-Лёфа
5 Относительная случайность
6 Сильнее, чем Мартин -Лёфа случайность
7 Слабее, чем случайность Мартина-Лёфа
8 См. Также
9 Ссылки
10 Дополнительная литература

История

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

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

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

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

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

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

Конструктивное нулевое покрытие (Мартин-Лёф, 1966): это оригинальное определение Мартина-Лёфа. Для конечной двоичной строки w мы обозначим C w цилиндр, порожденный w. Это набор всех бесконечных последовательностей, начинающихся с w, который является основным открытым набором в канторовском пространстве. произведение мера μ (C w) цилиндра, порожденного w, определяется как 2. Каждое открытое подмножество канторовского пространства является объединением счетного последовательность непересекающихся основных открытых множеств, а мера открытого множества - это сумма мер любой такой последовательности. Эффективное открытое множество - это открытое множество, которое представляет собой объединение последовательности базовых открытых множеств, определенных рекурсивно перечисляемой последовательностью двоичных строк. Конструктивное нулевое покрытие или набор эффективных мер 0 - это рекурсивно перечислимая последовательность $U i {\ displaystyle U_ {i}}$ $U_ {i}$ эффективных открытых множеств, такая что $U i + 1 ⊆ U i { \ Displaystyle U_ {я + 1} \ substeq U_ {i}}$ $U_ {i + 1} \ substeq U_i$ и $μ (U i) ≤ 2 - я {\ displaystyle \ mu (U_ {i}) \ leq 2 ^ { -i}}$ $\ mu (U_i) \ leq 2 ^ {- i}$ для каждого натурального числа i. Каждое эффективное нулевое покрытие определяет $G δ {\ displaystyle G _ {\ delta}}$ $G_ \ delta$ набор меры 0, а именно пересечение множеств $U i {\ displaystyle U_ {i}}$ $U_ {i}$ .

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

G δ {\ displaystyle G _ {\ delta}}

G_ \ delta

, определяемом конструктивным нулевым покрытием.

Конструктивные мартингалы (Шнорр 1971): A мартингал - это функция $d: {0, 1} ∗ → [0, ∞) {\ displaystyle d: \ {0,1 \ } ^ {*} \ to [0, \ infty)}$ $d: \ {0,1 \} ^ * \ to [0, \ infty)$ такой, что для всех конечных строк w $d (w) = (d (w ⌢ 0) + d (w ⌢ 1)) / 2 {\ displaystyle d (w) = (d (w ^ {\ smallfrown} 0) + d (w ^ {\ smallfrown} 1)) / 2}$ $d (w) = (d (w ^ \ smallfrown 0) + d (w ^ \ smallfrown 1)) / 2$ , где $a ⌢ b {\ displaystyle a ^ {\ smallfrown} b}$ $a ^ \ smallfrown b$ - это конкатенация строк a и b. Это называется «условием справедливости»: если мартингейл рассматривается как стратегия ставок, то указанное выше условие требует, чтобы игрок играл против справедливых коэффициентов. Говорят, что мартингал d преуспевает в последовательности S, если $lim sup n → ∞ d (S ↾ n) = ∞, {\ displaystyle \ limsup _ {n \ to \ infty} d ( S \ upharpoonright n) = \ infty,}$ $\ limsup _ {n \ to \ infty} d (S \ upharpoonright n) = \ infty,$ где $S ↾ n {\ displaystyle S \ upharpoonright n}$ $S \ upharpoonright n$ - первые n битов S. Мартингал d равен конструктивная (также известная как слабо вычислимая, нижняя полувычислимая ), если существует вычислимая функция $d ^: {0, 1} ∗ × N → Q {\ displaystyle {\ widehat {d}}: \ {0,1 \} ^ {*} \ times \ mathbb {N} \ to {\ mathbb {Q}}}$ $\ widehat {d}: \ {0,1 \} ^ * \ times \ N \ to {\ mathbb {Q}}$ такой, что, для всех конечных двоичных строк w

$d ^ (w, t) ≤ d ^ (w, t + 1) < d ( w), {\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)$ $\ widehat {d} (w, t) \ leq \ widehat { d} (w, t + 1) <d (w),$ для всех натуральных чисел t,
$lim t → ∞ d ^ (w, t) = d (w). {\ displaystyle \ lim _ {t \ to \ infty} {\ widehat {d}} (w, t) = d (w).}$ $\ lim_ {t \ to \ infty} \ widehat {d} (w, t) = d (w).$

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

Интерпретации определений

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

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

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

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

Вероятность остановки Чейтина Ω является примером случайной последовательности.
RAND (дополнение RAND) - это подмножество меры 0 множества всех бесконечных последовательностей. Это подразумевается тем фактом, что каждое конструктивное нулевое покрытие покрывает набор меры 0, существует только счетное число конструктивных нулевых покрытий, и счетное объединение множеств меры 0 имеет меру 0. Это означает, что RAND является Измерьте 1 подмножество множества всех бесконечных последовательностей.
Каждая случайная последовательность нормальна.
Имеется конструктивное нулевое покрытие RAND. Это означает, что все эффективные тесты на случайность (то есть конструктивные нулевые покрытия) в некотором смысле подпадают под этот универсальный тест на случайность, поскольку любая последовательность, которая проходит этот единственный тест на случайность, будет проходить все тесты на случайность. (Martin-Löf 1966)
Существует универсальный конструктивный мартингал d . Этот мартингал универсален в том смысле, что для любого конструктивного мартингала d, если d преуспевает в последовательности, то d также преуспевает в этой последовательности. Таким образом, d преуспевает в каждой последовательности в RAND (но, поскольку d является конструктивным, он не преуспевает ни в одной последовательности в RAND). (Schnorr 1971)
Класс RAND - это $Σ 2 0 {\ displaystyle \ Sigma _ {2} ^ {0}}$ $\ Sigma _ {2} ^ {0}$ подмножество пространства Кантора, где $Σ 2 0 {\ displaystyle \ Sigma _ {2} ^ {0}}$ $\ Sigma _ {2} ^ {0}$ относится ко второму уровню арифметической иерархии. Это потому, что последовательность S находится в RAND тогда и только тогда, когда в универсальном эффективном нулевом покрытии есть некоторое открытое множество, не содержащее S; это свойство можно определить с помощью формулы $Σ 2 0 {\ displaystyle \ Sigma _ {2} ^ {0}}$ $\ Sigma _ {2} ^ {0}$ .
Существует случайная последовательность, которая является $Δ 2 0 {\ displaystyle \ Delta _ {2} ^ {0}}$ $\ Delta _ {2} ^ {0}$ , то есть вычислимым относительно оракула для задачи остановки. (Schnorr 1971) Ω Чейтина является примером такой последовательности.
Никакая случайная последовательность не является разрешимой, вычислимо перечислимой или совместно вычислимо-перечислимый. Поскольку они соответствуют $Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}$ $\ Delta_1 ^ 0$ , $Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}$ $\ Sigma_1 ^ 0$ и $Π 1 0 {\ displaystyle \ Pi _ {1} ^ {0}}$ $\ Pi_1 ^ 0$ уровней арифметической иерархии, это означает, что $Δ 2 0 {\ displaystyle \ Delta _ {2} ^ {0}}$ $\ Delta_2 ^ 0$ - это самый нижний уровень в арифметической иерархии, где можно найти случайные последовательности.
Каждая последовательность сводима по Тьюрингу некоторой случайной последовательности. (Кучера 1985/1989, 1986). Таким образом, существуют случайные последовательности произвольно высокой степени Тьюринга.

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

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

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

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

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

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

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

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

См. Также

Ссылки

Дополнительная литература

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

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

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

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

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

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

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

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

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