Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 47
Текст из файла (страница 47)
Определение В. Говорят, что последовательность (1) будет й-распредапенной, если Рг(п~ <0„<о„..., пь <Ь'„+ь, <гь) =(е, — н~)...(сь — иь) (д) для всех вариантов действительных чисел и, о прп 0 < и < ез < 1 для 1 < у < 1з Равнораспределенная последовательность является 1-распределенной. Заметим, что, если Й > 1, Ььраспределенная последовательность всегда является (6 — 1)- распределенной, так как в (5) можно положить иь = 0 и оь = 1. Таким образом, в частности, любая последовательность, о которой известно, что она 4-распределена, должна быть также 3- и 2-распределенной. Можно определить наибольшее 6, для которого данная последовательность является Й-распределенной, что приведет нас к формулировке более сильного свойства.
Определение С. Говорят, что последовательность оо-распределена, егшц опа Ь-раслределена для всех пачожптельвых целых й. До сих пор мы рассматривали (О ..1)-последовательности, т. е, последовательности действительных чисел, лежащих между 0 и 1. Такие же понятия применяются к целочисленным последовательностям, Говорят, что последовательность (Х„) = Хо, Хы Хз, ... явлнется Ь-очной последовагпельностью. если каждый член последовательности Х„является одним из целых чисел О, 1, ..., 6 — 1. Таким образом, 2-ичная (бинарная) последовательность — это последовательность нулей и единиц.
Определим также Ь-очное число, состоящее из 6 цифр, как строку й цельгх чисел х~хе... хь, где 0 < х. < Ь для 1 < Т < 6. Определение ь1. Говорят, что 6-цчная последоватнльпость явтчяется 6-распределенной, если Рг(Х„Х„еы..Х„еь ~ — — х~хю хь) =- 1!Ь (О) для всех Ь-пчньгх чисел хатха ° ать ° Из етого определения ясно, что если 0о, Уы ... являет< я й-распределенной последовательностью 10.,1), то последовательность (Ы'а), (ИУг), ... является Й-распределенной Ь-ичной последовательностью.
(Коли положить н. = х,/6, о1 = (х1 + 1)/Ь, Х„= (ЬУ„1, то равенство (5) превратится в равенство (0).) Более того, каждая Ььраспределенная Ь.ичная последовательность является также (Й вЂ” 1)-распределенной, если Й > 1: мы складываем вероятн~ -тп для Ь-ичных чисел х~...хь ~0, х~... хы ~1, ..., х,...хь ~ (Ь вЂ” 1), чтобы получить Рг(Х„...
Х„=,...., ) = 1~6' (Вероятности для несовместных событий еддитивны; см. упр. 5.) Следовательно, естествеано ввести понятие со-распределенных 6-ичных последовательностей, как в определении С. Представление положительных действительных чисел в системе с основанием 5 можно рассматривать как 5-ичную последовательность, например и оютветствует 10-ичиой последовательности 3, 1, 4, 1, о, 9, 2, б, 5, 3, 5, 8, 9, .... Предполагается, что эта последовательность оо-распределенная, но никто, однако, не в состоянии даже доказать, что она является точно 1-распределенной. Проанализируем это понятие более подробно для случая, когда й равно миллиону. Бинарная последовательность, являющаяся 1 000 000-распределенной, может содержать серию из миллиона нулей) Аналогично )О,. 1)-последовательность, являющаяся 1 000 000-распределенной, может содержать миллион последовательных значений, каждое из которых меньше —,'.
Правда, в среднем такое случается только в одной из 2'ееееее ситуаций, но это действительно происходит. Действительно, данный феномен встречается в любой поистине случайной последовательности. Мы используем пока наше интуитивное понятие "истинная случайность". Каждый может легко себе представить, что такая ситуация будет иметь значительные последствия, если такое множество из миллиона "истинно случайных" чисел использовать в эксперименте компьютерного моделирования. Это будет хорошим поводом для того, чтобы вызвать недовольство генератором случайных чисел.
Однако при наличии последовательности чисел, которые никогда не пробегают миллион последовательных Г,, меньших -', последовательность будет не случайной и она не будет подходящим источником чисел для других предполагаемых применений, использующих на входе крайне длинные блоки Г . В итоге истинно случайная последовательность будет проявлять локальную "неслучайность" . Локальная "неслучайность"' необходима в одних применениях, но она гибельна в других. Можно сделать вывод, что нет последовательности "сэучайных" чисел, которую можно 'было бы использовать в любом случае. В подобном духе каждый может утверждать, что невозможно решить, будет ли конечная последовательность случайной; любая конкретная последовательность ничем не отличается от любой другой.
Эти факты действительно представляют собой камни преткновения всякий раз, когда необходимо дать полезное определение случайности, но они не являются истинной причиной смятения. Все еще можно сформулировать такое определение случайности бесконечной последовательности действительных чисел, чтобы соответствующая теория (рассмотренная должным образом) много дала для понимания обычных конечных последовательностей рациональных чисел, которые на самом деле генерируются на компьютере, Более того, ниже в этом разделе будет показано, что существует несколько внушающих доверие определений случайности конечных последовательностей.
В. оо-распределенные последовательности. Кратко рассмотрим теорию оо-распределенных поглеловательностей. Чтобы описать ее адекватно, понадобится немного высшей математики, поэтому в остальной части этого раздела предполагается, что читатель знаком с понятиями, необходимыми для понимания далыюйшего материала. Во-первых, нужно обобщить определение А, так как фигурпрующий в нем предел не существует для всех последовательностей. Определим — е(п) Рг(5(п)) = 1ппзпр †, Х г(5(п)) = 1пп1п( †. и(п) (7) ь ~ос и И-~ОО и Тогда вероятность Рг(5(п)) является общим значением Рг(5(п)) н Рг(5(п)) (если она существует).
Мы вгщелн, что Й-распределенная (О .. 1)-последовательность приводит к Й-распределенной Ь-ичной последовательности, если У заменить (Ьь."). Наша теорема показывает, что обратное утверждение также справедлнво. Теорема А. Пусть (Уь) = Уа, Ум Ую ... -- (0.,1)-последовательность. Если последовательность «ЬЗП.5) = (Ьуио), (Ь1П1), (ЬУПз), является И-распределенной Ь;-нчной последовательностью для любого Ьу вз бесконечной последовательностп целых чисел 1 < Ь~ < Ьз < Ьз < - °, то исходная последовательность (У„) К-распределенная.
В качестве примера предположим, что Ь = 2т. Последовательность (2%а), (2Ж~) „... является, по существу, последовательностью первых у двоичных разрядов бияарного представления 6е, Уы .... Если все эти последовательности целых чисел Ь-распределены в смысле определения П, то последовательность действительных чнсел (/а, Уг,... также должна быть й-распределенной в смысле определения В. е,' < еу < е' + 1/Ь.
еы ..., иь < У„.~ь г < еь. Получим и' < и - < и' + Пусть 5(п) — утверждение, что и~ Рг(5(п)) < Рг ~и~ < П„< е( + —, Ь' 1/Ь, 11 < (/,+ь г < еа+ -1 (е( — й+ )...(еь иь+ ); + — (/„+ь, < еь/ = ~е~ — й, — -)... ~еь — иь — Д Рг(5(п)) > Рг(и', + - < Ь'„< е'„..., и~, Сейчас ~(е' — й: х 1/Ь) — (еу — и )) < 2/Ь.
Так как наше неравенство выполняется для всех Ь = Ь; н так как Ь. -Ф ао прн у -ь ао, получим (ег — иг)... (еь — иь) < Рх(5(п)) < Рг(5(о)) < (ег — ид. ° (еь иь) й Следующая теорема является основным орудием для доказательства различных утверждений о Ь-распределенных последовательностях.
Доказательство. Если последовательность 1Юа), (Ьбгг), ... Ь-распределена, та с помощью сложения вероятностей получим, что (б) выполняется всякий раз, когда каждое иу и еу — рациональные числа со знаменателем Ь. Предпаложям, что и,, е„— любые действительные числа, и пусть и', е' — раг1нональные числа со знаменателем Ь, такие, что Теорема В. Предположим, что (У„) — к-распределенная [0..1)-последовательность, п пусть у(хм хт,..., хь ) — интегрируемая по Рпмапу функция к переменных. Тогда 1 г' й — Е т,П„„...,,„,)=~" "~'Л.„.„.,)Ь, ~., (8) »-~»» и о о о<о<» Аокааагаельстпеа. Из определения й-распределенной последовательности следует, что этот результат справедлив в частном случае, когда Ихы",хь) =[В1<х1<с1 " па<ха<па) (9) для некоторых постоянных пы пы..., пь, оа.
Более того, (8) выполняется каждый раз, когда 1 = а16 + атут + ° ° + а~~~ и каждая функция Д является функцией вила (9).,Лругими словами, (8) выполняется каждый раз, когда у является»ступенчатой функцией", полученной путем разбиения единичного к-мерного куба на подкубы, грани которых параллельны осн координат, и у принимает постоянные значения на каждом подкубе. Пусть | — любая интегрируемая по Рнману функция.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
