нию R4. Введенные нами исчислимые правила подпоследовательностей всегда дают подпоследовательности {Xs„), для которых sq < si < • • •, но (s„) не должны быть монотонны в R4; они только должны здовлетворять условию s„ ф Sm Для пф т. Итак, определения R4 и R5 можно скомбинировать следующим образом.

Определение R6. Ь-пчная последовательность (Хп) называется случайной, если для каждого эффективного алгоритма, точно определяющего бесконечную последовательность различных неотрицательных целых чисел (s„) как функцию л и значений Xg, , Xs„ i, подпоследовательность {Xs„), которая соответствует этому алгоритму, является случайной в смысле определения R5.

[О.. 1)-последовательность {U„) называется случайной, если Ь-ичная последовательность {[bUnj) является случайной для всех целых чисел Ь>2.

Автор утверждает*, что это определение точно удовлетворяет всем разумным философским требованиям случайности, а значит, отвечает на основной вопрос, поставленный в этом разделе.

D. Существование случайных последовательностей. Как было показано, определение R3 слишком строгое в том смысле, что не существует удовлетворяющей ему последовательности, и в приведенных выше определениях R4-R6 предпринимались попытки сохранить существенные элементы определения R3. Для того чтобы показать, что определение R6 не чрезмерно ограничительно, все еще необходимо доказать, что последовательность, удовлетворяющая всем этим условиям, существует. Интуитивно мы совершенно правильно ощущаем, что это не проблема, так как мы верим, что истинно случайная последовательность существует и удовлетворяет определению R6, но доказательство действительно необходимо, чтобы показать, что определение состоятельно.

Интересный метод построения последовательностей, удовлетворяющих определению R5, найден А. Вальдом (А. Wald). Он начинается с построения простой 1-распределенной последовательности.

Лемма Т. Пусть последовательность действительных чисел (F„) определена следующим образом в терминах двоичной системы:

Vo =0, Vi = .1, V2 = .01, Уз = .11, Vi = .001,

Vn = .Cr...cil, есяи n = 2-bci2-i-b----bcr. (29)

Обозначим через /б1...б, множество всех действительных чисел в [0..1), которые имеют двоичное представление, начиная с O.bi... Ьг- Таким образом,

/бь..б. = [(O.bi... Ьг)2 .. (O.bi... br)2 + 2-0 (30)

.Тогда, есля i>{n) - число 14 в Ibi...br. при О < к < п, получим

р{п)/п - 2-\<1/п. (31)

Доказательство. Так как р(п) - число к, для которых /с mod 2 = (br-..6i)2, получим р(п) = t или -I-1, когда [п/2\ = t. Следовательно, и{п) - гг/2 < 1.

* По крайней мере, он сделал такое заявление, когда готовил этот материал в 1966 году.

Из (31) следует, что последовательность ([2V„j) - это равнораспределенная 2-ичная последовательность. Отсюда согласно теореме А получаем, что (К„) - равнораспределенная [О.. 1)-последовательность. Действительно, достаточно ясно, что (У„) настолько равнораспределена на [0.. 1), насколько это вообще возможно. (Чтобы получить дополнительную информацию о данной и родственных последовательностях, обратитесь к работам J. G. van der Corput, Ргос. Koninklijke Nederl. Akad. Wetenschappen 38 (1935), 813-821, 1058-1066; J. H. Halton, Numerische Math. 2 (1960), 84-90, 196; S. Haber, J. Research National Bur. Standards B70 (1966), 127-136; R. Bejian and H. Faure, Comptes Rendus Acad. Sci. Paris A285 (1977), 313-316; H. Faure, J. Number Theory 22 (1986), 4-20; S. Tezub, ACM Trans. Modeling and Сотр. Simul. 3 (1993), 99-107.

Л. Г. Рамшоу (L. H. Ramshaw) показал, что последовательность {фп mod 1) немного более равнораспределена, чем (У„) (см. J. Number Theory 13 (1981), 138-175).

Пусть сейчас TZi, TZ2, ... - бесконечное множество правил подпоследовательностей, и необходимо найти последовательность {U„), для которой все бесконечные подпоследовательности (f7„)7j равнораспределены.

Алгоритм W {Последовательность Вальда). Задана бесконечная последовательность правил подпоследовательностей Ti, 72, • • •, которая определяет подпоследовательности [О.. 1)-последовательностей рациональных чисел. Эта процедура определяет [О .. 1)-последовательность {Un)- Для вычисления требуется бесконечно много вспомогательных переменных C[ai,..., а], где г > 1 и = О или 1 для 1 < j < г. Вначале все эти переменные равны нулю. W1. [Инициализация п] Присвоить п 4- 0. W2. [Инициализация г.] Присвоить г 4- 1.

W3. [Проверка Лг] Если элемент [/„ должен принадлежать подпоследовательности, определенной Ti которая основана на значениях Uk для О < < п, присвоить Or 4- 1; иначе - присвоить 0.

W4. [Случай [ai,..., а] не окончен?] Если C[ai,..., а] < 3 • 4~\ перейти к шагу W6.

W5. [Увеличить г.] "Присвоить г 4- г -I-1 и возвратиться к шагу W3.

W6. [Присвоить Un] Увеличить значение C[ai,...,Ог] на 1, и пусть fc будет его

новым значением. Присвоить Un Vk, где Vjt определено в приведенной выше

лемме Т.

W7. [Увеличение п] Увеличить п на 1 и возвратиться к шагу W2.

Строго говоря, это не алгоритм, так как он не заканчивается, но мы, конечно, слегка преобразуем процедуру, чтобы он останавливал работу, когда п достигает заданного значения. Чтобы понять идею построения, выполните алгоритм вручную, заменяя число 3 4" шага W4 значением 2.

Алгоритм W не предназначен для получения случайных чисел на практике. Имеется в виду, что он имеет только теоретическое значение.

Теорема W. Пусть {Un) -последовательность рациональных чисел, определенная алгоритмом W, и пусть к - положительное целое число. Если подпоследовательность {Un)R-k бесконечна, то она 1-распределена.

Доказательство. Пусть A[ai,ar] означает подпоследовательность ([/„) (возможно пустую), включающую те элементы Un, которые для всех j <г принадлежат подпоследовательности {Un)R-j, если Oj = 1, и не принадлежат подпоследовательности {U„)TZj, если Oj ~ 0.

Достаточно доказать для всех г > 1 и всех пар двоичных чисел ai... Ог иЬх... Ьг, что Pv{U„ е hi...b,.) = 2" по отношению к подпоследовательности A[ai,... ,аг] всякий раз, когда последняя бесконечна (см. равенство (30)). Если г > к, для бесконечной последовательности {U„)TZk существует конечное объединение непересекающихся подпоследовательностей A[ai,..., а] для - I и Oj = О или 1 для 1 < j < j 7 - Из этого следует, что Pr(t/„ £ Ibi...b) = 2" по отношению к {U„)TZk (см. упр. 33). Этого достаточно, чтобы показать, что согласно теореме А последовательность 1-распределена.

Пусть B[ai,... ,аг] означает подпоследовательность (Un) для тех п, в которых C[ai,..., Or] увеличивается на единицу на шаге W6 алгоритма. Согласно алгоритму B[ai,.. .,аг] - конечная последовательность с самое большее 3 • элементами. За исключением конечного числа, все члены A[ai,... ,аг] являются членами подпоследовательностей B[ai,... ,аг, .. ,at], где Oj = О или 1 для г < j <t.

Предположим, что A[ai,...,ar] бесконечна, и пусть A[ai,...,ar] - {Us„), где So < «1 < «2 < • • • Если - большое целое число с 4 < 4 < < 4+\ логически вытекает, что число значений к < N, для которых Us принадлежит Ibi...br., равно (за исключением конечного множества элементов начальных подпоследовательностей)

Здесь т - число перечисленных выше подпоследовательностей B[ai,... ,at], в которых Us появляется для некоторых к < N, Nj - чисяо значений к с Us в соответствующей подпоследовательности и p(Nj) - число таких значений, которые также принадлежат Ibi...br.- Значит, согласно лемме *Г

piN)-2-N = u{Ni)~2-Ni + --- + piNm)-2-Nm\

<

u{Ni)-2--Ni ++ p{Nm)-2-N,

<m<l + 2 + A+--- + 2-+ < 2+.

Неравенство для m следует здесь нз того, что согласно сделанно.му выбору iV элемент С4д, принадлежит B[ai,...,«<] для некоторых t <q+\.

Мы доказали, что \v {N)IN - 2-- < 21+IN < 2/VN. I

Чтобы показать окончательно, что существуют последовательности, удовлетворяющие определению R5, сначала заметим, что, если ([/„) - [О.. 1)-последо-вательность рациональных чисел и если TZ - исчисляемое правило подпоследовательностей для Ь-ичной последовательности, TZ можно преобразовать в исчисляемое правило подпоследовательности TZ для (Un), полагая fn{x\,... ,Хп) в TV равным fn{\bxi\,... ,\Ьхп\) в TZ. Если [О.. 1)-последовательность {U„)TZ равно-распределена, значит, существует Ь-ичная последовательность ([bJ7„J)7. Сейчас множество всех исчисляемых правил подпоследовательностей для Ь-ичных последовательностей для всех значений b является счетным (так как возможно только счетное множество эффективных алгоритмов). Значит, они могут образовать