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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

${\ Displaystyle {\ widehat {d}} (ш, т) \ leq {\ widehat {d}} (ш, т + 1) <д (ш),}$ для всех натуральных чисел t ,
${\ displaystyle \ 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 ( w 0) и d ( w 1), вычисление имеющейся суммы денег эквивалентно вычислению ставки. Характеристика мартингейла говорит, что никакая стратегия ставок, реализуемая любым компьютером (даже в слабом смысле конструктивных стратегий, которые не обязательно вычислимы ), не может делать деньги, делая ставки на случайной последовательности.

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

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

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

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

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

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

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

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

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

На противоположном конце спектра случайностей находится понятие K-тривиального множества . Эти множества антислучайны в том смысле, что весь начальный сегмент является логарифмически сжимаемым (т. Е. Для каждого начального сегмента w), но они не вычислимы. ${\ Displaystyle К (ш) \ Leq К (| ш |) + Ь}$

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

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

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

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

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

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

Мартин-Лёф, П. (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). Этюд с критикой коллектива . Париж: Готье-Виллар.

Languages

In other projects