Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 52
Текст из файла (страница 52)
а„для которых число единиц и(г) среди а~... а„удовлетворяет иеравенству Число таких двоичиых строк равно С(г,е) = 2 (",), и суммирование вгяполняется по всем значениям й с !и — ~1г! > сг. В упр. 1.2.10-21 доказана, что С(г,с) < 2" ' 'е ' ", отсюда согласно (32) (33) В(г,е) имеет меру < 2 "С(г,е) < 2е ' ". На следующем шаге определим В"(гсе) =В(г,е)иВ(г+1,е)иВ(г+2,с)О " Мера В'(г, с) равна самое большее ~ь>„2е ' " и является остатком сходящегося ряда, так что 11ш (мера В'(г,г)) = О. (34) Теперь, если к — действительное число, двоичное разложение (О.ХеЛ ~ ...')в которого приводит к бескомечной ие 1-рвспределеииой последовательности (Х,„) Я., и если и(г) обозначает число 1 в первых г элементах последней последовательности, то !и(г)/г — Ц > е для некоторого е > 0 и бесконечного множества г. Это означает, что х принадлежит В'(г,е) для всех г.
И наконец, находим, что А (И, Б) = Ц П В'(г, 1/»). »>» «й» Согласно (34) П„>, В'(г, 1/1) имеет меру нуль для всех й Следовательно, Х(Я,В) имеет меру нуль. $ Основываясь на факте существования двоичных последовательностей, удовлетворяюсцих определению Вб, можно показать существование (О ..1) случайных в этом смысле последовательностей (подробности — в упр. 36). Состоятельность определения Еб в связи с этим установлена, Е. Случайные конечные последовательности. Доводы, приведенные выше, показывают, что невозможно определить понятие случайности конечной последовательности: заданная конечная последовательность так же вероятна, как и любая другая. До сих пор почти каждый согласен, что последовательность 011101001 "более случайна", чем 101010101, и последняя последовательность "более случайна", чем 000000000.
Хотя верно, что истинно случайные последовательности проявляют локально неслучайное поведение,мы предполагаем такое поведение только у длинной конечной последовательности, а не у короткой, Предлагались различные способы определения случайности конечной последовательности, но здесь будут сделаны только наброски нескольких идей. Для простоты ограничимся рассмотрением Ь-ичиых последовательностей.
Пусть задана Ъ-ичная последовательность Лш Хы ..., Лл и Можно сказать, что Рг(5(п)) ы р, если (и(Х)/Х вЂ” р( ( 1/»/Х, (35) где и(п) — величина, появившаяся в определении А в начале раздела. Приведенную выше последовательность можно назвать |с-распределенной, если Рг(Х Л„е»... Х„+» 1 = х»хю .. х») ж 1/Ь" (36) для всех Ъ-ичных чисел х»хю ..
х». (Ср. с определением )У. К сожалению, последовательность может быть й-распределенной согласно этому новому определению, когда она не (Й вЂ” 1)-распределена.) Сейчас можно дать следующее аналогичное определению Е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. б-нчная последовательность Хе, Хг, ..., Хя г является (и, с)-случайной относительно множества алгоритмов А, если для каждой падпоследовательностя Хп, Хм, ..., Х~„, определенной алгоритмом А, мы имеем либо гп < и, либо ! 1 1 — иа(Хм,...,Хф ) — — <е дзя 0<а <Ь, Здесь и„(хы..., хм) — количество чисел а в последовательности хд,..., х,„, (Другими словами, каждая достаточно длинная подцоследовательность, определенная алгоритмом из множества А, должна быть приближенно равнораспределенной.) Основной идеей в этом случае является предположение, что А — множество "простых" алгоритмов и количество (и сложность) алгоритмов в А может увеличиваться при росте т.
В качестве примера определения 442 рассмотрим двоичную последовательность. Пусть А состоит иэ следующих четырех алгоритмов. а) Взять всю последовательность. Ь) Взять нечетные члены последовательности, начиная с первого. с) Взять члены последовательности, следующие за нулем. б) Взять члены последовательности, следующие за единицей. Сейчас последовательность Хе, Хм ..., Хт является (4,-")-случайной относительно А, если; по (а) ~3(Хо+ Х~ + + Хт) — ~2~ < ~3, т. е. если последовательность содержит 3, 4 или 5 единиц; цо (Ь) ~2(Хо+ Хэ+ Ха+ Хе) — Ц < -', т. е. если последовательность содержит точно 2 единицы на четной позиции; по (с) существуют три возможности в зависимости от того, как много нулей занимают позиции Ле, ..., Ле: если здесь 2 или 3 нуля, то нет необходимости в проверке (так как и = 4); если 4 нуля, то за ними должны следовать 2 нуля и 2 едкницы; если 5 нулей, то за ними должны следовать 2 единицы и 3 ~уля; по (д) мы получим условия, подобные условиям в (с).
Оказывается, что только следукнцие двоичные последовательности длины 8 являются (4, й)-случайными в соответствии с этими правилами, 1 00001011 00011010 00011011 00100011 00100110 00100111 01101000 0110ПОО 01101101 01110010 ' 0Н10П0 01001110 01011011 01011110 01100010 01100011 01100110 00101001 00101100 00110010 00110011 00110110 00111001 плюс те, которые получены из этих, если единицы и нули поменять местами. Ясно, что множество алгоритмов можно сделать таким большим, что не будет последовательностей, не удовлетворяющих определению, когда и и е малы. А. Н.
Колмогоров доказал, что (и, е)-случайная двоичная последовательность всегда брдегл существовать для любого заданного Х, если число алгоритмов в А не превышает зп~~р-с) зе Этот результат не достаточно строгий, чтобы показать, что последовательности, удовлетворяющие определению С)1, существуют, но последние могут быть эффективно построены с использованием процепуры Риса (Вееэ) из упр. 3.2.2-21. Обобщенный спектральный критерий, основанный на дискретном преобразовании Фурье, можно использовать для проверки, насколько последовательность соответствует определению (41 (см. А.
Сотрайпег, РЬуз!са( йек Е52 (1995), 5634-5645). Другие интересные подходы к определению случайности приведены Пером Мартин-Лефом (Рег МагГш-ЬоГ, 1пгогтапоп апд Сопгго1 9 (1966), 602-619). Пусть задана конечная Ь-нчная последовательность Хы ..., Х~д, 1(Хы..., Хя) — длина самой короткой программы Тьюринга, которая генерирует эту последовательность. (Вместо этого можно использовать другие классы эффективных алгоритмов, например такие, которые обсуждались в разделе 1,1.) Тогда 1(Хэ,..., Хн) — мерв "хаотичности" последовательности и это понятие можно отождествить со случайностью. Последовательности длины Ж, максимизирующие 1(Хы..., Хл), можно называть случайными.
(С практической точки зрения генерирование случайного числа компьютером — это, конечно, наихудшее определение "случайности", какое можно себе представить!) По существу, почти в то же время такое определение случайности независимо предложил Г. Чайтин (О. Сйыгишц .7АСМ 16 (1969), 145-159.) Интересно отметить, что хотя в данных определениях не упоминается о свойствах равнораспределенности, как в наших определениях, Мартин-Леф и Чайтин доказали, что случайные последовательности этого вида также имеют ожидаемые свойства равнораспределенности. На самом деле Мартин-Леф продемонстрировал, что такие последовательности удовлетворяют всем вычислимым статистическим критериям случайности в соответствующем смысле.
Дополнительную информацию об определении случайной конечной последовательности можно найти в следующих работах: Звонкнн А. К. и Левин Л. А. Успехи мат. наук 35,6 (Ноябрь, 1970), 85-127; Левин Л. А. Докл. Акад. наук СССР 212 (1973), 548-550; Левин Л. А. Информация н контроль 61 (1984), 15-37. Р. Псевдослучайные числа, С теоретической точки зрения утешительно знать, что существуют случайные конечные последовательности с разными особенностями, но такие теоремы не дают ответов на вопросы, с которыми сталкиваются в действительности программисты.
Недавние исследования привели к более практичной теории, основанной на изучении множесптв конечных последовательностей. Точнее, рассмотрим мрльшимнажества, в которых последовательности могут появляться более одного раза. Пусть 5 — мультимножество, содержащее двоичные строки длины Ж; назовем 5 Х-исшочннком. Пусть Зм означает определенный Х-источник, содержащий все 2м возможных Х-двоичных строк. Каждый элемент 5 представляет последовательность, которую можно использовать в качестве источника псевдослучайных двоичных разрядов, выбор различных "начальных" значений приводит к различным элементам 5. Например, возможно такое множество 5 (В~Вэ... Вм ~ Ву старший значащий двоичный разряд Ху) (38) в линейной конгруэнтной последовательности, определенной равенством Л ~~ (аЛ1 + с) шоб 2', в котором суцгествует одна строка В~Вэ...Вм для каждого из 2' начальных значений Ле.
Основной идеей псевдослучайных последовательностей, как будет показано в этой главе, является получение Х двоичных разрядов, появляющихся случайно, несмотря на то что мы используем лишь несколько "истинно случайных" двоичных разрядов, когда выбираем начальное значение. В только что рассмотренном примере понадобилось е истинно случайных двоичных разрядов для выбора Ле. Вообще, для использования отбирается 18 15~ из 5 истинно случайных двоичных разрядов, после чего процедура становится детерминированной. Если Х = 10э и (5~ = 2ээ, получаем более 30 ООО "кажущихся случайными" двоичных разрядов из выбранного истинно случайного двоичного разряда, При йя вместо 5 мы не получим такого большого числа "случайных разрядов". поскольку 18 фм~ = Х, Что означает "кажущихся случайными"? Э.
Ч. Яо (А. С. Уао) в 1982 году предложил хорошее определение: рассмотрим любой алгоритм А, который при применении к строке двоичных разрядов В = В~... Вь выдает значение А(В) = 0 или 1. Можно рассматривать А как критерий случайности, например алгоритм А может вычислить распределение серий последовательных нулей и единиц, выдавая на выходе единицу, если длины серий значительно отличаются для ожидаемого распределения. Что бы ни делал А, вероятность Р(А,5) можно рассматривать как вероятность того, что А(В) = 1, когда  — случайно выбранный элемент нз 5, и можно сравнивать с вероятностью Р(А, Эм) того, что А(В) = 1, когда  — истинно случайная строка двоичных разрядов длины Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
