и можно удалить не возведенные в квадрат члены и, применяя (16), получить

ип, = £(£1 + Х, (23)

n=l 0<j<m

Используя неравенство

/г X 2 г

Ке«0 е«?

(см. упр. 1.2.3-30), находим, что

N+q ч 2

Также получим

N<n<N+q n=l

Подставив это неравенство в (24), получим

Данная формула справедлива всякий раз, когда q кратно т, и если мы устремим g -)• 00, то получим (17), что и завершает доказательство.

Более простое доказательство можно найти у Дж. В. С. Касселя (J. W. S. Cas-sels. Pacific J. Math. 2 (1952), 555-557).

В упр. 29 и 30 иллюстрируется нетривиальность этой теоремы и тот факт, что -распределенная последовательность имеет вероятности, отклоняющиеся от истинных вероятностей (т, т)-распределения, по существу, не более чем на l/y/q (см. (25)). Для доказательства теоремы необходима гипотеза о оо-распределении последовательности.

Используя теорему С, можно доказать, что оо-распределенная последовательность проходит критерий серий, критерий "максимум-", критерий конфликтов, критерий промежутков между днями рождений и критерий подпоследовательностей, о которых упоминалось в разделе 3.3.2. Нетрудно показать, что она также удовлетворяет критерию интервалов, покер-критерию и критерию монотонности (см. упр. 12-14). Критерий собирания купонов является значительно более трудным, но и его последовательность проходит (см. упр. 15 и 16).

Существование оо-распределенной последовательности достаточно простого вида гарантирует следующая теорема.

Теорема F. (Дж. Н. Франклин (J. N. Franklin).) [О.. 1)-последовательность [/о, Ui,U2, ... с

Un = 61" mod 1 (26)

является оо-распределенной для почти всех действительных чисел 9 > 1. Другими словами, множество

{9 \ 9 > 1 и (26) не оо-распределено}

имеет меру нуль.

Доказательство этой теоремы и некоторые обобщения приведены в Math. Сотр. 17 (1963), 28-59. I

Франклин показал, что 9 должно быть трансцендентным числом для того, чтобы (26) была оо-распределенной. Раньше, в 60-е годы, степени (тг" mod 1) получали в результате трудоемких вычислений, использующих многократную точность для п < 10000, и 35 самых старших двоичных разрядов этих чисел, оставленных в файле на диске, успешно использовались как источник равномерно распределенных случайных чисел. Согласно теореме F вероятность того, что степени (тг" mod 1) оо-распределены, равна 1, однако существует несчетное множество действительных чисел, поэтому теорема не дает информации о том, действительно ли последовательность для тг имеет оо-распределение. Можно совершенно спокойно держать пари, что никто при нашей жизни не докажет, что именно данная последовательность не является оо-распределенной, хотя это и возможно. Руководствуясь такими соображениями, он может законно удивиться, если окажется, что существует какая-либо оо-распределенная последовательность: существует ли алгоритм вычисления действительных чисел Un для всех п > О, такой, что последовательность (Un) оо-распределена? Ответ - "Да", как показано, например, в работе D. Е. Knuth, BIT 5 (1965), 246-250. Построенная последовательность полностью состоит из рациональных чисел. На самом деле каждое число Un имеет ограниченное представление в двоичной системе счисления. Другое построение определенной оо-распределенной последовательности, отчасти более сложное, чем построение предыдущей последовательности, вытекает из теоремы W, приведенной ниже. (См. также Н. М. Коробов, Изв. Акад. наук СССР 20 (1956), 649-660.)

С. Эквивалентно ли понятие оо-распределенности понятию случайности?

Принимая во внимание все теоретические результаты относительно оо-распреде-ленных последовательностей, можно быть уверенным в одном: понятие "оо-распределенная последовательность" является важным в математике. Кроме того, кажется очевидным, что интуитивное понятие случайности можно формализовать следующим образом.

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

Мы видели, что последовательности, удовлетворяющие этому определению, удовлетворяют всем статистическим критериям раздела 3.3.2 и многим другим.

Попытаемся объективно критиковать это определение. Прежде всего, всякая ли "поистине случайная" последовательность оо-распределена? Существует бесконечное число последовательностей Uq, Ui, ... действительных чисел между нулем и единицей. Если генератор истинно случайных чисел выдает значения Uo, Ui, ..., то любую из возможных последовательностей можно рассматривать как в равной степени подходящую и некоторые из последовательностей (на самом деле бессчетное количество) даже не равнораспределены. С другой стороны, используя любое разумное определение вероятности на этом пространстве всех возможных последовательностей, можно прийти к заключению, что случайная последовательность является оо-распределенной с вероятностью 1. Итак, получена следующая формализация определения случайности Франклина, приведенного в начале этого раздела.

Определение R2. [О.. 1)-последовательность ([/„) называется случайной, если всякий раз, когда Р является таким свойством, что P((V„)) выполняется с вероятностью 1 для последовательности (V„) независимых случайных равномерно распределенных величин, Р( ([/„)) также выполняется.

Можно ли предположить, что определение R1 эквивалентно определению R2? Давайте выдвинем возможные возражения против определения R1 и проанализируем их.

Во-первых, определение R1 распространяется только на предельные свойства последовательностей при п -)• оо. Существуют оо-распределенные последовательности, в которых первый миллион элементов - нули. Можно ли такие последовательности рассматривать как случайные?

Это возражение не очень существенно. Если е - любое положительное число, то нет причины каждому элементу последовательности из первого миллиона не быть меньще е. С вероятностью 1 истинно случайнаяпоследовательность содержит бесконечно много рядов в миллион последовательных элементов, меньших е, так почему это не может произойти в начале последовательности?

Во-вторых, рассмотрим определение R2, и пусть Р - такое свойство, что все элементы последовательности различны; Р справедливо с вероятностью 1, поэтому любая последовательность с миллионом нулей не является случайной по этому критерию.

Пусть Р - такое свойство, что нет элемента последовательности, равного нулю. Р снова справедливо с вероятностью 1, поэтому по определению R2 любая последовательность с нулевым элементом не случайна. Вообще говоря, пусть хо - любое фиксированное число между нулем и единицей и пусть Р - такое свойство: нет элемента последовательности, равного хо- Из определения R2 сейчас следует, что нет случайной последовательности, которая может содержать элемент xq! Можно доказать, что не существует последовательности, удовлетворяющей условиям определения R2. (Если Щ, Ui, ... - такая последовательность, то выберем хо = Uo-)

Следовательно, если R1 - слишком слабое определение, то R2 является, несомненно, слишком строгим. "Правильное" определение должно быть менее строгим, чем R2. В действительности мы не показали, что определение R1 слишком слабое, поэтому продолжим исследование. Как упоминалось выше, оо-распределенная последовательность рациональных чисел построена. (В самом деле, это не так уди-