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