AOP_Tom2 (1021737), страница 51
Текст из файла (страница 51)
Теорема М. Пусть действительное число х, 0 < х < 1, соответствует двоичной последовательности (Х„), если (О.ХэХ~ ... )т является двоичным представлением х. Прн этом почти все х соответствуют случайным в смысле определения В6 последовательностям, (Другим словами, множество всех действительных чисел х, соответствующих неслучайным по определению Вб двоичным последовательностям, имеет меру нуль.) Доказашельстиво. Пусть о — эффективный алгоритм, определяющий бесконечную последовательность различных неотрицательных чисел (э„), где выбор х„зависит только от п и Л,„для 0 < к < и, и пусть И вЂ” исчислимое правило подпоследовательности. Тогда любая двоичная последовательность (Л„) приводит к подпоследовательности (Х,„)Е и по определению В6 эта подпоследовательность должна быть либо конечной, либо 1-распределенной.
Достаточно доказать, что для фиксированных тс н Я множество д' (Е, о) всех действительных х, соответствующих (Х„), такое, что (Х,„)Я. бесконечна и не 1-распределена, имеет меру нуль. Для х существует неслучайное двоичное представление тогда и только тогда, когда х принадлежит ( ) й'(И, о), взятому по с сетному множеству выборов Е и о. Следовательно, пусть Е, о фиксированы. Рассмотрим множество Т(а~ах. а„), определенное для всех двоичных чисел а1аю .. а„как множество всех х, соответству- ющих (Х„), такое, что (Л,„) Тс имеет > г элементов, из которых первые г элементов равны ам аэ, ..., а, соответственно. Первым результатом будет неравенство (32) Т(а~аз...
а,) имеет меру < 2 Доказательство начнем с замечания, что Т(а, аэ... а„) является измеримым множеством: каждый элемент Т(а,аэ... а,) — действительное число я = (О.ХвХ~ ..)м для которого существует такое целое число т, что алгоритм о определяет различные значения эр, эм ..., эви и правило 1с определяет подпоследовательность Хем Х„, ..., Л",, такую, что Л, является г-м элементом этой подпоследовательности.
Множество всех действительных р = (О УэУ~...)м таких, что 1;, = Л„для 0 < я < т, также принадлежит Т(а~аз... а„) и является измеримым множеством, состоящим из конечного объединения двоичных подынтервалов 1м и. Поскольку существует только счетное множество таких двоичных интервалов, то Т(а~ах... а,) — счетное объединение двоичных интервалов, и оно, следовательно, измеримо. Более того, данный довод может быть распространен, чтобы показать, что мера Т(аз... а,, 0) равна мере Т(ам .. а„~ 1), так как последнее множество является объединением двоичных интервалов., полученных из предшествующей рекуррентной формулы У„= Х,„для 0 < и < ш и У,„ф Х,„.
Поскольку Т(а,... а„~О) С1 Т(аы .. а, ~ 1) С Т(ам .. а„<), мера Т(а~от...а„) равна самое большее половине меры Т(аы,,а, >). Неравенство (32) теперь легко получить индукцией по г. Сейчас, когда (32) установлено, осталось, по существу, показать, что двоичное представление почти всех действительных чисел равнораспределено. Пусть для 0 < е < 1 В(г, е) — это ( ) Т(п ~... а„), где объединение берется по всем двоичным строкам а~...
а„для которых число единиц и(г) среди а~... а„удовлетворяет неравенству )и(г] — 1г~ > сг. Число таких двоичных строк равно С(г, е) = 2 (ь), и суммирование выполняется по г+~ всем значениям и с ~й — 1г~ > ег. В упр. 1.2.10-21 доказано, что С(г, е) < 2"т'е ' ", отсюда' согласно (32) (ЗЗ) В(г, е) имеет меру < 2 "С(г, е) < 2е ' ". На следующем шаге определим В'(г, е) = В(г, с) 0 В(г + 1, с) 11 В(г + 2, е) 0 ть Мера В'(г,е) равна самое большее 2', >„2е ' " и является остатком сходящегося ряда, так что )цп (мера В'(г, е)) = О.
(34) Теперь, если я — действительное число, двоичное разложение (О.ХвХ~...')э которого приводит к бесконечной не 1-распределенной последовательности (Х,„)Тс, и если и(г) обозначает число 1 в первых г элементах последней последовательности, то для некоторого е > 0 и бесконечного множества г. Это означает, что х принадлежит В'(г, с) для всех г. И наконец, находим, что Х(К,Л) = Д П В'(.,1/1). ~»в г>1 Согласно (34) П„>, В"(г,1/1) имеет меру нуль для всех б Следовательно, !т'(Я., 5) имеет меру нуль. 1 Основываясь на факте существования двоичных последовательностей, удовлетворяющих определению Кб, можно показать существование (0..1) случайных в этом смысле последовательностей (подробности — в упр. 36). Состоятельность определения К6 в связи с этим установлена.
Е. Случайные конечные последовательности. Ловоды, приведенные вылив, показывают, что невозможно определить понятие случайности конечной последовательности: заданная конечная последовательность так же вероятна, как и любая другая. Да снх пор почти каждый согласен, что последовательность 011101001 "более случайна", чем 101010101., и последняя последовательность "более случайна", чем 000000000. Хотя верно, что истинно случайные последовательности проявляют локально неслучайное поведение,мы предполагаем такое поведение только у длинной конечной последовательности, а не у короткой. Предлагались различные способы определения случайности конечной последовательности, но здесь будут сделаны только наброски нескольких идей. Для простоты ограничимся рассмотрением Ь-нчных последовательностей.
Пусть задана Ь-ичная последовательность Лв, Л„..., Лн м Можно сказать, что Рг(5(п)) а р, если )и(дт)/г1' — р~ < 1/~IХ. (35) где и(п) — величина, появившаяся в определении А в начале раздела. Приведенную выше последовательность можно назвать й-распределенной, если Рг(Х„Х„вы .. Х„~ь 1 — — х1 хт...
хь) в 1/Ь" (36) для всех Ь-ичных чисел х~хэ...хь. (Ср. с определением П. К сожалению, последовательность может быть Ь-распределенной согласно этому новому определению, когда она не (Й вЂ” 1)-распределена.) Сейчас можно дать следующее аналогичное определению К1 определение случайности. Определение Ц1. Ь-ичивя последовательность длины Х случайна, если она Ь-распределена (в вышеприведенном смысле) для всех положительных целых чисел Ь (!Ойь Х.
Например, согласно этому определению существует 178 неслучайных двоичных последовательностей длины 11, 00000001111 10000000111 11000000011 11100000001 11110000000 00000001110 10000000110 11000000010 11100000000 11010000000 00000001101 10000000101 11000000001 10100000001 10110000000, 00000001011 10000000011 01000000011 01100000001 01110000000 00000000111 плюс 01010101010 и асе последовательности с девятью или более нулями, плюс асе последовательности, полученные из предшествующих последовательностей, если единицы и нули поменять местами. Подобным образом можно сформулировать определение, аналогичное определению Вб, для конечной последовательности.
Пусть А — множество алгоритмов, каждый из которых является процедурой выделения и выбора, дающей подпогшедовательность (Х,„)Е, как в доказательстве теоремы М. Определение ь)2. 5-пчнвя последовательность Хо, Хм ..., Хм-1 является (и, а)-случайной относительно множества алгоритмов А„если для каждой подпоследоеательноств Хп. Хн, ..., Х,, определенной алгоритмом А, мы имеем либо гп < п, либо 1 1 — и~(Хц,..., Хс ) — — < е для 0 < а < Ь. т Здесь и (х,,...,х ) — количество чисел а в последовательности хы..., х (Другими словами, каждая достаточно длинная подпоследовательность, определенная алгоритмом из множества А, должна быть приближенно раанораспределенной.) Основной идеей а атом случае является предположение, что А — множество "простых" алгоритмов и количество (н сложность) алгоритмов в А может увеличиваться при росте Х.
В качестве примера определения Я2 рассмотрим двоичную последовательность. Пусть А состоит из следующих четырех алгоритмов. а) Взять асю последовательность. Ь) Взять нечетные члены последовательности, начиная с первого. с) Взять члены последовательности, следующие за нулем. о) Взять члены последовательности, следующие за единицей.
Сейчас последовательность Ло, Хп ..., Хт является (4, -')-случайной относительно А, если: по (а) ~в(Хо+ Х1 + ° ° + Хт) — 1'~ < в, т. е. если последовательность содержит 3, 4 или 5 единиц; по (Ь) ~1(Хо + Хз + Х4 + Хе) — -'~ < -', т. е, если последовательность содержит точно 2 единицы на четной позиции; по (с) существуют три возможности в зависимости от того, как много нулей занимают позиции Хо,, Хсл если здесь 2 или 3 нуля, то нет необходимости а проверке (так как и = 4); если 4 нуля, то за ними должны следовать 2 нуля и 2 единицы; если 5 нулей, то за ними должны следовать 2 единицы и 3 нуля; по (б) мы получим условии, подобные условиям и (с).
Оказывается, что только следующие двоичные последовательности длины 8 являются (4, -')-случайными в соответствии с этими правилами, 00001011 00011010 00011011 00100011 00100110 00100111 00101001 00101100 00110010 00110011 00110110 00111001 01001110 01011011 01011110 01100010 01100011 01100110 01101000 01101100 01101101 01110010 ' 01110110 плюс те, которые получены из этих, если единицы и нули поменять местами. Ясна, что множество алгоритмов можно сделать таким большим, что не будет последовательностей, не удовлетворяющих определению, когда и и е малы. А.
Н. Колмогоров доказал, что (п,е)мшучайная двоичная последовательность всегда будеш существовать для любого заданного Ж, если число алгоритмов в А не превьппает 1 эье  — В 2 (37) Этот результат не достаточно строгий, чтобы показать, что последовательности, удовлетворяющие определению !41, существуют, но последние могут быть эффективно построены с использованием процедуры Риса (Вееэ) из упр.
3.2.2 — 21. Обобщенный спектральный критерий, основанный на дискретном преобразовании Фурье, можно использовать для проверки, насколько последовательность соответствует определению !41 [см. А. Согпрайпег, Рйувса! Нею Е52 (1995), 5634-5645). Другие интересные подходы к определению случайности приведены Пером Мартин-Лефом (Рег Маг!!п-Ее!, ХпГогшаг!оп апс! Сопгго! 9 (1966), 602 — 619).
Пусть задана конечная Ь-ичиая последовательность Хм ..., Хм, !(Х„...,Хм) — длина самой короткой программы Тьюринга, которая генерирует эту последовательность. (Вместо этого можно использовать другие классы эффективных алгоритмов, например такие, которые обсуждались в разделе 1.1.) Тогда !(Хы..., Хл) — мера "хаотичности" последовательности и это понятие можно отождествить со случайностью. Последовательности длины Х, максимизирующие !(Х,,...,Хм), можно называть случайными. (С практической точки зрения генерирование случайного числа компьютером — это, конечно, наихудшее определение "случайности", какое можно себе представить!) По существу, почти и то же время такое определение случайности независимо предложил Г.
Чайтин (С. Спа!с1п„А4СМ 16 (1969), 145-159.) Интересно отметить, что хотя в данных определениях не упоминается а свойствах равнораспределенности, как в наших определениях, Мартин-Леф и Чайтин доказали, что случайные последовательности этого вида также имеют ожидаемые свойства равнораспределенности. На самом деле Мартин-Леф продемонстрировал, что такие последовательности удовлетворяют всем вычислимым статистическим критериям случайности в соответствующем смысле. Дополнительную информацию об определении случайной конечной последовательности можно найти в следующих работах: Звонниц А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
