AOP_Tom2 (1021737), страница 172
Текст из файла (страница 172)
Пайка (К. Руйе, а'. Ноуа1 55аа 5ос. В27 (1966), 396-449).] 37. Рассмотрим многогранник в гиперплоскости 51 + + 5 = 1, определенный неравенствами 51 > О, ..., 5 > О. Он состоит из и! конгруэнтных подмногогранников, определенных упорядочением 5, (прсдоолагаетсн, что 51 различны), и операцией сортировки является от п1 к одному складывание больших 51ногогранников иэ подмногогранников, в которых 51 « 5„. Преобразование, которое переводит (510,...,500) в (5',,...,5,',), является взаимно однозначным отображением, разлагающим дифференциальные объемы на и! частей, Оно образует вершины (-„',..., —,',), (О, — „1,...,,—,'1), ..., (О...,О, 1) подмногогранников в соответствующих нершинах (1,0,..., 0), (О, 1, О,..., 0), ..., (О,...,О, 1); линейное растяжение и искажение полностью приспособлены к процессу. (Евклидова расстояние между вершинами (О,...,О,;,..., -) н (О,..., О, 5,..., -„) в подмногограннике рав- 1 ! 1 1 но ]у ' — Ь ']'1~; преобразование образует регулярный симплекс, в котором все и вершин нвходятсн на расстоянии ь49.) Поведение итерированных разностей (О, О, 1) легче понять, если проверить детали графически при и = 3.
В этом ш1учае многогранник является простым равносторон- х<х у<в 2а аа ни54 треуголъником, точки которого вы- 22 а2 ражены в барицентрических координатах м 51 (х,у,х), х + у + 2 = 1. На приведен- 24 54 ном рисунке иллюстрируются два первых 25 55 уровня рекурсивного разбиения этого тре- 34 35 15 угольника, Каждый иэ 6 подтреуголь- у>х ников помечен днузначным кодом рд, где за 33 13 55 45 1а 32 53 43 12 р соответствует подходнщей перестановке, Ы 44 когда (х,у, 2) = (51, 52,53) рассортврова- аа 51 41 45 ны в виде (5п н 5121 5432), а 9 соответствует перестановке следующей стадии, когда 51, ' ' ' 1 Х > У < „ (О, 1, О) 5з и Яз рассортированы в соответствии со следующим кодом: О:х<у<х, 1:х<з<у, 2;у<х<з, 3:у<з<х, 4;з<х<у, 5.г<у<х.
Например, для точек подтреугольника 34 выполняются неравенства Ял < ал < 5~ и бз < Я < аз. Этот процесс можно продолжить да получения бесконечного числа уровней; все точки треугольника с иррациональными барицентрическими координатами вследствие этого получат единственное представление в системе счислении с основанием б. Четырехгранник аналогично может быть разделен на 24, 24, 24, ... падчетырехгранз ников; в общелл случае эта процедура образует представление с основанием п! для любого (и — 1)-мерного симплекса. Когда п = 2, процесс особенно прост: если х Р (О, -', 1), при преобразовании образуется разность (х, 1 — х) = (х, у) в (2х шос) 1, 2у шоб 1) либо (2у шос( 1, 2х шоб 1) в зависимости от того, будет ли х < у или х > у. Повторные испытания — это, по существу, сдвиг бинарного представления влево на один разряд, который, возможно, дополняет результат. После не более чем е+ 1 итершплй на е-разрядные числа процесс должен сойтись к фиксированной точке (0,1).
Перестановочное кодирование для и = 2 соответствует просто свертке и растягиванию линии; первые четыре уровни разбиений имеют следующие четырехразрцдные коды. (1, О) (О, 1) оооо ооо~ ооц оооо оыо шы оюл оюо цоо лло! мы гцо лоло шм ~оо~ ~ооо Эта последовательность точна совпадает с двоичным кодом Грея, рассматриваемым в разделе 7.2.1.
В обн[ем случае в перестанавачном коде в систелле счислении с основанием и! для п-снмплекса смежные области иллеют идентичные коды, за исключением одной цифры. Посте каждой итерации разностного преобразования в представлении каждой точки удаляется крайняя соева цифра. Заметим, что равные разности дней рождения— это точки около границы разложения на первом уровне. Фундаментальное преобразование нз (Яц..., Яо) в (Я',,..., Я„') подразумевается в доказательстве Витворта предложения 1Х1 в пятом издании СЬо!се алс! СЬапсе (см. ссылку на литературу в ответе к упр. 26) Сначала оно было подробно изучено Дж.
Дурбиным (Л. ПнгЬ(п, В!ошезг!Ьа 49 (1961), 41-55), которого вдохновил подобными построениями П. В. Сухатме (Р. Ъ'. Яц!сЬагше, Аппо(з ог" Енбел!сз 9 (1937), 52-56) Перестановочное кодирование для повторных разностей было введено Г, Э, Даниелем (Н. Е. Паше!з, В!ошеог!Ьа 49 (1962), 139 — 149). 20. (а) Число разбиений пл на п различных положительных частей равно р (тп — ("з')), что следует из упр 5.1.1-16. Эти разбиения могут быть переставлены и! способами, чтобы образовать п-мерные строки (уц,у„) с О = ул < уз « .
у < т, и каждая из этих п-мерных строк приводит к появлению (и — 1)! и-мерных строк, таких, что ул = О и О < уз,..., у < т. Добавим константу по модулю т к каждому уз, что позволит сохранить разность. Отсюда Ь оо(т) = тп! (п — 1)! Р„(гп — ("Оз')). (Ь) Нулевые разности соответствуют вларам в одной н тай же урне, и з — 1 — их вклад а число равных разностей. Поэтому Ь„„,(т) = („,! Ь! —,ц, ~ — Во(™). (с) Так как ( "л) = (",), вероятности равны п((п 1)'т (Р (т ( 2 )) 2Р~-'(т (2))) ' г е!л 29. Из предыдущего ответа н упр. 5.1.1-15 палучаелл Ь„о(з) = п'.
(п — 1)! з( з Я(1 — з) х ,, х (1 — з")). Когда г = 1, и! в наших предыдущих рассуждениях преобразуется в п!/2 ичислорешенийдоО < зл « . зл < зол~ < < з„сел+. +з =траяна числу решений до О < зл — 1 « - зл — Ь < зл ~ — Ь < < з„— и+ 1 с (з~ — 1) + порядок 0((т/и) "ю). ни олин из других корней единицы не появляется более и/2 раз как полюс знаменателя. Следовательно, была допущено существование *'тяжелых хвостов" (см.
СЛХагЬ, з9,4) и выполнено интегрирование по всем Ь Формулы / е ' гзр 8! = (.у 1)(.! — 3) . (1)л/йх х(у — четное) и и! = (и/е)" л/2яиехр( —,' и ' + 0(п л)) достаточны для завершении вычислений. С д (т) = р (т — (" л ') ) вместо р„(т) вычисления производятся таким же образом, но с сп возрастающим, как -п(и'ж — и Ы ), и с дополнительным множителем ехр(-р( л )). Получаем т" 'е 4м / 13оэ 169а' — 20!ба — 1728а' + 41472п -л ) и!(и — 1)! (, 288и 165888пэ -!- 0(и ) что совпадает с формулой для р„(т), но о заменено на — о. Действительно, если определить р„(т) = г„(2т + ("+')) и д„(т) = г„(2т — ("л )), производящая функция Я,(х) = ~„гл(х~) = П„",(х " — х") ' удовлетворит равенству Я (1/е) = (-1)" Н~(х). Отсюда следует формула двойственности г„(-т) = ( — 1)" 'г (т) в том смысле, что уравнение превратится в равенства, когда г„(т) выражается через полинам по т и корни единицы Поэтому люжно сказать, что д„(т) = р„( — т).
В общем случае интерпретацию такай двойственности можно найти в работе Дж. Пойа (см. С. Рб!уа, МагЬ. Ее!сзсЬгуй 29 (1928), 549 — 640, 544). (Дополнительно см. работу Дж. Шекерса (С. Зхейегее, лгиаггег!у Х ЛуаСЬ. Ох/ог8 2 (1951), 85-108; 4 (1953), 96-111 ) Точное значение д„(т), когда гп = 2лл и п = 512, равно 7.080693469590264 094... х 10™; наша аппроксимация дает оценку 7.080693501 к 10'л' . Вероятность того, что критерий дней рождения обнаружит И = 0 разностей, равна Ь„ае(т)/т" = и!(гл — 1)!т' "йк(т) = е М+ 0(и ') согласно УпР 28, посколькУ вклад от Ь ш(т) равен ж фе Г = О(и '). Включение множителя д (х) = 2 "„,'(х ' — 1) в подынтегральное выражение д„(т) дает тот же эффект, что и умножение результата на и+0(п '), поскольку д„(е е+пл) = (")р+ 0(илр ) + ЙО(п 5) — 11~0(и 5~) + Подобным же образом экстрамножитель 2,«,л<„(х л — 1)(х ' — 1), по существу, умножает на -'и"р = -'п~ и добавляет О(и ').
Другие вклады в вероятность того, что В = 2, имеют порядок О(и '). Таким же образом найдем, что вероятность получения г равных разностей равна е 7~(п/4) "/г!+ 0(и '), т. е. число равных разностей приближенно имеет распределение Пуассона. Более сложные члены возникают, если осуществить разложение до порядка 0(и л). 31. 79 дваицных разрядов содержат 24 множества троек (1!и 1' ьзл, У„еы), (У ам Уе.лзэ, К.-лле),, (1' еэл,1л ьлмУ~.лгл), плюс 7 дополнительных разрядов Уч лы,,У ьзо.
Последний двоичный разряд с равной вероятностью является 0 или 1, но в каждой группе троек с вероятностью -' двоичные разряды иллеют вид (0,0, 0) и с вероятностью з л — они будут иметь вид (О, 1, Ц. Поэтому производящая функция для суммы двоичных разрядов равна /(г) = (лтэх)~(-'-ф-)~~ (это полинам 55-й степени). (Данная формула не точна., строго говоря, она имеет вид (2л'/(г) — 1)/(2л' — 1), поскольку все 0-случаи исключены.) Коэффициенты 2~~/(х) легко подсчитать на вычислительной машине, и, следовательно, можно найти, что вероятность тога, что единиц больше, чем нулей, равна 18509401282464000/(2лл — 1) 0.51374 Замечанпе.
Это упражнение основано на открытии Ваттулайнена, Ала-Ниссила и Канкаала (см. работу Чаып!а!пеп, А!а-Х!эе!!а, апб КапЬаа!а, Раув!са! Вег!ев. Ееллегэ 73 (1994), 2513-2516), состоящего в том, что генератор Фибоначчи с запаздыванием не удовлетворяет более сложному критерию двумерного случайного блуждания. Заметим, чта и последовательность Уэ„, Уэ„ем .
не удовлетворяет этому критерию, поскольку она описывается тем же рекуррентным соотношением. Смещение в сторону единиц распростра- няется на подпоследовательности, которые состоят нз четных элементов, генерируемых последовательностью Х = (Хч-ы ш Х -г4) шоб2', ей присуща тенденция иметь больше случаев (... 10)г, чел» (... 00)г в двоичной записи.
Нет ничего магического в числе 79 в этом критерии Эксперименты показывают, что значимые отклонения в сторону единиц присущи также случайным блужданиям длиной 101, 1001 или 10001. Но формальное доказательство этого, веронтно, будет трудным. 1 3 г 1г 1 г.г 4 г 4 7 ск 11 р ф (',")(''," Г, множители (1+ 2гг+ бег+ 5г'+ 10гг+ 8ге+ г )/32, (1+ 2гг+ 7гг+ 7г~+ 15г~+ 25ге+ 29г~+ 28гз + 13г" + г'е)/128 и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
