AOP_Tom2 (1021737), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

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

Возможно, следовало бы потребовать, чтобы для случайной последовательности выполнялось Рг(Ь„рациональное) = О. Из определения равнораспределенностн (см. равенство (2)) следует, что Рг(и < (7„< е) = о — и. Существует очевидный способ обобщения этого определения, используя теорию меры: "если Я С [О .. 1) — множество меры р, то (27) Рг((7„е Я) = р для всех случайных последовательностей (С~„)". В частности, если Я вЂ” множество рациональных чисел, то оно имеет меру нуль; значит, нет последовательности рациональных чисел, равпораспредезенных в этом обобщенном смысле. Разумно ожидать, что теорема В может распространяться на интегрирование по Лебегу вместо интегрирования по Римвну, если оговорено свойство (27).

Однако мы снова найдем, что определение (27) слишком строгое, так как нет последовательностей, удовлетворяющих этому свойству. Если Пе, Ц, ... — любая последовательность, множество Я = (Пе, Ьы...) есть множество меры нуль. Кроме того, Рг((7в е Я) = 1. Поэтому в силу тех же аргументов, из-за которых рациональные числа были исключены нз случайных последовательностей, можно исключить все случайные последовательности.

До сих пор определение В.1 можно было считать приемлемым. Однако существует несколько совершенно обоснованных возражений по этому поводу. Например, если имеется случайная в интуитивном смысле последовательность, то бесконечная подпоследовательность (28) также должна быть случайной. Это не всегда верно для оо-распределенных посчедовательностей.

В самом деле, если взять любую ао-распределенную последовательность и присвоить С'„~ ь- 0 для всех и, количество иь(п), появляющихся в критерии к-распределенности, изменится самое большее на ~/й. Значит, отношение ць(п)/и не изменится.

Таким образом, определение Н1 не удовлетворяет этому критерию случайности. Можно было бы усилить Н1 следующим образом. Определение НЗ. [О .. 1)-последовательность называется случайной, если каждая ее бесконечная подпоследовательвость является оо-распределенной. Однако еще раз определение вышло очень строгим; любая равнораспределенная последовательность ((7„) имеет монотонную подпоследовательность с б;, < П„ < Г,. < Секрет состоит в том, чтобы ограничиться подпоследоввтельностями., при построении которых можно было бы заранее сказать, принадлежит ли заданное С'„ этой подпоследовательности. Предлагаем следующее определение.

Определение Н4. [О ..1)-последовательность (У„) называется случайной, если для любого эффективного алгоритма, точно определяющего бесконечную послгдоватачьпость различных неотрицательных целых чисел а„для и ) О, подпоследова- тельность Н,э, Н„, Г„, ..., соответствующая этому алгоритму, является оо-распре- деленной. Алгоритм., относящийся к определению Н4, †. это эффективная процедура вычисления э„при заданном и (см. обсуждение в разделе 1.1).

Так, например, последовательность (тч шш1 1) нс удовлетворяет Н4, поскольку она или не равно- распределена, нли существует эффективный алгоритм, определяющий бесконечную подпоследовательность э„с (тм шой 1) < (х" гпо61) < (х" гной 1) < Точно так же никакая явно определенная поатедовательность не может удовлетворять определенно Й4. Это справедливо, егчи согласиться с тем, что никакая явно определенная последовательность не является случайной. Судя по ее виду, явная последовательность (В" шог1 1) на самом деле, однако, удовлетворяет определению Е4 для почти всех действительных чисел 6 > 1; это не противоречие,. так как почти все 0 не могут быть вычислены алгоритмом.

Ж. Ф. Коксма (Я, Р. Ко1сэша) доказал, что (й'" пюг1 1) является 1-распределенной для почти всех д > 1, если (э„) — любая последовательность различных положительных целых чисел [Сошроэ)бо МасЛ. 2 (1935), 250 — 258). Г. Нидеррейтер (Н. Н1ес(егге11ег) и Р. Ф. Тичи (Н. Р. Т1сЬу) усилили теорему Кокома, заменив "1-распределенность" "оо-распределенностью" [МаГ!~егпагйи 32 (1985), 26 — 32).

Только счетное множество последовательностей (э„) эффективно определимо; значит, (О" пюй 1) почти всегда удовлетворяет Н4. Определение Н4 более строгое, чем определение Н1, но все еще можно утверждать, что определение Н4 слишком слабое. Пусть, например, (ГГ„) — истинно случайная последовательность. Определим подпоследовательпость (Ь;„) следующим образом; эе = О и, если и > О, э„— наименьшее целое число > и, для которого все У,„ы У,„з, ..., У,„„меньше -'. Таким образом мы определили подпоследовательность значений, следуюгцих эа первой серией и значений, меньших ~1.

Предполоягим, что ЛГ„< э соответствует выпадению "герба" при бросании монеты. Игроки склонны считать, что длинный ряд "гербов" предполагает, что появление "решки" становится более вероятным, если монета не поддельная. В этом случае подпоследовательность (У,„) определяет систему азартной игры для человека, который делает и-ю ставку на первую решку, следующую после серии из и "гербов." Игрок, возможно, думает, что Рг(Ь;„> !) больше -', но, конечно, в истинной случайной последовательности (с,„) будет совершенно случайным. Нет системы азартных игр, которая всегда приводит к победе! Определение Н4 ничего не говорит о подпоследовательности, формируемой в соответствии с такой системой азартных игр; так что, по-видимому, необходимо нечто большее.

Пусть определено "правило подпоследовательности" Н как бесконечной последовательности функций (г„(хм..., хн)), где для и > О, ~„— функция и переменных и значение ~„(хы...,х„) равно либо О, либо 1. Здесь хы ..., х„— элементы некоторого множества о. (Таким образом, в данном случае уе — зто постоянная функция., равная либо О, либо 1.) Правило подпоследовательности гс определяет подпоследовательность бесконечной последовательности (Х„) элементов 5 следующим образом: п-й член Л„принадлежит подлоследовательностн (Х„)Е тогда я только тогда, когда 1„(Хе, Лг,, Л„~) = 1. Заметим, что нодпоследовательность (Л„))с, определенная таким образом, необязательно бесконечна; фактически в ней вообще может не быть элементов. Например, подпоследовательность азартного игрока, описанная выше, соответствует такому правилу подпоследовательности: (в = 1 и для и > О, /„(хм..., х„) = 1 тогда и только тогда, когда найдется некоторое Ь, 0 < Ь < и, такое, что Ь последовательных чисел х , х „ ..., х ьь, все будут < -, когда т = и, но не когда 1 й<гп<п.

Правило подпоследовательностей 1с называют исчислиммм, если существует эффективный алгоритм, определяющий значение ~„(хм..., х„), когда и и хм..., х„ заданы на входе. При попытке определить случайность лучше ограничиться исчислимыми правилами подпоследовательностей, когда пытаемся определить случайность, чтобы не получить чрезмерно ограничительное определение, подобное Вй. Но эффективный алгоритм нельзя рассматривать с произвольными входными действительными числами. Например, если действительное число х точно определено бесконечным разложением в десятичной системе счисления, то не существует алгоритма для того, чтобы определить, будет ли х < -', так как для этого нужно исследовать все цифры числа 0.333.... Поэтому исчислимое правило подпоследовательностей неприменимо ко всем (О .. 1)-последовательностям и служит основой для слелующего определения Ь-ичных последовательностей. Определение К5.

6-нчнвя последовательность называется случайной, если каждая бесконечная подл ослсдо ватель ность, определенная ясчлслпмым правилом подпогле- довательностеК является 1-распределенной. (0..1)-последовательность (Ья) называетгя случайной, есдп 6-очная последовательность ((ЬУ„) ) является случайной для всех целых чпсел Ь > 2. Заметим, что определение В.5 говорит только об 1-распределении, а не о оо-распределении. Интересно проверить, что это может быть сделано без потери общности.

Очевидно, можно определить исчислимое правило подпоследовательности И(аы .. аь) следующим образом при любом заданном 6-ичном числе ам .. аь. пусть г„(хм...,х„) = 1 тогда и только тогда, когда и > Й вЂ” 1 и х„э+1 — — ам ..., х„-~ = аь м х„= аы Если (Л„) является Ь-распределенной Ь-ичной последовательностью, то правило Я(а~... аь), с помощью которого выбирается подпоследовательность, содержащая точно следующие за появлением а~... аь члены, определяет бесконечную подпоследовательность, и, если эта подпоследовательность 1-распределена, каждая из строк а1...

оьаьы размерности (6+1) для 0 < аьч.1 < 6 появляется с вероятность 1/6~+' в (Л„). Таким образом, индукцией по Ь можно доказать, что последовательность, удовлетворяющая определению В.5, является Ь-распределенной для всех Ь. Подобным образом, рассматривая "композицию" правил подпоследовательностей, получаем: если Е, определяет бесконечную подпоследовательность (Л"„)Ем то можно определить правило подпоследовательности К~Ее, для которого (Л )Ка% = ((Л„)Я1)йз, и найти, что все подпоследовательности, рассматриваемые в определении В5, оо-распределенные (см. упр. 32). Факт, что со-распределение следует из определения К5 как очень частный случай, ободряет, и это хороший признак того,что можно, наконец, найти требуемое определение случайности. Но, увы, это все еще проблема.

Не ясно, почему последовательность, удовлетворяющая определению В5, должна удовлетворять определе- нию В4. Введенные нами исчислнмые правила подпоследовательностей всегда дают падпоследовательности (Х,„), для которых эо < эт <, но (э„) не должны быть монотонны в В4; они толька должны удовлетворять условию э„ф егя для и ф пь Итак, определения В4 и В5 можно скомбинировать следующим образом. Автор утверждаетэ, что это определение точно удовлетворяет всем разумным философским требованиям случайности, а значит, отвечает на основной вопрос, поставленный в этом разделе. В.

Существование случайных последовательностей. Как было показано, определение ВЗ слишком строгое в том смысле, что не существует удовлетворяющей ему поыедовательности, и в приведенных выше определениях В4 — Вб предпринимались попытки сохранить существенные элементы определения ВЗ. Для того чтобы показать, что определение В6 не чрезмерно ограничительно, все еще необходимо доказать, что последовательносттч удовлетворяющая всем этим условиям, существует.

Характеристики

Список файлов книги