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

Двоичная последовательность

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

В теории вероятностей с мерой , введенной Андреем Колмогоровым в 1933 году, не существует такого понятия , как случайная последовательность. Например, рассмотрим подбрасывание честной монеты бесконечное количество раз. Любая конкретная последовательность, будь то или , имеет равную вероятность ровно нуля. Невозможно утверждать, что одна последовательность «более случайна», чем другая, используя язык теории вероятностей с мерой. Однако интуитивно очевидно, что выглядит более случайным, чем . Алгоритмическая теория случайности формализует эту интуицию. ${\displaystyle 0000\dots }$ ${\displaystyle 011010\dots }$ ${\displaystyle 011010\dots }$ ${\displaystyle 0000\dots }$

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

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

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

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

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

История

Рихард фон Мизес

Ричард фон Мизес формализовал понятие теста на случайность , чтобы определить случайную последовательность как ту, которая прошла все тесты на случайность. Он определил «коллектив» ( kollektiv ) как бесконечную двоичную строку, определенную таким образом, что ${\displaystyle x_{1:\infty }}$

• Существует предел . ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{i}=p\in (0,1)}$
• Для любого «допустимого» правила, такого, что оно выбирает бесконечную подпоследовательность из строки, мы все еще имеем . Он назвал этот принцип « невозможностью азартной системы ». ${\displaystyle (x_{m_{i}})_{i}}$ ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$

Чтобы выбрать подпоследовательность, сначала выберите бинарную функцию , такую, что при любой двоичной строке она выводит либо 0, либо 1. Если она выводит 1, то мы добавляем к подпоследовательности, иначе мы продолжаем. В этом определении некоторые допустимые правила могут воздерживаться вечно на некоторых последовательностях и, таким образом, не выбирать бесконечную подпоследовательность. Мы рассматриваем только те, которые выбирают бесконечную подпоследовательность. ${\displaystyle \phi }$ ${\displaystyle x_{1:k}}$ ${\displaystyle x_{k+1}}$

Другими словами, каждая бесконечная двоичная строка — это игра с подбрасыванием монеты, а допустимое правило — это способ для игрока решить, когда делать ставки. Коллектив — это игра с подбрасыванием монеты, где нет способа, чтобы один игрок выиграл больше, чем другой в долгосрочной перспективе. То есть, не существует игровой системы, которая бы работала для игры.

Определение обобщает двоичный алфавит на счетный алфавит:

• Частота каждой буквы стремится к пределу, большему нуля.
• Для любого «допустимого» правила, которое выбирает бесконечную подпоследовательность из строки, частота каждой буквы в подпоследовательности все равно стремится к одному и тому же пределу. ${\displaystyle (x_{m_{i}})_{i}}$

Обычно допустимые правила определяются как правила, вычислимые машиной Тьюринга, и мы требуем . При этом у нас есть случайные последовательности Мизеса–Вальда–Черча . Это не ограничение, поскольку, имея последовательность с , мы можем построить случайные последовательности с любым другим вычислимым . ^[1] Здесь «Черч» относится к Алонзо Черчу , чья статья 1940 года предложила использовать правила, вычислимые по Тьюрингу. ^[2] ${\displaystyle p=1/2}$ ${\displaystyle p=1/2}$ ${\displaystyle p\in (0,1)}$

Теорема. ( Абрахам Вальд , 1936, 1937) ^[3] Если существует только счетное число допустимых правил, то почти любая последовательность является коллективом.

Набросок доказательства: используйте теоретико-мерную вероятность.

Зафиксируйте одно допустимое правило. Выберите случайную последовательность из пространства Бернулли. С вероятностью 1 (используйте мартингалы) подпоследовательность, выбранная допустимым правилом, все еще имеет . Теперь добавьте все счетное число правил. С вероятностью 1 каждая подпоследовательность, выбранная каждым правилом, все еще имеет . ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$ ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$

Контрпример. (Жан Виль, 1939) ^[4] Если существует только счетное число допустимых правил, то существует коллектив с для всех . ${\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}x_{k}\geq p}$ ${\displaystyle n}$

Доказательство: См. ^[5]

Интуитивно, долгосрочное среднее случайной последовательности должно колебаться по обе стороны от , подобно тому, как случайное блуждание должно пересекать начало координат бесконечно много раз. Контрпример предполагает, что определение фон Мизеса недостаточно сильное. ${\displaystyle p}$

Пер Мартин-Лёф

Контрпример Вилле предполагает, что смысл случайности Мизеса–Вальда–Черча не достаточно хорош, потому что некоторые случайные последовательности не удовлетворяют некоторым законам случайности. Например, контрпример Вилле не удовлетворяет одному из законов итерированного логарифма : Наивно, можно исправить это, потребовав, чтобы последовательность удовлетворяла всем возможным законам случайности, где «закон случайности» — это свойство, которому удовлетворяют все последовательности с вероятностью 1. Однако для каждой бесконечной последовательности у нас есть закон случайности, который , что приводит к выводу, что случайных последовательностей не существует. $${\displaystyle \limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1}$$ ${\displaystyle y_{1:\infty }\in 2^{\mathbb {N} }}$ ${\displaystyle x_{1:\infty }\neq y_{1:\infty }}$

( Per Martin-Löf , 1966) ^[6] определил «случайность Мартина-Лёфа», допуская только законы случайности, которые являются вычислимыми по Тьюрингу. Другими словами, последовательность является случайной, если она проходит все вычислимые по Тьюрингу тесты случайности.

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

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

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

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

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

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

Бесконечная последовательность S является случайной по Мартину-Лёфу тогда и только тогда, когда существует константа c такая, что все конечные префиксы S являются c -несжимаемыми. Более кратко, ${\displaystyle K(w)\geq |w|-O(1)}$ .

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

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

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

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

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

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

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

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

Эффективный набор мер 0 можно интерпретировать как машину Тьюринга, которая способна сказать, учитывая бесконечную двоичную строку, выглядит ли строка случайной на уровнях статистической значимости. Набор является пересечением сжимающихся наборов , и поскольку каждый набор задается перечислимой последовательностью префиксов, учитывая любую бесконечную двоичную строку, если он находится в , то машина Тьюринга может решить за конечное время, что строка действительно попадает в . Следовательно, она может «отвергнуть гипотезу о том, что строка случайна на уровне значимости ». Если машина Тьюринга может отвергнуть гипотезу на всех уровнях значимости, то строка не является случайной. Случайная строка — это та, которая для каждого вычислимого по Тьюрингу теста случайности умудряется оставаться навсегда неотвергнутой на некотором уровне значимости. ^[8] ${\displaystyle U_{1}\supset U_{2}\supset U_{3}\supset \cdots }$ ${\displaystyle U_{n}}$ ${\displaystyle U_{n}}$ ${\displaystyle U_{n}}$ ${\displaystyle 2^{-n}}$

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

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

Универсальность

Существует универсальный конструктивный мартингал d . Этот мартингал универсален в том смысле, что если задан любой конструктивный мартингал d , то если d успешен на последовательности, то d также успешен на этой последовательности. Таким образом, d успешен на каждой последовательности в RAND ^c (но, поскольку d конструктивен, он не успешен ни на одной последовательности в RAND). (Шнорр, 1971)

Существует конструктивное нулевое покрытие RAND ^c . Это означает, что все эффективные тесты на случайность (то есть конструктивные нулевые покрытия) в некотором смысле включены в этот универсальный тест на случайность, поскольку любая последовательность, прошедшая этот единственный тест на случайность, пройдет все тесты на случайность. (Мартин-Лёф 1966) Интуитивно этот универсальный тест на случайность гласит: «Если последовательность имеет все более длинные префиксы, которые могут быть все более хорошо сжаты на этой универсальной машине Тьюринга», то она не случайна». — см. следующий раздел.

Эскиз конструкции: Перечислим эффективные нулевые покрытия как . Перечисление также эффективно (перечислено модифицированной универсальной машиной Тьюринга). Теперь у нас есть универсальное эффективное нулевое покрытие путем диагонализации: . ${\displaystyle ((U_{m,n})_{n})_{m}}$ ${\displaystyle (\cup _{n}U_{n,n+k+1})_{k}}$

Прохождение тестов на случайность

Если последовательность не проходит тест на алгоритмическую случайность, то она алгоритмически сжимаема. И наоборот, если она алгоритмически сжимаема, то она не проходит тест на алгоритмическую случайность.

Эскиз конструкции: Предположим, что последовательность не проходит тест на случайность, тогда ее можно сжать, лексикографически перечислив все последовательности, которые не проходят тест, затем закодировать местоположение последовательности в списке всех таких последовательностей. Это называется «перечислительным кодированием источника». ^[9]

И наоборот, если последовательность сжимаема, то по принципу ящика только исчезающе малая часть последовательностей такова, поэтому мы можем определить новый тест на случайность как «имеет сжатие этой универсальной машиной Тьюринга». Кстати, это и есть универсальный тест на случайность.

Например, рассмотрим двоичную последовательность, выбранную из распределения Бернулли IID. После взятия большого количества выборок у нас должно быть около единиц. Мы можем закодировать эту последовательность как "Сгенерировать все двоичные последовательности длиной , и единиц. Из них -я последовательность в лексикографическом порядке.". ${\displaystyle N}$ ${\displaystyle M\approx pN}$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle i}$

По приближению Стирлинга , где — двоичная энтропийная функция . Таким образом, число бит в этом описании равно: Первый член предназначен для префиксного кодирования чисел и . Второй член предназначен для префиксного кодирования числа . (Используйте омега-кодирование Элиаса .) Третий член предназначен для префиксного кодирования остальной части описания. Когда велико, это описание содержит только биты, и поэтому оно сжимаемо со степенью сжатия . В частности, степень сжатия равна единице (несжимаемо) только когда . (Пример 14.2.8 ^[10] ) ${\displaystyle \log _{2}{\binom {N}{pN}}\approx NH(p)}$ ${\displaystyle H}$ $${\displaystyle 2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)}$$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle N}$ ${\displaystyle \sim H(p)N}$ ${\displaystyle \sim H(p)}$ ${\displaystyle p=1/2}$

Невозможность игровой системы

Если рулеточный стол генерирует алгоритмически случайную последовательность, то нет способа обыграть дилера. Если нет, то есть способ.

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

Примеры

• Вероятность остановки Ω Хайтина является примером случайной последовательности.
• Не каждая случайная последовательность вычислима.
• Каждая случайная последовательность является нормальной , удовлетворяет закону больших чисел и удовлетворяет всем свойствам, вычислимым по Тьюрингу, которым удовлетворяет поток IID равномерно случайных чисел. (Теорема 14.5.2 ^[10] )

Отношение к арифметической иерархии

• RAND ^c ( дополнение RAND) является подмножеством меры 0 множества всех бесконечных последовательностей. Это следует из того факта, что каждое конструктивное нулевое покрытие покрывает множество меры 0, существует только счетное число конструктивных нулевых покрытий, а счетное объединение множеств меры 0 имеет меру 0. Это означает, что RAND является подмножеством меры 1 множества всех бесконечных последовательностей.
• Класс RAND является подмножеством пространства Кантора, где относится ко второму уровню арифметической иерархии . Это происходит потому, что последовательность S находится в RAND тогда и только тогда, когда существует некоторое открытое множество в универсальном эффективном нулевом покрытии, которое не содержит S ; это свойство можно определить с помощью формулы. ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$
• Существует случайная последовательность, которая является , то есть вычислимой относительно оракула для проблемы остановки. (Шнорр, 1971) Ω Хайтина является примером такой последовательности. ${\displaystyle \Delta _{2}^{0}}$
• Никакая случайная последовательность не является разрешимой , вычислимо перечислимой , или со-вычислимо-перечислимой . Поскольку они соответствуют уровням , и арифметической иерархии , это означает, что является самым низким уровнем в арифметической иерархии, где могут быть найдены случайные последовательности. ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$
• Каждая последовательность сводима по Тьюрингу к некоторой случайной последовательности. (Kučera 1985/1989, Gács 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. Часто рассматриваемыми важными оракулами являются проблема остановки, и оракул n- го перехода, , поскольку эти оракулы способны отвечать на конкретные вопросы, которые возникают естественным образом. Последовательность, которая случайна относительно оракула, называется n -случайной; последовательность является 1-случайной, следовательно, тогда и только тогда, когда она случайна по Мартину-Лёфу. Последовательность, которая является n -случайной для каждого n , называется арифметически случайной. n -случайные последовательности иногда возникают при рассмотрении более сложных свойств. Например, существует только счетное число множеств , поэтому можно подумать, что они должны быть неслучайными. Однако вероятность остановки Ω является 1-случайной; только после достижения 2-случайности становится невозможным, чтобы случайный набор был . ${\displaystyle \emptyset '}$ ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle \emptyset ^{(n-1)}}$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$

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

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

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

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

• Случайная последовательность
• Грегори Хайтин
• Стохастик
• Метод Монте-Карло
• K-тривиальный набор
• Вероятность универсальности
• Статистическая случайность

Ссылки

1. Ли, Мин; Витаний, ПМ (2019). "1.9 Случайность". Введение в сложность Колмогорова и ее приложения (четвертое изд.). Cham: Springer. ISBN 978-3-030-11298-1.
2. Коупленд, Артур Х. (июнь 1940 г.). «Алонзо Чёрч. О концепции случайной последовательности. Бюллетень Американского математического общества , т. 46 (1940 г.), стр. 130–135». Журнал символической логики (обзор). 5 (2): 71–72. doi :10.2307/2266178. ISSN  0022-4812. JSTOR  2266178. S2CID  124646586.
3. Вальд, А. (1936). О понятии коллективизма в расчете вероятностей. Comptes Rendus des Seances de l'Académie des Sciences, 202, 180–183. Вальд, А. (1937). Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrech- nung. Ergebnisse eines Mathematischen Kolloquiums, 8, 38–72.
4. Вилле, Дж. (1939). «Этюд критического анализа понятия коллектива» , «Монографии вероятностей», «Вычисление вероятностей и их приложений» , Готье-Виллар.
5. Либ, Эллиотт Х.; Ошерсон, Дэниел; Вайнштейн, Скотт (2006-07-11). «Элементарное доказательство теоремы Жана Вилля». arXiv : cs/0607054 .
6. Мартин-Лёф, Пер (1 декабря 1966 г.). «Определение случайных последовательностей». Информация и управление . 9 (6): 602–619. doi :10.1016/S0019-9958(66)80018-9. ISSN  0019-9958.
7. Жан-Поль Делаэ , Случайность, непредсказуемость и отсутствие порядка, в Философии вероятности , стр. 145–167, Springer 1993.
8. Ли, Витаньи, Раздел 2.4
9. Cover, T. (январь 1973). «Исходное кодирование перечисления». IEEE Transactions on Information Theory . 19 (1): 73–77. doi :10.1109/TIT.1973.1054929. ISSN  0018-9448.
10. Cover, Thomas M.; Thomas, Joy A. (2006-07-18). Элементы теории информации 2-е издание (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. ISBN 978-0-471-24195-9.
11. Юнге Ван: Случайность и сложность. Кандидатская диссертация, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

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

• Eagle, Anthony (2021), «Случайность против случайности», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (весна 2021 г.), Metaphysics Research Lab, Stanford University , получено 28.01.2024
• Дауни, Род; Хиршфельдт, Денис Р.; Нис, Андре; Тервейн, Себастьян А. (2006). «Калибровка случайности». The Bulletin of Symbolic Logic . 12 (3/4): 411–491. CiteSeerX  10.1.1.135.4162 . doi :10.2178/bsl/1154698741. Архивировано из оригинала 2016-02-02.
• Gács, Péter (1986). «Каждая последовательность сводится к случайной» (PDF) . Информация и управление . 70 (2/3): 186–192. doi : 10.1016/s0019-9958(86)80004-3 .
• Кучера, А. (1985). «Мера, Π⁰
  ₁-классы и полные расширения PA". Неделя теории рекурсии . Конспект лекций по математике. Том 1141. Springer-Verlag. С. 245–259. doi :10.1007/BFb0076224. ISBN 978-3-540-39596-6.
• Кучера, А. (1989). «Об использовании диагонально нерекурсивных функций». Исследования по логике и основаниям математики . Т. 129. Северная Голландия. С. 219–239.
• Левин, Л. (1973). «О понятии случайной последовательности». Советская математика — Доклады АН СССР . 14 : 1413–1416.
• Ли, М.; Витаний, П.М.Б. (1997). Введение в сложность Колмогорова и ее приложения (второе изд.). Берлин: Springer-Verlag.
• Мартин-Лёф, П. (1966). «Определение случайных последовательностей». Информация и управление . 9 (6): 602–619. doi :10.1016/s0019-9958(66)80018-9.
• Нис, Андре (2009). Вычислимость и случайность . Oxford Logic Guides. Том 51. Оксфорд: Oxford University Press. ISBN 978-0-19-923076-1. Збл  1169.03034.
• Шнорр, CP (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). Критический этюд понятия коллекционирования . Париж: Готье-Виллар.