Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 50
Текст из файла (страница 50)
Нет системы азартных игр, которая всегда приводит к победе! Определение Е4 ничего не говорит о подпоследовательности, формируемой в соответствии с такой системой азартных игр; так что, по-видимому, необходимо нечто большее. Пусть определено "правило подпоследовательности" Я. как бесконечной последовательности функцнй (~„(я~ „..., х„)), где для и > О, уэ — функция и переменных и значение ~„(яы...,я„) равно либо О, либо 1. Здесь яг, ..., х„— элементы некоторого множества 5.
(Таким образом, в данном случае уэ — это постоянная функция, равная либо О, либо 1.) Правило подпоследовательности к определяет подпоследовательность бесконечной последовательности (Л'„) элементов о' следующим образом: п-й член Х„принадлежит лодпоследовательяостп (Л„) И тогда и только тогда, когда у„(Хе, Хм..., Х„~) = 1. Заметим, что подпоследовательность (Х„)Я, определенная таким образом, необязательно бесконечна; фактически в ней вообще может яе быть элементов, Например., подпоследовательность азартного игрока, описанная выше, соответ- ствует такому правилу подпоследовательности: Д = 1 и для и > О, )'„(хы ..,, х„) = 1 тогда и только тогда, когда найдется некоторое 6, 0 < 6 < и, такое, что 6 последо- вательнык чисел х„„х ы ..., х ьч.1 все будут < —, когда т = п, но не когда 1 6<ш(п, Правило подпоследовательностей К называют исчислвммм, если существует эффективный алгоритм, определяющий значение ~„(хы..., х„), когда и и хы, .., х„ заданы на входе.
При попытке определить случайность лучше ограничиться исчис- лимыми правилами подпоследовательностей, когда пытаемся определить случай- ность, чтобы не получить чрезмерно ограничительное определение, подобное КЗ. Но эффективный алгоритм нельзя рассматривать с произвольными входными дей- ствительными числами. Например, если действительное число х точно определено бееконечным разложением в десятичной системе счисления, то не существует ал- горитма для тога, чтобы определить, будет ли х ( -, так как для этого нужно 1 исследовать все цифры числа О.ЗЗЗ.... Поэтому исчислимое правило падпогледова- тельностей неприменимо ко всем [О ..
1)-последовательностям и служит основой для следующего определения 6-ичнык последовательностей. Определение Кб, 6-нчнв» нос чедовательность называется случайной, если каждая бесконечная подпоследовательность, определенная ясчпслилсым правилам подпоследовательностей, является 1-распределенной. [О .. 1)-последовательность (У„) называется случайной. если 6-л чная последовательность ([61~„)) является случайной для всех целых чисел 6 > 2. Заметим, что определение К5 говорит только об 1-распределении, а не о оо-распределении.
Интересно проверить, что это может быть сделано без потери общности. Очевидно, можно определить исчислимое правило подпоследовательности К(аы .. аь) следующим образом при любом заданном Ь-ичном числе аы .. аь. пусть у„(хы...,х„) = 1 тогда и только тогда, когда и > Й вЂ” 1 и х„ьь~ — — аы ..., х„1 — — аь ы х„= аю Если (Л;,) является Й-распределенной Ь-ичной последовательностью, то правило Й(а1... аь), с помощью которого выбирается подпоследовательность, содержащая точно следующие за появчением аы .. аь члены, определяет бесконечную подпоследовательность, и, если эта подпоследовательность 1-распределена, каждая из строк аы .. аьаь„.1 размерности (6+1) лдя О < аь+1 < 6 появляется с вероятность 1/6~" в (Л'„).
Таким образом. индукцией по 6 можно доказать, что последовательность, удовлетворяющая определению К5, является 6-распределенной для всех 6. Подобным образом, рассматривая "композицию" правил подпоследовательностей, получаем: если 1с1 определяет бесконечную подпоследовательность (Х„)Кы то можно определить правило подпоследовательности К11<з, для которого (Л„) Я1 Еэ — — ((Х„) тс1))2ю и найти, что все подпоследовательности, рассматриваемые в определении К5, оо-распределенные (см. упр. З2). Факт, что оо-распределение следует из определения К5 как очень частный случай, ободряет, и это хороший признак того, что можно, наконец, найти требуемое определение случайности. Но, увы, это все еще проблема.
Не ясно, почему последовательность, удовлетворяющая определению К5, должна удовлетворять определе- нию Е4. Введенные нами исчислимые правила подпоследовательностей всегда дают подпоследовательности (Х,„), для которых зо < з1 < ., но (зе) не должны быть монотонны в К4; онн только должны удовлетворять условию з„ф з для и ф т.
Итак, определения И4 и Иб можно скомбинировать следующим образом. Определение Кб. 6-нчиая посдедовательиость (Л„) называется случайной, если для каждого эффективного алгоритма, точно определяюгцего бескоиечяую последовательность различных исотрицательяых целых чисел (ае) как функцию и и значений Х„,..., Л„„,, подпогледовательиость (Л,„), которая соответствует этому алгоритму, является случайяой в смысле определения гг5. (О .. 1)-последовательность (Ьг„) называется случайной, если 6-пчиая последовательность ((66'„~ ) является случайной для всех целых чисел Ь > 2.
Автор утверждаета, что это определение точно удовлетворяет всем разумным философским требованиям случайности, а значит, отвечает на основной вопрос, поставленный в этом разделе. О. Существование случайных последовательностей. Как было показано, определение гг3 слишком строгое и том смысле, что не существует удовлетворяющей ему последовательности, и в приведенных выше определениях К4-Кб предпринимались попытки сохранить существенные элементы определения Ю.
Для того чтобы показать, что определение Кб не чрезмерно ограничительно, все еще необходимо доказать, что последовательность, удовлетворяющая всем этим условиям, существует. Интуитивно мы совершенно правильно ощущаем, что это не проблема, так как мы верим, что истинно случайная погчедовательность существует и удовлетворяет определению К6. но доказательство действительно необходимо, чтобы показать, что определение состоятельно.
Интересный метод построения последовательностей, удовлетворяющих определению Нб., найден А. Вальден (А. Ъа1о). Он начинается с построения простой 1-распределенной последовательности. Ио 0 Ъ| .1 1э 01 гз ° 11 а .001 1;, = . с,... с1 1„если и = 2" + сг 2' ~ + ° + с„. (29) Обозначим через 1а, а, множество всех действительных чисел в (О .. 1), которые имеют двоичное представление, начиная с 0.6г... 6„. Такпч образом, 1„,. = ((0.6,... 6„)з (0.6,... 6„), +2-'). ,Тогда, если и(н) — число 1га в 1а,, а. прн 0 < й < и, получим (30) (ю (и)/и — 2 ") < 1/и.
(31) Доказательство. Так как г (и) — число 1г, для которых Ь шос1 2" = (Ь„... 61)т, получим р(п) =1 или 1+1, когда (и/2")' = 1.. Следовательно, ~и(п) — и/2'( < 1. $ * По крайней мере, ои сделал такое эаивлеиие, когда готовил этот материал е ! эбб году. Лемма Т. Пусть последователыгость действительных чисел (уе) опрелелеиа сле- дующим образом в терминах двоичной системы: Из (31) следует, что последовательность ([2"1'„)) — это равнораспределенная 2'-ичная последовательность. Отсюда согласно теореме А получаем, что (1'„)— равнораспределенная [0..1)-последовательность. Действительно, достаточно ясно, что (1'„) настолько равнораспределена на [0..1), насколько это вообще возможно. (Чтобы получить дополнительную информацию о данной и родственных последовательностях, обратитесь к работам 1.
С. гап дег Согрис„ Ргос. Ко»»шЩ)»е №дег1. А11ад. И есепэсЬаррел ЗВ (1935), 813-821, 1058-1066; Л. Н. На1соп, Хитег1эсЬе 51аг)ь 2 (1960), 84-90, 196:, В. НаЬег., Х НеаеагсЬ Хас)опа) Виг. Ясапс(агдв ВТО (1966), 127- 136; Н, Ве)сап аид Н. Ганге, Сотрсез Непдиэ Асад, Ясй Раг1э А285 (1977), 313-316; Н.
Ганге, Х МитЬег ТЬеогу 22 (1986), 4-20; 8. Тезис»а, АСИН 21впэ. Моде1шд апд Сотр, Яп»и). 3 (1993), 99-107. Л. Г. Рамшоу (1., Н. НапжЬаж) показал, что последонательность (»Спшод1) немного более равнораспределена, чем (г"„) (см. Х ХитЬег Т1»еогу 13 (1981), 138-175). Пусть сейчас 7»», Нз, ...
— бесконечное множество правил подпоследовательностей, и необходимо найти последовательность (С„), для которой все бесконечные подпоследовательности ((Г„)Н1 равнораспределены. Алгоритм Ж (Последовательность Вальда). Задана бесконечная последовательность правил подпоследовательностей Я.„ Нм ..., которая определяет подпоследовательностн [0..1)-последовательностей рациональных чисел. Эта процедура определяет [О ..
1)-последовательность (П„). Для вычисления требуется бесконечно много вспомогательных переменных С[а»,..., а„), где г > 1 и ау = О нли 1 для 1 < у < г. Вначале все эти переменные равны нулю. Ж1. [Инициализация п.) Присвоить и» вЂ” О. Ю2. [Инициализация г.) Присвоить г е- 1. гг'3. [Проверка 7С,.) Если элемент Г„должен принадлежать подпоследовательности, определенной 7»,, которая основана на значениях П» для 0 < х < и, присвоить а, +- 1; иначе — присвоить а„ +- О. %'4. [Случай [а»,...,а„] не окоячен7) Если С[а»,..., а,) < 3 ° 4' ', перейти к ша.- гу %6. 'эг'5. [Увеличить г.) 'Присвоить т е- г + 1 н возвратиться к шагу 1УЗ. '676.
[Присвоить (г„.) Увеличить значение С[а»,...,а,) на 1, и пусть 1с будет его НОВЫМ ЗНаЧЕНИЕМ. ПРИСВОИТЬ 5»„+- СГ»э ГДЕ 1Г» ОПРЕДЕЛЕНО В ПРИВЕДЕННОЙ ВЫШЕ лемме Т. 'ЙГ7. [Увеличение и.] Увеличить и на 1 и возвратиться к шагу %2. 1 Строго говоря, это не алгоритм, так как он не заканчивается, но мы„конечно, слегка преобразуем процедуру, чтобы он останавливал работу, когда и досыпает заданного значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
