(Вероятности для несовместных событий аддитивны; см. упр. 5.) Следовательно, естественно ввести понятие оо-распределенных Ь-ичных последовательностей, как в определении С.

Представление положительных действительных чисел в системе с основанием b можно рассматривать как 6-ичную последовательность, например тг соответствует 10-ичной последовательности 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, .... Предполагается, что эта последовательность оо-распределенная, но никто, однако, не в состоянии даже доказать, что она является точно 1-распределенной.

Проанализируем это понятие более подробно для случая, когда к равно миллиону. Бинарная последовательность, являющаяся 1 ООО 000-распределенной, может содержать серию из миллиона нулей! Аналогично [О.. 1)-последовательность, являющаяся 1 ООО 000-распределенной, может содержать миллион последовательных значений, каждое из которых меньше . Правда, в среднем такое случается только в одной из 2°°°°°° ситуаций, но это действительно происходит. Действительно, данный феномен встречается в любой поистине случайной последовательности. Мы используем пока наше интуитивное понятие "истинная случайность". Каждый может легко себе представить, что такая ситуация будет иметь значительные последствия, если такое множество из миллиона "истинно случайных" чисел использовать в эксперименте компьютерного моделирования. Это будет хорошим поводом для того, чтобы вызвать недовольство генератором случайных чисел. Однако при наличии последовательности чисел, которые никогда не пробегают миллион последовательных Uj, меньших i, последовательность будет не случайной и она не будет подходящим источником чисел для других предполагаемых применений, использующих на входе крайне длинные блоки Uj. В итоге истинно случайная последовательность будет проявлять локальную "неслучайность" . Локальная "неслучайность" необходима в одних применениях, но она гибельна в других. Можно сделать вывод, что нет последовательности "случайных" чисел, которую можно было бы использовать в любом случае.

В подобном духе каждый может утверждать, что невоз.можно решить, будет ли конечная последовательность случайной; любая конкретная последовательность ничем не отлинается от любой другой. Эти факты действительно представляют собой камни преткновения всякий раз, когда необходимо дать полезное определение случайности, но они не являются истинной причиной смятения. Все еще можно сформулировать такое определение случайности бесконечной последовательности действительных чисел, чтобы соответствующая теория (рассмотренная должным образом) много дала для понимания обычных конечных последовательностей рациональных чисел, которые на самом деле генерируются на компьютере. Более того, ниже в этом разделе будет показано, что существует несколько внушающих доверие определений случайности конечных последовательностей.

В. оо-распределенные последовательности. Кратко рассмотрим теорию оо-распределенных последовательностей. Чтобы описать ее адекватно, понадобится немного высшей математики, поэтому в остальной части этого раздела предполагается, что читатель знаком с понятиями, необходимыми для понимания дальнейшего материала.

Во-первых, нужно обобщить определение А, так как фигурирующий в нем предел не существует для всех последовательностей. Определим

Р?(5(п)) = limsup Рг(5(п)) = liminf (7)

П-+00 IT- П-+00 п

Тогда вероятность Рг(5(п)) является общим значением Рг(5(п)) и Рг(5(п)) (если она существует).

Мы видели, что -распределенная [О.. 1)-последовательность приводит к fc-pac-пределенной Ь-ичной последовательности, если U заменить [bU\. Наша теорема показывает, что обратное утверждение также справедливо.

Теорема А. Пусть ([/„) = Uq, Ui, U2, ... - [О.. 1)-последовательность. Если последовательность

{[bjUn\) = [bjUo\, [bjUi\, [bjU2\, ...

является к-распределенноп bj-пчной последовательностью для любого bj из бесконечной последовательности целых чисел 1 < 61 < 62 < 63 < •, то исходная последовательность (Un) к-распределенная.

В качестве примера предположим, что bj = 2К Последовательность [2-[/oj! [2-[7iJ,... является, по существу, последовательностью первых j двоичных разрядов бинарного представления Uo,Ui, ... . Если все эти последовательности целых чисел fc-распределены в смысле определения D, то последовательность действительных чисел Uq, Ui, ... также должна быть -распределенной в смысле определения В.

Доказательство. Если последовательность [ЬЩ], [bUi\, ... fc-распределена, то с помощью сложения вероятностей получим, что (5) выполняется всякий раз, когда каждое Uj и Vj - рациональные числа со знаменателем Ь. Предположим, что Uj, Vj - любые действительные числа, и пусть uj, vj - ра11иональные числа со знаменателем Ь, такие, что

uj < Uj < uj -f- 1/6, vj < Vj < vj + 1/6.

Пусть 5(n) - утверждение, что ui < U„ < vi, ..., Uk < Un+k-i < i>k. Получим

P?(5(n)) < Pr(ui <U„<v, + l, uk< Un+k-i < vk + I)

= iv[-u, + l)...{vk-u, + l);

Pr(5(n)) > Pr(«; +-<U„<vi, ...,uk + l< U„+k-i < vk)

= {vi-u,-l)...{vk-uk-l).

Сейчас \{vj - uj ± 1/6) - (vj - Uj)\ < 2/6. Так как наше неравенство выполняется для всех b-bj и так как bj -> 00 при j -> 00, получим

(vi -щ)... (vk - Uk) < Pr(5(n)) < P?(5(n)) < (vi -щ)... (vk - Uk). I

Следующая теорема является основным орудием для доказательства различных утверждений о fc-распределенных последовательностях.

Теорема В. Предположим, что (Un) - к-распределенная [О.. 1)-последователь-нрсть, и пусть f{xi,x2,. . ,Xk) - интегрируемая по Риману функция к переменных. Тогда

lim - V f{Uj,Uj+i,...,Uj+k-i)= •• / f{xi,X2,...,Xk)dxi...dxk. W " 0<><n Jo Jo

Доказательство. Из определения -распределенной последовательности следует, что этот результат справедлив в частном случае, когда

f{xi,...,Xk) = [ui<xi<vi, Uk<Xk<Vk], (9)

для некоторых постоянных ui, ы, ..., Uk, Vk- Более того, (8) выполняется каждый раз, когда / = ai/i -f- аг/г -f- • • • -f- am/m и каждая функция fj является функцией вида (9). Другими словами, (8) выполняется каждый раз, когда / является "ступенчатой функцией", полученной путем разбиения единичного fc-мерного куба на подкубы, грани которых параллельны оси координат, и / принимает постоянные значения на каждом подкубе.

Пусть / - любая интегрируемая по Риману функция. Если е - любое положительное число, то (по определению интегрируемости по Риману) получим, что существуют ступенчатые функции f vi f, такие, что f {xi,.. .,Хк) < fii,.. .,Хк) < f{xi,..., Хк), и такие, что разность интегралов / и / меньше е. Поэтому (8) вьшолняется для / и /. И поскольку

i l{Uj,...,Uj+k-i)<l Е fiUj,...,Uj+k-i)

0<j<n 0<j<n

E 7iUj,...,Uj+k-i),

0<j<n >

можно заключить, что (8) верно также для /.

Теорема В может применяться, например, в критерии перестановок из раздела 3.3.2. Пусть {pi,p2, ,Рк) - любая перестановка чисел {1,2,..., fc}. Покажем, что

Рг([/„+р, 1 < Un+p,-i < < Un+p,-i) = 1/fc!. (10)

Для доказательства предположим, что последовательность (Un) fc-распределена и пусть

f{Xi ,...,Хк) = [Хр, < < • • • < XpJ.

Имеем

Рг([/„+р, 1 < Un+p,-l < < Un+p,-l)

= [[ f{xi,...,Xk)dxi...dxk JO Jo

= lo "Чо -Jo 4o -i-

Следствие P. Если [0 .. 1)-последовательность к-распределена, то она удовлетворяет критерию перестановок порядка к в смысле равенства (10).