вительно; см. упр. 18.) Почти все действительные числа иррациональны. Возможно, следовало бы потребовать, чтобы для случайной последовательности выполнялось

Рг([/„ рациональное) = 0.

Из определения равнораспределенности (см. равенство (2)) следует, что Рг(ы <Un<v) = V-U. Существует очевидный способ обобщения этого определения, используя теорию меры: "если 5 С [О.. 1) - множество меры д, то

Рг([/„ €S)=p (27)

для всех случайных последовательностей {Un)" В частности, если 5 - множество рациональных чисел, то оно имеет меру нуль; значит, нет последовательности рациональных чисел, равнораспределенных в этом обобщенном смысле. Разумно ожидать, что теорема В может распространяться на интегрирование по Лебегу вместо интегрирования по Риману, если оговорено свойство (27). Однако мы снова найдем, что определение (27) слишком строгое, так как нет последовательностей, удовлетворяющих этому свойству. Если Uq, Ui, ... - любая последовательность, множество 5 = [Uq, Ui,...} есть множество меры нуль. Кроме того, Рг([/„ € 5) = 1. Поэтому в силу тех же аргументов, из-за которых рациональные числа были исключены из случайных последовательностей, можно исключить все случайные последовательности.

До сих пор определение R1 можно было считать приемлемым. Однако существует несколько совершенно обоснованных возражений по этому поводу. Например, если имеется случайная в интуитивном смысле последовательность, то бесконечная подпоследовательность

Uo,Ui,U,,U9,...,Un,... (28)

также должна быть случайной. Это не всегда верно для оо-распределенных последовательностей. В самом деле, если взять любую оо-распределенную последовательность и присвоить [/„2 <- О для всех п, количество Uk{n), появляющихся в критерии fc-распределенности, изменится самое большее на у/п. Значит, отношение vk{n)/n не изменится. Таким образом, определение R1 не удовлетворяет этому критерию случайности.

Можно было бы усилить R1 следующим образом.

Определение R3. [О.. 1)-последовательность называется случайной, если каждая ее бесконечная подпоследовательность является оо-распределенной.

Однако еще раз определение вышло очень строгим; любая равнораспределенная последовательность ([/„) имеет монотонную подпоследовательность с Uso < Us < [/..<•••

Секрет состоит в том, чтобы ограничиться подпоследовательностями, при построении которых можно было бы заранее сказать, принадлежит ли заданное [/„ этой подпоследовательности. Предлагаем следующее определение.

Определение R4. [О .. 1)-последовательность (Un) называется случайной, если для любого эффективного алгоритма, точно определяющего бесконечную последовательность различных неотрицательных целых чисел s„ для п > О, подпоследова-

тельность и so, Us-,, Us2, , соответствующая этому алгоритму, является оо-распределенной.

Алгоритм, относящийся к определению R4, - это эффективная процедура вычисления s„ при заданном п (см. обсуждение в разделе 1.1). Так, например, последовательность (тг" mod 1) не удовлетворяет R4, поскольку она или не равно-распределена, или существует эффективный алгоритм, определяющий бесконечную подпоследовательность s„ с (тг*" mod 1) < (тг mod 1) < (тг* mod 1) < • • •. Точно так же никакая явно определенная последовательность не может удовлетворять определению R4. Это справедливо, если согласиться с тем, что никакая явно определенная последовательность не является случайной. Судя по ее виду, явная последовательность (в" mod 1) на самом деле, однако, удовлетворяет определению R4 для почти всех действительных чисел 9 > 1; это не противоречие, так как почти все 9 не могут быть вычислены алгоритмом. Ж. Ф. Коксма (J. F. Koksma) доказал, что (й"" mod 1) является 1-распределенной для почти всех > 1, если (s„) - любая последовательность различных положительных целых чисел [Compositio Math. 2 (1935), 250-258]. Г. Нидеррейтер (Н. Niederreiter) и Р. Ф. Тичи (R. F. Tichy) усилили теорему Коксма, заменив "1-распределенность" "оо-распределенностью" [Mathematika 32 (1985), 26-32]. Только счетное множество последовательностей (s„) эффективно определимо; значит, (й" mod 1) почти всегда удовлетворяет R4.

Определение R4 более строгое, чем определение R1, но все еще можно утверждать, что определение R4 слишком слабое. Пусть, например, (С/„) - истинно случайная последовательность. Определим подпоследовательность ([/«„) следующим образом: so = О и, если п > О, s„ - наименьшее целое число > п, для которого все [/«„-ь Ug„-2, Us-n меньше . Таким образом мы определили подпоследовательность значений, следующих за первой серией п значений, меньших . Предположим, что [/„ < соответствует выпадению "герба" при бросании монеты. Игроки склонны считать, что длинный ряд "гербов" предполагает, что появление "решки" становится более вероятным, если монета не поддельная., В это.м случае подпоследовательность ([/«„) определяет систему азартной игры для человека, который делает п-ю ставку на первую решку, следующую после серии из п "гербов." Игрок, возможно, думает, что Рг([/«„ > ) больше , но, конечно, в истинной случайной последовательности ([/«„) будет совершенно случайным. Нет системы азартных игр, которая всегда приводит к победе! Определение R4 ничего не говорит о подпоследовательности, формируемой в соответствии с такой системой азартных игр; так что, по-видимому, необходимо нечто большее.

Пусть определено "правило подпоследовательности" 11 как бесконечной последовательности функций {fn{xi,.. - tXn)), где для п > О, /„ - функция п переменных и значение /„(хх,... ,а;„) равно либо О, либо 1. Здесь xi, Хп - элементы некоторого множества 5. (Таким образом, в данном случае /о - это постоянная функция, равная либо О, либо 1.) Правило подпоследовательности TZ определяет подпоследовательность бесконечной последовательности (Хп) элементов 5 следующим образом: п-й член Х„ принадлежит подпоследовательности {X„}TZ тогда и только тогда, когда fn (Хо ,Xi,..., Хп-1) = 1 Заметим, что подпоследовательность

{Xn)TZ, определенная таким образом, необязательно бесконечна; фактически в ней вообще может не быть элементов.

Например, подпоследовательность азартного игрока, описанная выше, соответствует такому правилу подпоследовательности: /о = 1 и для п > О, /„(2:1,..., Хп) = 1 тогда и только тогда, когда найдется некоторое к, О < к < п, такое, что к последовательных чисел Хт, Хт-1, . • •, Хт-к+1 все будут < , когда m = п, но не когда к < тп < п.

Правило подпоследовательностей TZ называют исчислимым, если существует эффективный алгоритм, определяющий значение /„(xi,... ,х„), когда п и xi, ..., х„ заданы на входе. При попытке определить случайность лучше ограничиться исчислимыми правилами подпоследовательностей, когда пытаемся определить случайность, чтобы не получить чрезмерно ограничительное определение, подобное R3. Но эффективный алгоритм нельзя рассматривать с произвольными входными действительными числами. Например, если действительное число х точно определено бесконечным разложением в десятичной системе счисления, то не существует алгоритма для того, чтобы определить, будет ли х < , так как для этого нужно исследовать все цифры числа 0.333 Поэтому исчислимое правило подпоследовательностей неприменимо ко всем [О .. 1)-последовательностям и служит основой для следующего определения Ь-ичных последовательностей.

Определение R5. Ь-хгчная последовательность называется случайной, если каждая бесконечная подпоследовательность, определенная исчислимым правилом подпоследовательностей, является 1-распределенной.

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

Заметим, что определение R5 говорит только об 1-распределении, а не о оо-распределении. Интересно проверить, что это может быть сделано без потери общности. Очевидно, можно определить исчислимое правило подпоследовательности TZ{ai...ak) следующим образом при любом заданном Ь-ичном числе ai...ak: пусть /n(xi,... ,х„) = 1 тогда и только тогда, когда п > к - 1 и Xn-k+i = «1, • • •, х„ 1 = ак-1, х„ = uk. Если (Хп) является /с-распределенной Ь-ичной последовательностью, то правило TZ{ai... а), с помощью которого выбирается подпоследовательность, содержащая точно следующие за появлением ai.. .Uk члены, определяет бесконечную подпоследовательность, и, если эта подпоследовательность 1-распре-делена, каждая из строк ai... afca+i размерности {к + 1) для О < Пк+г < Ъ появляется с вероятность 1/Ь*+ в (Х„). Таким образом, индукцией по к можно доказать, что последовательность, удовлетворяющая определению R5, является /с-распределенной для всех к. Подобным образом, рассматривая "композицию" правил подпоследовательностей, получаем: если Tli определяет бесконечную подпоследовательность {Хп)Т1\, то можно определить правило подпоследовательности 7i72, для которого (X„)7i72 = ((An)7i)72, и найти, что все подпоследовательности, рассматриваемые в определении R5, оо-распределенные (см. упр. 32).

Факт, что оо-распределение следует из определения R5 как очень частный случай, ободряет, и это хороший признак того, что можно, наконец, найти требуемое определение случайности. Но, увы, это все еще проблема. Не ясно, почему последовательность, удовлетворяющая определению R5, должна удовлетворять определе-