Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 48
Текст из файла (страница 48)
Если е — любое положительное число, то (по определению интегрируемости по Риману) получим, что существуют ступенчатые функции у и У, такие, что Дхы...,хк) < У(хы...,хь) < ,~(хы...,хь), и такие, что разность интегралов у и у' меньше а Поэтому (8) выполняется для у и 7. И поскольку 1 1 1(П~,,(5~+а-~) < — ~~ У(б'1, Па+а-1) оя<» о<1<» 1 т < — з У%,..., Пт+„,), о<1<» можно заключить, что (8) верно также для у. ! Теорема В может применяться, например, в крирперпи пересшановок из раздела 3.3.2.
Пусть (рырз,...,рк) — любая перестановка чисел (1,2,...,к). Покажем, что Р (П„„,, < и„„,, « " и».,р„1) = 1! ай (1О) Для доказательства предположим, что последовательность (6' ) к-распределена и пусть г(х1 хь) [хр < хр « хр 1 г(»'»+р~-1 < К~+р»-1 < ' ' < П»+ра-1) г' =/ - / ~(хы...,хь)аахм..с(хь о о Йхр 1хр дхр1 Следствие Р. Если [О .. 1)-последовательность к-распределена, то опа удоалетворяет крптершо перестановок порядка й в смысле равенства (10).
$ Также можно показать, что последовательность удовлетворяет криглерию сериальмой корреллции, Следствие Я. Если (0..1)-последовательность (к+ Ц-распределена, токоэг)и)пациент серцальной корреляции между К, п К,ч.ь стремится к нулю: -„' Б оП +э — („' Е М Й Е Пу+ ) О. 1пп (Все суммпрования здесь выполняются по 0 < у < и.) Докаэагпельспьоо. По теореме В значения ТУП 1~ П ) У" ПР стремятся соответственно к пределу т, -', -', 1, -' при и -+ оо. э Рассмотрим несколько более общие свойства распределений последовательностей.
Мы определяли понятие й-распределения, рассматривая все смежные строки размерности Й, например последовательность является 2-распределенной тогда и только тогда„ когда точки (По.01) (о1:Пэ) (Вт Пз) (~~3 ~4) (~~4:ОБ)> равнораспределены в единичном квадрате. Это вполне возможно несмотря на то. что пары точек (Уд, Уз), Щ, У4), (6э, Уэ),... могут бьггь ме равнораспределенными. Если в некоторой области не хватает точек (Гэ„ы Пэ„), их можно компенсировать другими точками: (Пэ„, Уз„~.1). Например, периодическая бинарная последовательность (Хл) = 0,0,0,1, 0,0,0.1, 1,1,0,1, 1,1,0,1, 0,0,0,1, ...
(И) с периодом длины 16 будет 3-распределенной; однако последовательность четных элементов (Ллл) = О, О, О, О, 1, О, 1, О, ... имеет в три раза больше нулей, чем единиц, тогда как подпоследовательность нечетных элементов (Хт .~1) = О, 1, О, 1, 1, 1, 1, 1, ... имеет в три раза больше единиц, чем нулей. Предположим, что последовательность (У„) является оо-распределенной. Пример (11) показывает, что подпоследовательиость чередующихся членов (Гз„) = Уо, Уэ, Г~, Уэ,... не обязана быть со-распределенной или даже 1-распределенной. Но (Уд„) на самом деле является со-распределенной и многое еще будет верным.
Определение Е. 10 .. 1)-погледовательиость (У„) называют (т, й)-распределенной, Рг(и1 < У,„„+1 < ом из < Слал++1 < оэ, ..., иэ < П лез+э 1 < оь) = (щ — и1)... (оь — иь) для любого выбора действительных чисел и„, о„прп О < и, < о, < 1 для 1 < г < Й и для всех целых у прп О < у < гп. Поэтому й-распределенная последовательность является частным случаем определения Е при щ = 1; случай, когда ~п = 2, означает, что строки размерности /с, начинающиеся с четного номера, должны иметь такую же плотность, как и строки размерности й, начинающиеся с нечетного номера, и т.
д. Следующие свойства определения Е очевидны: (т, к)-распределенная последовательность является (гп, к)-распределенной для 1 < к < к; (тп, й)-распределевная послелоаательность является (п,а)-распрвделенной для всех делптелей о' чнсла т. (См. упр. 9.) Также можно определить понятие (пт, й)-распределенности 6-ичной последовательности, как в определении О, и доказать теорему А, остающуюся верной для (т,й)-распределенных последовательностей.
Следующая теорема, которая во многих отношениях является, скорее, сюрпризом, показывает, что свойства, присущие оо-распределению, действительно очень строгие, более строгие, чем мы представляли себе, когда впервые рассматривали определение этого понятия. Теорема С. (Иван Нивен (1эап Н1теп) и Г. С. Цукерман (Н. Б. Епскегшап).) со-распрвделенная последовательность является (т, к)-распределенной для всех положятельных гп и й. Доказательство.
Достаточно доказать теорему для б-ичной последовательности, используя обобщение только что упомянутой теоремы А. Более того, можно предположить, что т = й, так как (12) и (13) утверждают, что последовательность (т, й)-распределена, если она (гпк, гпй)-распределена. Таким образом, докажем, что любая оо-распределеьчщя Ь-пчная последовательность Хе, Хм... является (гп, т)-распределенной для всех положительных целых пк Наше доказательство — это упрощенная версия первоначального доказательства, приведенного в статье %~еп апо' Упскегшап, Рас1йс з.
Маса. 1 (1951), 103-1 99. Ключевая используемая идея является важным методом, применяемым во многих ситуациях в математике: "Если н сумма т величин, и сумма их квадратов согласуются с гипотезой, что т величин равны, то гипотеза верна". В строгом виде этот принцип можно сформулировать так. лемма е. Заданы га последовательностей чисел (уэ„) = ууо, узы - ",лля 1 < 1 < гп. Предположим, что 1пп (у|„+уз„+ ° ° + у,„„) = то, )ш (уз+ з+ + г )< г Тогда для каждого у существует 1пп„, у.„н он равен а. Невероятно простое доказательство этой леммы приведено в упр.
9. $ Продолжим доказательство теоремы С. Пусть х = я1хз... я„, — э-ичное число; скажем, что х встречавшая на позиции р, если Хр ~1Х„„,+э... Хр = х. Пусть иу(п) — число х, находящихся на позиции р, когда р < и и ршоб гп = 1. Пусть уг„= иг(п)/и и нужно доказать, что 1 1(пг ф „= —, а-+оо г пгб"' Во-первых, известно, что так как последовательность т-рвсггрцделеиа. Согласно лемме Е и равенству (16) теорема доказана, если показать., что Вюапр(у,'„+~,'„+" +у,' ц„) < — „'„,.
(17) и ФЮ пз я ~ (яуу~ Однако это неравенство не очевидна„.необходимо несколько деликатных маневров, прежде чем можно будет его доказать, Пусть о кратно гп. Рассмотрим Это число появлений пар х-в на позициях рг н рг, для которых и — О < рг < рг < и и рг — рг кратно пг.
Рассмотрпм сумму Каждое появление пары х-в, встречакяцейся на позициях рг и рз с рг < Рг < ра +Ч: где рг — рг кРатно пг и рг < № учитывается точно рг + д — рг раз в общей сумме Ям (т, е. когда рг < и < рг + д), а такие пары, которые появляются на позициях рг и рг с № < рг < рг < Х + д, учитываются точно гг'+ о — рз рвз.
Пусть 4(п) — число пар х, встречающихся на позициях рг и рг с рг +1 = рг < п. Приведенный выше анализ показывает, что И вЂ” 1)4 (№+ Ч) > Ям > ~~~ И вЂ” пгт)4„г(№). (20) о<г<д/~я о<г <дум Так как начальная последовательность является о распределенной, то 1, 1 й — А„г(№) = —. м 1гю для всех 1, 0 < 1 < д/пг, и, следовательно, из (20) получаем б~д х о — пгг о(д — пг) 1пп ф 2.~ бтп1 2г~фгтп о<г<оут Из этих равенств после нескольких преобразований получим утверждение теоремы, По определению (( ( ) ( ))г ( ( ) ( ))) кц О<г< и можно удалить не возведенные в квадрат члены н, применяя (16), получить Ти д(д — и!) 17 52йз би! где (му(п) — иу(п — д)) .
Тм = ~~~, и=1 о<у<»! Используя неравенство (см. упр. 1.2.3-30), находим, что р Ф<-д 3 йтэпр ~ ~. ~ ~ Х(и (и) — му(п-д))) < — + —. (24) 1 У ~ д(п-и!) д у~~, Р7(Х+д) ( ! ! ) и!51'и би' 051<иъ ии1 Также получим 4му(Х) < !! иу(п) = ~~! (!ч(п) — и!(и — д)) < ди~(Х+е). и — "1 Подставив это неравенство в (24), получим ~ О<у< и (25) Данная формула справедлива всякий раз, когда д кратно и1, и если мы устремим д -+ оо, то получим (17), что и завершает доказательство. Более простое доказательство можно найти у Дж. В. С. Касселя (Л. '!т'. Б. Саээе1э, Ра<16< Х Май. 2 (1052), 555-557). 1 В упр.
29 и 30 нллюсгрируегся нетривиальность этой теоремы и тот факт, что д-распределенная последовательность имеет вероятности, отклоняющиеся от истинных вероятностей (т,ьч)-распределения, по существу, не более чем на 1/Я (см. (25)). Для доказательства теоремы необходима гипотеза о оо-распределении носледовательности. Используя теорему С, можно доказат!ь что оо-распределенная последовательность проходит критерий серий, критерий "максимум-1", критерий конфликтов, критерий промежутков между днями рождений и критерий подпоследовательностей, о которых уноминелось в разделе 3.3.2.
Нетрудно показать, что она также удовлетворяет критерию интервалов, нокер-критерию и критерию монотонности (см. упр. 12-14). Критерий собирания купонов является значительно более трудным, но и его последовательность проходит (см. упр. 15 и 16). Существование оз-распределенной последовательности достаточно простого вида гарантирует следующая теорема. Теорема Р. (Дж. Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
