*3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

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

Шио, Ui, U2, ... (1)

действительных чисел в области О < [/„ < 1. Эти последовательности назывались случайными, даже несмотря на то, что они совершенно детерминированные по характеру. Чтобы оправдать использование этой терминологии, мы утверждали, что числа "ведут себя так, рсак будто они действительно случайны". Такое утверждение может быть удовлетворительным для практических целей (в настоящее время), но это шаг в сторону очень важного методического и теоретического вопроса "Что именно подразумевается под случайным поведением?". Необходимо количественное определение. Нежелательно говорить о понятиях, которых мы на самом деле не понимаем, главным образом потому, что, по-видимому, можно сделать много парадоксальных утверждений, касающихся случайных чисел.

Теория вероятностей и математическая статистика тщательно избегают обсуждения спорных вопросов. Они воздерживаются от безусловных утверждений и вместо этого выражают все в терминах вероятностей, связанных с последовательностью случайных событий. Аксиомы теории вероятностей установлены так, что теоретические вероятности можно легко вычислить, но о том, что на самом деле означает "вероятность" или как это понятие можно разумно применить к действительности, ничего не говорится. В книге Probability, Statistics, and Truth (New York: Macmillan, 1957), P. фон Мизес (R. von Mises) подробно обсуждает эту ситуацию и предлагает следуюи;ую точку зрения: определение вероятностей зависит от того, какое используется определение случайных последовательностей.

Процитируем здесь несколько утверждений двух авторов, комментировавших эту тему.

Д. Г. Лехмер (D. Н. Lehmer) (1951): "Случайная последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят оиределенное количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность".

Д. Н. Франклин (J. N. Franklin) (1962): "Последовательность (1) случайна, если она обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок случайных равномерно распределенных величин".

Утверждение Франклина, по существу, обобщает высказывание Лехмера о том, что последовательность должна удовлетворять всем статистическим критериям. Его определение не вполне точное, и позже мы убедимся, что разумное объяснение его утверждения приводит к заключению о том, что не существует такого объекта, как случайная последовательность! Так давайте начнем с менее ограничительного утверждения Лехмера и попытаемся сделать его точным. Что нам действительно необходимо - так это сравнительно короткий перечень математических свойств, каждое из которых удовлетворяет нашим интуитивным представлениям о случайной

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

Пусть и и г; - действительные числа, О < и < v < 1. Если U - случайная величина, равномерно распределенная .между О и 1, вероятность того, что и <U <v, равна V -и. Например, вероятность, что <U < , равна . Как можно выразить это свойство единственного числа U свойством бесконечной последовательности Uo, Ui, U2, ...? Очевидный ответ - подсчитать, сколько раз [/„ находится между и и и, и сказать, что среднее число попаданий в этот интервал равно v - и. Наше интуитивное понятие вероятности основано, таким образом, на частоте появления события.

Точнее, пусть z(n) - число значений j, О < j < п, таких, что и < Uj < v, и отношением и{п)1п необходимо приблизить значение v - и, когда п стремится к бесконечности:

lim = .-n. (2)

п-юо п

Если это условие вьшолняется для всех вариантов и и v, говорят, что последовательность равнораспределена.

Пусть утверждение 5(п) относится и к целому числу п, и к последовательности Uo, Ui, например 5(п) может быть приведенным выше утверждением "и < и„ < v". Можно обобщить понятие, используемое в предыд}щем разделе, чтобы определить вероятность того, что 5(п) справедливо по отношению к некоторой бесконечной последовательности.

Определение А. Пусть {п) - чисяо значений j, О < j < п, таких, что S(j) верно. Мы говорим, что S{n) выполняется с вероятностью Л, если предел i{n)/n, когда п стремится к бесконечности, равен Л. А именно: Рг(5(п)) = Л, если Ит„ юог(")/" = А.

В терминах этой записи последовательность Uo, Ui, ... равнораспределена тогда и только тогда, когда Рг(ы < Un < v) = v - и для всех действительных чисел и, v при О < и < V < 1.

Последовательность может быть равнораспределена, даже если она не случайна. Например, если Uo, Ui, ... и Vq-, Vi, ... - равнораспределенные последовательности, то нетрудно показать, что последовательность

Wo,W„W2,W3,... = IUo, + Fo, t/b i + ... (3)

также равнораспределена, поскольку подпоследовательность Uo,Wi, равно-распределена между О и i, в то время как промежуточные члены Ч- 2 К), + , • равнораспределены между и 1. Но в последовательности Wj, j = 0,1,2,..., значения, меньшие , всегда следуют за значениями, большими или равными. соответственно. Значит, последовательность не случайна согласно любому разумному определению. Необходимы свойства, которые сильнее равнораспределенности.

Естественная возможность обобщить свойство равнораспределенности, которое позволяет развеять сомнения предыдущего раздела, - рассмотреть смежные пары

членов нашей последовательности. Можно потребовать, чтобы последовательность удовлетворяла условиям

Pr(wi <Un <Vi и U2 < Un+l < V2) = (Il - Ui)(v2 - щ) (4)

для любых членов ui, vi, «2, V2 при О < Mi < < 1, О < Мг < i2 < 1. И вообще, для любого положительного целого к можно потребовать, чтобы наша последовательность была к-распределенной в смысле определения В.

Определение В. Говорят, что последовательность (1) будет к-распределетюп, если

Рг(м1 <U„<vi, Uk< Un+k-i < Vk) = {vi -ui)... [vk - Uk) (5)

для всех вариантов действительных чисел Uj, Vj при О < Uj < Vj < 1 для 1 < j < к.

Равнораспределенная последовательность является 1-распределенной. Заметим, что, если к > 1, /с-распределенная последовательность всегда является (к - 1)-распределенной, так как в (5) можно положить Uk = О и Vk = 1. Таким образом, в частности, любая последовательность, о которой известно, что она 4-распределена, должна быть также 3- и 2-распределенной. Можно определить наибольшее к, для которого данная последовательность является /с-распределенной, что приведет нас к формулировке более сильного свойства.

Определение С. Говорят, что последовательность оо-распределена, если она А;-распределена для всех положительных целых к.

До сих пор мы рассматривали [О.. 1)-последовательности, т. е. последовательности действительных чисел, лежащих между О и 1. Такие же понятия при.ме-няются к целочисленным последовательностям. Говорят, что последовательность (Хп) = Хо, Xi, Х2, ... является Ь-ичной последовательностью, если каждый член последовательности Х„ является одним из целых чисел О, 1, 6-1. Таким образом, 2-ичная (бинарная) последовательность - это последовательность нулей и единиц.

Определим также Ь-ичное число, состоящее из к цифр, как строку к целых чисел Х1Х2... Хк, где Q <Xj <Ь для \ < j <к.

Определение D. Говорят, что Ь-ичная последовательность является к-распределенной, если

Рг(Х„Х„+1...Х„+, 1 =XiX2...X,) - 1/6= (6)

для всех Ь-ичных чисел Х1Х2... х.

Из этого определения ясно, что если Uo, U\, ... является /с-распределенной последовательностью [0..1), то последовательность \bLo\, [bU\\, ... является -распределенной 6-ичной последовательностью. (Еати положить Uj = Xj/b, Vj - [xj ->г I)lb, Хп = [bUn\, TO равенство (5) превратится в ]1авенство (6).) Более того, каждая /с-распределенная 6-ичная последовательность является также {к - 1)-распределенпой, если к > 1: мы складываем вероятности л.ля 6-ичных чисел

XI . . . Х< 1 О, Xi . . . Х 1 1, . . . , Xi . . . X;t i (6 - 1), чтобы ПОЛ3ЧИ гь Pr(X„...A„+fc-2 = Xi...X, i) = l/6*