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

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

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

Правда, в среднем такое случается только в й одной из 2сееевее ситуаций, но это действительно происходит. Действительно, данный феномен встречается в любой поистине случайной последовательности. Мы используем пока наше интуитивное понятие "истинная случайность'. Каждый может легко себе представить, что такая ситуация будет иметь значительные последствия, если такое множество из миллиона "истинно случайных" чисел использовать в эксперименте компьютерного моделирования. Это будет хорошим поводом для того, чтобы вызвать недовольство генератором случайных чисел.

Однако при наличии последовательности чисел, которые никогда не пробегают миллион последовательных Г~ч меньших —, последовательность будет не случайной и она не будет подходящим 1 источником чисел для других предполагаемых применений, использующих на входе крайне длинные блоки П . В итоге истинно случайная последовательность будет проявлять локальную "недлучайностьь, Локальная "неслучайность" необходима в одних применениях, но она гибельна, в других.

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

Эти факты действительно представляют собой камни преткновения всякий раз, когда необходимо дать полезное определение случайности, но они не являются истинной причиной смятения. Все еше можно сформулировать такое определение случайности бесконечной последовательности действительных чисел, чтобы соответствующая теория (расюмотренная должным образом) много дала для поннмания обычных конечных последовательностей рациональных чисел, которые на самом деле генерируются на компьютере. Более того, ниже в этом разделе будет показано, что существует несколько внушающих доверие определений случайности конечных последовательностей.

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

Во-первых, нужно обобщать определение А, так как фигурирующий в нем предел не существует для всех последовательностей. Определим — н(п) Рг(5(п)) =!!швцр, Рг(5(п)) = !пп!и( —. н(гг) (7) и-~со и и — ~сь П Тогда вероятность Рг(5(п)) является общим значением Рг(5(ц)) и Рг(5(п)) (если она существует). Мы видели, что й-распределенная [0..1)-последовательность приводит к 6-распределенной б-ичной последовательности, если П заменить [ЬЦ .

Наша теорема показывает, что обратное утверждение также справедливо. Теорема А. Пусть (Ьп) = По, Пы (7м ... — [0..1)-последовательносты Если последовательность ([Ьт(7„)) = [Ь,Пе), [Ь,Пг), [Ь,П.), является 6-раснределеннойг Ьу-ггчной последовательностью для любого Ь нз бесконечной послеловательностгг целых чисел 1 < Ьг < Ьз < Ьз <, то исходная погледовательность (У„) И-раснреде тенная. В качестве примера предположим, что Ь = 2'. Последовательность [2'По), [21Пг),...

является, по существу, последовательностью первых у двоичных разрядов бинарного представления Ь и Ь'ы .... Если все эти последовательности целых чисел 6-распределены в смысле определения П, то последовательность действительных чисел (7в, (7ы ... также должна быть й-распределенной в смысле определения В. Доказательство. Если погледовательность [Ьбв), [ЬГ~), ... Ь-распределена, то с помощью сложения вероятностей получим, что (5) выполняется всякий раз., когда, каждое и, и и, — рациональные числа со знаменателем 6. Предположим, что и, и — любые действительные числа, и пусть и'з и„' — райиональные числа со знаменателем 6, такие, что и ° <и <и +1/Ь.

иг, ..., иь < П„ч.ь г < иы Получим 1/Ь, 1~ — ив+ -7!; Ь/' Ь Рг(5(п)) ) Рг~и' + — < б;, < и',...., иь ! иь /. 6/' Сейчас [(и'. — и'. ~ 1/Ь) — (и — и )[ < 2/Ь. Так как наше неравенство выполняется для всех 6 = Ь. и так как 6 — > оо цри 7' — > оо, получим (и~ — и~)...

(иь — иь) < Рг(5(п)) < Рг(5(п)) < (и~ — и~)... (иг — иь). 1 Следующая теорема является основным орудием ддя доказательства различных утверждений о й-распределенных последовательностях. и'.<и <и'+ Пусть 5(п) — утверждение, что иг 1 Рг(5(п)) < Рг[и' < (7„< о[ + —, Ь' < П„< иь Теорема В.

Предположим, что (Уи) — й-распределенная [0..1)-послсдовахельность, и пусть !'(х1. хю..., хь) — интегрируемая по Рпману функция lс переменных. Тогда 1 г' г' 1пп — ~~' ~(бу,П ~„..., Гу+1 !) = / / у(х1,хт,...,хь) Их1... 1(хрь (8) и — ~ии и о о 0<1<и Доказан!ельстео. Из определения к-распределенной последовательности следует, что этот результат справедлив в частном случае, когда у(х1,...,хь) = [и! <х! < 01, ..., иь <хь < еь], (9) можно заключить, что (8) верно также для У. ) Теорема В может применяться, например, в критерии перестановок из раздела 8.8.2.

Пусть (р„р,,...,рь) — любая перестановка чисел (1,2,...,к). Покажем, что 1 1(ь'и+р — 1 < Пи1ри-1 « ' ' ' Пи+р! — !) 11'"" (10) Для доказательства предположим, что последовательность (У„) к-распределена и пусть У(х1,...,хь) = [х„<х„« "хр„]. Имеем РГ0'" Чр — ! < 1!и-рри-1 « ' ' ' бр+и! — 1) г1 ! 1(х1,...,хь) Ых1... 1(хь Следствие Р.

Если [О .. 1)-последовательносгь й-распределена, то она удовлетворяет критерию перестановок порядка к в смысле равенства (10). $ для некоторых постоянных и1, и„..., пы еь. Более того, (8) выполняется каждый раз, когда ~ = а1~! + а!11 +. + а„,( и каждая функция У1 является функцией вила (9). Другими словами, (8) выполняется каждый раз, когда у является иступенчатой функцией", полученной путем разбиения единичного к-мерного куба на подкубы, грани которых параллельны оси координат, и у принимает постоянные значения на каждом подкубе. Пусть 1 — любая интегрируемая по Риману функция. Если с — любое положительное число, то (по определению интегрируемости по Риману) получим, что существуют ступенчатые функции 1 и У, такие, что у(х1,..., хь) < у(х1,..., х1) < 1(х1,..., хь), и такие, что разность интегралов у и 1 меньше е.

Поэтому (8) выполняется для 1 и у. И поскольку 1 1 „-,р, 1(~' " П1+ь- ) < — ~~', 1(П! " П1-1-1) 0<1<и 0<1<и < — ~ ' 7(П1,...,П1„,), 1 0<!'<и Также можно показать, что последовательность удовлетворяет кригперию сериальной корреляции. Следствие Я.

Если (О .. 1)-последовательность (к + 1)-распределена, то коэффициент сернвльной корреляция между Г„п Г„+1 стремится к нулю: 1пп (1 т Гг (1 т Г,)2)(1 т Гг (1 т Г )2) (Все суммирования здесь выполняются по 0 < 1' < и.) Доказательство. По теореме В значения 1гт Гг стремятся сгютветственно к пределу —, —, 3, —, — при и — 1 оо. 2 1 1 1 1 1 Рассмотрим несколько более общие свойства распределений последовательностей. Мы определяли понятие 1с-распределения, рассматривая все смежные строки размерности к, например последовательность является 2-распрвделенной тогда и только тогда, когда точки (~ щ Г1), (Г1,Г2); (Г2,! 3); (ГЗ: ~ 4), (1 4 ° 03) равнораспределены в единичном квадрате.

Это вполне возможно несмотря на то, что пары точек (Г1, Гг), (Гг, Г1), (Г-„Гв) .., могут быть не равнораспределенными. Если в некоторой области не хватает точек (Г1„1, Гг„), их можно компенсировать другими точками; (Гг„, Г2„,1). Например, периодическая бинарная последовательность (Х„) = 0,0,0,1. 0,0,0,1, 1,1,0,1, 1,1,0,1, 0,0,0,1, (11) с периодом длины 16 будет 3-распределенной; однако последовательность четных элементов (Хг„) = О, О, О., О, 1, О, 1, О, ... имеет в три раза болыпе нулей, чем единиц, тогда как подпогледовательность нечетных элементов (Х2„.11) = О, 1, О., 1, 1, 1, 1, 1, ... имеет в три раза больше единиц, чем нулей.

Предположим, что последовательность (Г„) является ос-распределенной. Пример (11) показывает., что подпоследовательность чередующихся членов (Гг,) = Ге, Гг, Г4; Га, ... не обязана быть со-распределенной или даже 1-распределенной. Но (Гг„) на самом деле является оа-распределенной и многое еще будет верным.

Определение Е. (О .. 1)-последовательность (Г„) называют (т, 14)-распределенной, если 1 г(и1 < ~~пп41 < 1'1, и2 < ('глл4-гл1 < 12, ° ° иь < !'пьл+1'-';1 — 1 < и1) = ( '1 — и1) . ( '1. — и1) для любого выбора действительных чисел и,, и„пря 0 < иг < и, < 1 для 1 < г < 14 п для всех целых 1 нрн 0 < 1 < пь Поэтому 14-распределенная последовательность является частным случаем определения Е при гп = 1; случай, когда гп = 2, означает, что строки размерности 14, начинающиеся с четного номера, должны иметь такую же плотность, как и строки размерности !г, начинающиеся с нечетного номера, и т.

д. Следующие свойства определения Е очевидны: (им К)-распределенная последовательность является (т, к)-распределенной для 1 < к < й; (12) (т, Ь)-распределенная последовательность является (о, к)-распределениог1 для всех делителей г! числа т. (13) (См. упр. 8.) Также можно определить понятие (т, Ь)-распределенности Ь-ичвой поцэедовательности, как в определении Р, и доказать теорему А, остающуюся верной для (т, Й)-распределенных последовательностей. Следующая теорема, которая во многих отношениях является. скорее, сюрпризом, показывает, что свойства, присущие ж-распределению, действительно очень строгие, более строгие, чем мы представляли себе, когда впервые рассматривалн определение этого понятия.

Теорема С. (Иван Нивен (1чап !9!чеп) и Г. С. Цукерман (Н. Б. Хцсйегшап).) аа-рас- пределенная последовательность является (ги, л)-распределенной для всех положи- тельных т и Ь. Лемма Е. Заданы тп последовательностей члсел (уул) = Уэо, Уум для 1 < 1 < "л. Предположим, что !пп (уш+ уэь+ . + У~„) = то, !гш эпР (Угл + Уэл + ' ' ' + Умл) (14) ч->сю Тогда для каждого у существует !пп„, у „и он равен сь Невероятно простое доказательство этой леммы приведено в упр. 9. 1 Продолжим доказательство теоремы С. Пусть х = хгхз...

х — — Ь-ичное число, скажем, что х встречается на позиции р, если Хр ч,Х „,+э... Хр — — х. Пусть и (и) -- число х, находяшнхся на позиции р, когда р < и и ршопт = э1 Пусть Доказательства. Достаточно доказать теорему для Ь-ичной последовательности, используя обобщение только что упомянутой теоремы А. Более того, можно предположить, что л~ = Ь, так как (12) и (13) утверждают, что последовательность (т, й)-распределена, если она (лй, тй)-распределена. Таким образом, докажем, что любая со-расиределенная Ь-ичная последовательность Хе, Хм... является (т, т)-распределенной для всех положительных целых т. Наше доказательство — это упрощенная версия первоначального доказательства, приведенного в статье Х1чеп алг! Кис!гепвап, Рас!бс 1. Млей.

1 (1951), 103 109. Ключевая используемая идея является важным методом„применяемым во многих ситуациях в математике: "Есле и сумма т величин, и сумма их квадратов согласуются с гипотезой, что т величин равны, то гипотеза верна". В строгом виде этот принцип можно сформулировать так.

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

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