Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 55
Текст из файла (страница 55)
Выводы, история и библиография. Выше были определены различные степени случайности, которыми может обладать последовательность. Конечная оо-распределенная последовательность удовлетворяет великому множеству полезных свойств, которыми могут обладать случайные последовательности, и существует огромная теория, посвященная со-распределенным последовательностям. (В упражнениях, которые приводятся ниже, развиваются некоторые важные, не упомянутые в разделе, свойства таких последовательностей.) Определение Н! поэтому является подходящей основой дня теоретического изучения случайности. ' Понятие "со-распределение Ь-ичной последовательности" было введено в 1909 году Эмплем Борелем (Епц)е Ваге!). Он, по существу, ввел понятие (т, Ь)-распределенной последовательности и показал, что Ь-ичное представление почти всех действительных чисел является (т,Ь)-распределенным для всех т и й, Борель назвал такие чисиа яормальнммн по отношению к основанию Ь, Превосходное обсуждение этой темы появилось в его хорошо известной книге Ьесопв апг !а ТЬЙог!е дев Ропсбопн„2пд ед!с!оп (1914), 182-216.
Понятие оо-распределенной последовательности действительных чисел, также носящее название полностью равнараспределениай паследавательиастп, впервые появилось в заметке Н, М. Коробова (Доклады Акад. Наук СССР 62 (1948), 21-22). Коробов и несколько его коллег достаточно спироко развили теорию таких последоватеньностей в ряде статей в течение 50-х годов.
Полностью равно- распределенные последовательности независимо изучались Джоэнем Н. Франклиным (Зое1 Х. Ргап1сйп, ЛХагЬ. Сошр. 1у (1963), 28-59) в статье, которая особенно заслуживает внимания, так как она была вдохновлена проблемой генерирования случайных чисел. Книга Ь. Кшрегн апс! Н. %едегте!сег, ЬпКопп П!вгг!Ьиг!оп оГ Бес!иепст (Хенч Уогрс Ж!!еу, 1974) является чрезвычайно полным источником информации об огромной математической литературе, содержащей Ь-распределенные последовательности всех видов. Тем не менее мы увидели, что оо-распределенные последовательности не обладают достаточным количеством свойств, чтобы их можно было считать совершенно "случайными".
Определения Н4-Е6, приведенные выше, предусматривают дополнительные условия; в частности, определение Нб, видимо, было подходящим способом определения понятия бесконечной случайной последовательности. Это точное количественное утверждение, хорошо совпадающее с интуитивным понятием истинной случайности. Исторически развитие этих определений было стимулировано, главным образом, поискамн Р.
фон Мизесом (Н. топ М!эев) хорошего определения вероятности. В МаНь Яе!гэсйг!Н 5 (1919), 52-99, фон Мизес предложил определение, по духу сходное с определением Н5, хотя формулировка была слишком строга (подобно нашему определению НЗ), так что последовательностей, удовлетворяющих этим условиям, не существует. Многие исследователи отмечали это противоречие, и А. Г.
Коуплэнд (А. Н. Соре1апб, .Ашег, Х МаНь $0 (1928), 535-552) предлагал ослабить определение фон Мизеса заменой, которую он назвал допустимыми числами (или последовательностями Бернулли). Существует эквивалент оо-распределенных (О .. 1)-последовательностей, в которых все входные К, заменяются 1, если Ув < р илн 0 и если 6'„> р для заданной вероятности р. Так, Коуплэнд, по существу, предложил вернуться к определению Н1. Затем Абрахам Вальд (АЬгаЬаш Жа)6) показал, что нет необходимости так решительно ослаблять определение фон Мизеса, и предложил заменить счетное множество правилами подпоследовательностей. В важной статье ЕгйеЬп!ээе е!пеэ тай.
Ко!!осуп!шпэ 8 (лепна, 1937), 38-72, Вальд, по существу, доказал теорему %, хотя он сделал ошибочный вывод, что последовательность, построенная алгоритмом %, также удовлетворяет сильным условиям— Рг(С'„Е А) = мера 4 для всех измеримых по Лебегу 4 С (О., 1). Заметим, что не существует последовательности, которая может удовлетворять этому условию, Понятие "вычисляемость" играло большую роль на ранней стадии, когда Вальд написал статью и А. Черч (А. СЬцгсЬ, Ви!!..4шег. Май.
Бос. 46 (1940), 130 — 135) показал, как точное понятие "эффективный алгоритм" можно присоединить к те. ории Вальда, делая его определение совершенно строгим. Практически тогда же дополнение к определению Еб было предложено А. Н. Колмогоровым [Яаа)йуа А25 (1963), 369-376], как и определение Я2 для конечных последовательностей. Другое определение случайности для конечных последовательностей, находящееся где-то между определениями Я1 и Я2, намного раньше сформулировал А.
С. Безикович (А. 8. Веэ)сот(ссЬ, МаНь Ее!Гвс)н!гг 39 (1934), 146-156). В публикациях Черча и Колмогорова рассматривались только двоичные последовательности, для которых Рг(А'„= 1) = р с заданной вероятностью р. В этом разделе анализировалась более общая ситуация, поскольку (О ..
1)-последовательность, по существу, представляет все р сразу. Определение фон Мизеса-Вальда-Черча еще одним интересным способом усовершенствовал Дж. В. Говард (д. 'г'. Нопагб, 'Хе!Гэсйг. гйг шаНь Ъойй ипс! СгипсИвйеп г(ег АХаГЬ. 21 (1975), 215-224). Сле~0'ющнй важный вклад был сделан Дональдом В. Лавлендом (Попа!6 %. 1оте1апб, Хе!гзсйг. гйг шагй.
Еодй иЫ Стинг(!айеп Нег 5!агЬ. 12 (1966), 279 — 294), который обсудил определения Н4 — Н6 и несколько других понятий. Лавленд доказал, что существуют Н5-случайные последовательности, не удовлетворяющие определению Й4. В связи с этим он установил, что необходимо более строгое определение, такое как Нб. На самом деле Лавленд определил простую перестановку (у(п)) неотрицательных целых чисел и алгоритм Ълс', сходный с алгоритмом %, такой, что Р'((7г!ю ~ 1) — Р'("'г! > ~ 1) ~ 1 для каясдой В5-случайной последовательности ((уя), выдаваемой алгоритмом %', когда он задан бесконечным миожестволс правил подпоследовательпостей Йь Хотя определение Нб интуитивно строже определения Н4, очевидно, строю доказать это совсем не просто.
В течение нескольких лет данный вопрос оставался открытым, поскольку Н4 так или иначе включает в себя Нб. В конце концов, Томас Герцог (ТЬошаэ НегхоВ) и Джеймс К. Оуингс (мл.) (3ашеэ С. Окб!иВэ, 3г.) сумели построить большое семейство последовательностей, удовлетворяющих Н4, но не удовлетворяющих Нб. [См. Хе!гэсйг, Гбг тагЬ. ЪаВ!)с иЫ Огипг))аВеп с!ег Ма!Ь.
22 (1976), 385-389.) Другую важную статью написал Колмогоров [Проблемы передачи пнформацнгс 1 (1965), 3-11[. В ней ан рассмотрел проблему определения "информационного содержимого" последовательности, и эта работа привела к интересному определению Чайтина (СЬа!л!и) и Мартин-Лефа (Магбп-1.51) конечных случайных последовательностей через "хаотичность". [См. ГЕЕВ Тгапэ. 1Т-14 (1968), 662-664.) Их идея может быть также прослежена в работах Р. Дж. Соломонова (В. 3. Бо!ощипа(1, 1пгоппабап апд Сап!го! 7 (1964), 1-22, 224-254; 1ЕЕЕ Тгапэ.
1Т-24 (1978), 422-432; У. Сотр. Буэсехп Бей 55 (1997), 73-88). Обсуждение случайных последовательностей с философской точки зрения можно найти у К. Р. Поппера (К. Н, Роррег, ТЬе ЕоВ!с о! Бс!епс!Пс 1)!эсогегу (ьапг)оп., 1959)); особенно интересно построение на с. 162-163, впервые опубликованное в 1934 гаду. Дальнейшие связи между случайными последовательностями и теорией рекурсивных функций исследовались в работе О. Ъ'. Готе!апб, Тгаиэ. Атег. Ма!Ь, Бос.
125 (1966), 497-510. См. также работу К.-П. Шнорр (С.-Р. БсЬпогг, 2ейэсйг. !5айг. гегв'. СеЬ. 14 (1969), 27-35), нашедшего сильные связи между случайными последовательностями и "категориями меры", которые были определены Л. Э. Я. Броуэром (1. Е. Л. Вгоипег) в 1919 году. В следующей книге Шнорра, Еибл(!!В)сей ипс( ВаЬгэсйе!и!!сЬхей [Еесгиге 5!огеэ ш МагЬ. 218 (Вег!ш: Брг!пВег, 1971)), дан подробный обзор всей темы случайности и превосходное вступление к новым публикациям па этой теме. Обзор важнейших усовершенствований в течение следующих двух десятилетий можяо найти в книге Ап 1пггодисг!ап со Ко)тоВогог Согпр1ехйу апс( Вэ Арр!!сабапэ (БрппВег, 1993), МшВ 12 апс! Раи! М.
В. У!!апу!. Основы теории псевдослучайных последовательностей и эффективной информации заложены Мануэлем Блюмом (Мапие! В!шп), Сильвио Микали (Б!!ч!о М!са!!) и Эндре Яо (Алагем Уао) в работах [ЕОСБ 23 (1982). 80-91, 112-117; Б1СОМР 13 (1984), 850-864[, в которых построены первые явные последовательности, удовлетворяющие всем возможным статистическим критериям. Блюм и Микаля ввели понятие жесткого ядра двоичного разряда, булевой функции ~, такой, что ~(х) и д(х) легко вычисляются, хотя функция у[у! ')(х)) не вычисляется. В их статье берет начало лемма Р4.
Леонид Левин развил теорию в работе СогпЬ!пасоПса 7 (1987), 357-363, Затем он и Одед Голдрейч (Обед Оо!Йге!сЬ) [БТОС 21 (1989), 25-32[ проанализировали такие алгоритмы, как смешанно-квадратичный метод, и показали, что, используя маску подобным образом, можно получить жесткое ядро во многих случаях. Наконец, Левин в работе 3. Яушбойс Ъоб)с 38 (1993), 1102-1103, усовершенствовал методы предыдущей работы, введя алгоритм 1, и проанализировав его.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
