Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 49
Текст из файла (страница 49)
Франклин (1. Х. Ггапййп).) [О .. 1)-последовательность Уе, У1 Сэ с Г„= д" шод1 (26) является оо-распределенной для почти всех действительных чисел д > 1. Другими словами, множество (д [ И > 1 и (26) не со-распределено) имеет меру нуль. Доказательство этой теоремы и некоторые оГюбщения приведены в Май. Сотр.
17 (1963), 28-59. $ Франклин показал, что 9 должно быть трансцендентным числом для того, чтобы (26) была оо-распределенной. Раньше, в 60-е годы, степени (я" щоб 1) получали в результате трудоемких вычислений, использующих лщогократную точность для и < 10000, и 35 самых старших двоичных разрядов этих чисел, оставленных в файле на диске, успешно использовались как источник равномерно распределенных случайных чисел, Согласно теореме Г вероятность того, что степени (т" шог) 1) оо-распределены, равна 1, однако существует несчетное множество действительных чисел, поэтому теорема не дает информации о том, действительно ли последовательность для т имеет оо-распределение.
Можно совершенно спокойно держать пари, что никто при нашей жизни ие докажегл, что именно данная последовательность не является оо-распределенной, хотя это и возможно. Руководствуясь такими соображениями, он может законно удивиться, если окажется, что существует хакаялибо оо-распределенная последовательностгс существует лп алгоритм вычисления действительных чисел У для всех и > О, такой, что последовательность (С„) оо-распредслеиаУ Ответ — "Да", как показано, например, в работе 13, Е.
Кпп1п, В1Т 6 (1965), 246-250. Построенная последовательность полностью состоит из рациональных чисел. На самом деле каждое число У, имеет ограниченное представление в двоичной системе счисления. Другое построение определенной оо-распределенной последовательности, отчасти более сложное, чем построение предыдущей последовательности, вытекает нз теоремы 69, приведенной ниже. (См. также Н.
М. Коробов, Изв. 4кад. наук СССР 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 являетси, несомненно, слишком строгим. "Правильное" определение должно быть менее строгим, чем К2. В действительности мы не показали, что определение К1 слишком слабое, поэтому продолжим исследование. Как упоминалось выше, оо-распределенная последовательность рациональных чисел построена. (В самом деле, зто не так уди- вительно: см. упр.
18.) Почти все действительные числа иррациональны. Возможно, следовало бы потребовать, чтобы для случайной последовательности выполнялось РгЩ, рациональное) = О. Из определения равиораспределенности (см. равенство (2)) слелует, что Рг(и < Ь'„< е) = е-и. Существует очевидный способ обобщения этого определения, используя теорию мерьк "если 5 С (О ..1) — - множество меры д, то (27) Рг(У„е 5) = р для всех случайных последовательностей (У„)". В частности, если 5 — множество рациональных чисел, то оно имеет меру нуль; значит, нет последовательности рациональных чисел, равнораспределениых в этом обобщенном смысле.
Разумно ожидать, что теорема В может распространяться на интегрирование по Лебегу вместо интегрирования по Риману, если оговорено свойство (27). Однако мы снова найдем, что определение (27) слишком строгое, так как иегл последовательностей, удовлетворяющих этому свойству. Если Ц>, У~, ...
— любая последовательность, множество 5 = (Ц>,Гы...) есть множество меры нуль. Кроме того, Рг(У„е Я) = 1. Поэтому в силу тех же аргументов, из-за которых рациональные числа были исключены из случайных последовательностей, можно исключить все случайные последовательности. До сих пор определение В1 можно было считать приемлемым. Однако существует несколько совершенно обоснованных возражений по этому поводу.
Например, если имеется случайная в интуитивном смысле последовательность, то бесконечная подпоследовательность также должна быть случайной. Это не всегда верно для оо-распределенных последовательностей. В самом деле, если взять любую <ю-распределенную последовательность и присвоить (7„~ +- 0 для всех и, количество иь(п), появляющихся в критерии й-распределенности, изменится самое большее иа,,lй.
Значит, отношение иэ(п)/и ие изменится. Таким образом, определение Н1 не удовлетворяет этому критерию случайности. Можно было бы усилить В1 следующим образом. Определенпе КЗ, (О .. 1)-посэедовательпость называется случайной, если «аждвя ев бесколечпая подпогледовательность является со-распределеллол. Однако еще раз определение вышло очень строгим; любая равнораспределенная последовательность (0'„) имеет монотонную подпоследовательиость с Ум < ('„< У, < Секрет состоит в том, чтобы ограничиться подпоследовательиостями, при построении которых можно было бы заранее сказать, принадлежит ли заданное У„ этой подпоследовательностн.
Предлагаем следующее определение. Определение В4. (О .. 1)-последовательность (У„) называется случайной, если для любого эффективяого алгоритма, точно опрелеляюгпего бесконечную последовательность различных неотрицательных целых чисел э„для и ) О, подпоследова- тельность 1~м, С~~, бы, ..., Соответствующая этому алгоритму, является оо-распре- деленной. Алгоритм, относящийся к определению Н4, -- это эффективная процедура вычисления э„при заданном и (см. обсуждение в разделе 1.1). Так, например, последовательность (я" шод 1) не удовлетворяет Н4„поскольку ова или не равно- распределена, или существует эффективный алгоритм, определяющий бесконечную подпоследовательность э„с (я" шод 1) < (я" шод1) < (х*' шод1) < Точно так же никакая явно определенная последовательность яе может удовлетворять определению Я4.
Это справедливо, если согласиться с тем, что никакая явно определенная последовательность не является случайной. Судя по ее виду, явная последовательность (й" шод 1) на самом деле, однако, удовлетворяет определению К4 для почти всех действительных чисел д > 1; это не противоречие, так как почти все В не могут быть вычислены алгоритмом. Ж. Ф. Коксма (3. Р. Кокэша) доказал, что (д'" шо61) является 1-распределенной для почти всех д > 1, если (в„) — любая последовательность различных положительных целых чисел (Сошроэйю Май.
2 (1935), 259-258). Г. Нидеррейтер (Н. %ес)егге11ег) и Р. Ф. Тичи (В. Р. Т1сйу) усилили теорему Коксма, заменив "1-распределенность" "оо-распределенностью'" (Майегпасйа 32 (1985), 26 — 32). Только счетное множество последоватечьностей (э„) эффективно определимо; значит, (д" шоб 1) почти всегда удовлетворяет В4. Определение В4 более строгое, чем определение Н1, но все еэге можно утверждать, что определение Н4 слишком слабое. Пусть, например., (б"„) — истинно случайная последовательность.
Определим подпоследовательность (О;„) следующим образом: ээ = О и, если и > О, э„— наименьшее целое число > и, для которого все 6',„ы У,„з, ..., 5',„„меньше 1. Таким образом мы определили подпоследовательность значений, следующих за первой серией и значений, меньших —.'. Предположим, что 6'„< ~1 соответствует выпадению "герба" при бросании монеты. Игроки склонны считать, что длинный ряд "гербов" предполагает, что появление "решки" становится более вероятным, если монета не поддельная. В этом случае подпоследовательность (б',„) определяет систему азартной игры для человека, который делает и-ю ставку на первую решку, следующую после серии из и "гербов." Игрок, возможно, думает, что Рг(У,„> -') больше -', но, конечно, и истинной случайной последовательности (П,„) будет совершенно случайным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
