AOP_Tom2 (1021737), страница 48
Текст из файла (страница 48)
У/п = из(П)/П И НУЖНО ДОКаэатЬ, ЧтО 1 !)ш узп — — —,. и-«сю " гпбп' (16) Во-первых«известно, что 1 1пп (УО + У1 + . + У) -Вп) = — , «« — «пь (16) так как последовательность т-распределена. Согласно лемме Е и равенству (16) теорема доказана, если показать., что ппзапр(УО +У1 +'''+У)п« вЂ” 1)п) < и-«пп «пЬОп« Однако зто неравенство не очевидно, необходимо несколько деликатных маневров, прежде чем можно будет его доказать. Пусть О кратно тп. Рассмотрим (18) Это число появлений пар к-в на позициях р1 и ря, для которых и — О < р, < ре < и и рз — р1 кратно гп.
Рассмотрим сумму п=1 (Ч-«п/)Д (26+У) >5 > ~ (У вЂ” 1)д Ю. (20) О<«Ч/ О<1<О/и« Так как начальная последовательность является у-распределенной« то 1 1 1пп — 11 1(/)/) = —, и,, /)1 '" беп (21) для всех й О < 1 < д/п1«и, следовательно, из (20) получаем 51г ~ Π— т1 1'пп — = У и « /У ~ /1О«' О<1<О/т (22) 2тбтп« Из этих равенств после нескольких преобразований получим утверждение теоремы.
По определению 25м = ~~1 ~~«((1«1(п) — 1«1(п — О)) — (и1(11) — и (и — О))), =1 О<1< Каждое появление пары х-в, встречаю1цейся на позициях р1 и рт с р1 < р«< р1+ д« где рт — р1 кратно гп н р1 < /У, учитывается точно р, + Π— рт раз в общей сумме 5О (т. е. когда рт < и < р, + д)«а такие пары, которые появляются на позициях р1 ~ ре С /У < р1 < Ре < Х+ О, уЧитЫваются тачна /««1 + Π— рз Раз. Пусть 4(п) — число пар х, встречающихся на позициях р1 и ре с р1 +1 = рт < и. Приведенный выше анализ показывает, что и можно удалить не возведенные в квадрат члены и, применяя (16), получить 21ч я(Ч вЂ” гп) Ч !пп +— и-кв Х пзбз'л Ь'" ' (23) где хч.д Тм = ~~~ ~~~ (и (и) — и (и — д)) .
Используя неравенство (см. упр. 1.2.3 — 30), находим, что !ппэцр ~~~ ', ( '~ (и,(п) — и,(п — д))) <, + — „,. (24) .-~- о<1<,.' ". Также получим 4 и!(Х) < ~ ~и (и) = ~~~ (и (п) — и.(п — 4)) < дыу(Х+ 9). л=1 Подставив зто неравенство в (24), получим 'лл О<1< (25) Данная формула справедлива всякий раз, когда 4 кратно т, и если мы устремим д — 1 ос, то получим (17), что и завершает доказательство. Более простое доказательство можно найти у Дж. В. С.
Касселя (л. Ж. Я. Савве!э, Рас1бс Х Ма15. 2 (1952), 555 — 557). 1 В упр. 29 и 30 иллюстрируется нетривиальность этой теоремы и тот факт, что д-распределенная последовательность имеет вероятности, отклоняющиеся от истинных вероятностей (гп, ьп)-распределения, по существу, не более чем на, 1/ Д (см. (25)). Для доказательства теоремы необходима, гипотеза о оо-распределении последовательности. Используя теорему С, можно доказать, что оо-распределенная последовательность проходит критерий серий, критерий "максимум-1", критерий конфликтов, критерий промежутков между днями рождений и критерий подпоследовательностей, о которых упоминалось в разделе 3.3.2. Нетрудно показать, что она также удовлетворяет критерию интервалов, покер-критерию и критерию монотонности (см. упр.
12 — 14). Критерий собирания купонов является значительно более трудным, но и его последовательность проходит (см. упр. 15 и 16). Существование ос-распределенной последовательности достаточно простого вида гарантирует следующая теорема. Теорема Е. (Дж. Н. Франклин (3. Х. РгапИш),) (0..1)-последовательность Г>а, с>1 >>э .
с Г?„= йв 61 (26) является ос-распределенной для почти всех действительных чисел 6 > 1. Другпмн словамп, множество (6 ~ 6 > 1 и (26) не оо-распределено) имеет меру нуль. Доказательство этой теоремы и некоторые обобщения приведены в Май. Сош1>. 17 (1963), 23-59. 1 Франклин показал, что д должно быть трансцендентным числом для того, чтобы (26) была оо-распределенной.
Раныпе, в 60-е годы, степени (к" шой 1) получали в результате трудоемких вычислений, использующих многократную точность для и < 10000, и 35 самых старших двоичных разрядов этих чисел, оставленных в файле на диске, успешно использовались как источник равномерно распределенных случайных чисел. Согласно теореме Е вероятность того, что степени (к" пю61) оо-распределены, равна 1, однако существует несчетное множество действительных чисел, поэтому теорема не дает информации о том, действительно ли последовательность для к имеет оо-распределение.
Можно совершенно спокойно держать пари, что никто при нашей жизни не дакаэ>сеп>, что именно данная последовательность не является со-распределенной, хотя зто и возможно. Руководствуясь такими соображениями, он может законно удивиться, если окажется, что существует какая- либо оо-распределенная последовательность: существует лп алгоритм вычисления действительных чисел 1 „для всех и > О, такой, что последовательность (б'„) оо-распределена? Ответ — "Да", как показано, например, в работе О.
Е. Кппс1>, В1Т Б (1965), 246-250. Построенная последовательность полностью состоит из рациональных чисел. На самом деле каждое число С'„имеет ограниченное представление в двоичной системе счисления. Другое построение определенной оо-распределенной последовательности, отчасти более сложное, чем построение предыдущей последовательности, вытекает из теоремы Ж, приведенной ниже. (См. также Н. М.
Коробов, Изв. Акад. наук СССР 20 (1956), 649-660.) С. Эквивалентно ли понятие оо-распределенности понятию случайности? Принимая во внимание все теоретические результаты относительно оо-распределенных последовательностей, можно быть уверенным в одном: понятие "оо-распределенная последовательность" является важным в математике. Кроме того, кажется очевидным, что интуитивное понятие случайности можно формализовать следующим образом. Определение К1. (О .. 1)-последовательность называется случайной, если она яв- ляется оо-распределенной. Мы видели, что последовательности, удовлетворяющие этому определению, удовле- творяют всем статистическим критериям раздела 3.3.2 и многим другим.
Попытаемся обьективно критиковать это определение. Прежде всего, всякая ли "поистине случайная" последовательность ао-распределена? Существует бесконечное число последовательностей Ьо, Пы ... действительных чисел между нулем и единицей. Если генератор истинно случайных чисел выдает значения 1?о, Гм ..., то любую из возможных последовательностей можно рассматривать как в равной степени подходящую и некоторые из последовательностей (па самом деле бессчетное количество) даже не равнораспределены. С другой стороны, используя любое разумное определение вероятности на этом пространстве всех возможных последовательностей, можно прийти к заключению, что случайная последовательность является ~и-распределенной с еероятиностью б Итак, получена, следующая формализация определения случайности Франклина, приведенного в начале этого раздела.
Определение К2. [0..1)-последовательность (Вп) назьшается случайной, если всякий раз, когда Р является таким свойством, что Р((1о)) выполняется с яе; раятностью 1 для последовательности (1'„) независимых случайных равномерно распределенных величин, Р((П,)) также выполняется. Можно ли предположить, что определение К1 эквивалентно определению К2? Давайте выдвинем возможные возражения против определения К1 и проанализируем их. Во-первых, определение К1 распространяется только на предельные свойства последовательностей при и †> оо. Существуют со-распределенные последовательности, в которых первый миллион элементов — нули.
Можно ли такие последовательности рассматривать как случайные? Это возражение не очень существенно. Если е — любое положительное число, то нет причины каждому элементу последовательности из первого миллиона не быть меньше е. С вероятностью 1 истинно случайная'последовательность содержит бесконечно много рядов в миллион последовательных элементов, меньших е, так почему зто не может произойти в начале последовательности? Во-вторых, рассмотрим определение В.2, и пусть Р— такое свойство, что все элементы последовательности различны; Р справедливо с вероятностью 1, поэтому любая последовательность с миллионом нулей не является случайной по этому критерию. Пусть Р— таков свойство, что нет элемента последовательности, равного нулю.
Р снова справедливо с вероятностью 1, поэтому по определению К2 любая последовательность с нулевым элементом не случайна. Вообще говоря, пусть хо— любое фиксированное число между нулем и единицей и пусть Р— такое свойство: нет элемента последовательности, равного хо. Из определения К2 сейчас следует, что нет случайной последовательности, которая может содержать элемент хо! Можно доказать, чта яе существует последовательности, удовлетворяющей условиям определения Я2. (Если Уо, Пы... — такая последовательность, хо выберем хо = По ) Следовательно, если К1 — слишком слабое определение, то К2 является, несомненно, слишком строгим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
