(см. теорему 2.3.4.2G). Поэтому С имеет ранг -d и согласно упр. 3.3.1-25 достаточно показать, что ССС = С.

Нетрудно проверить, что Са/з = Р(а/3) Z]fc<f Гь(а,/3), где Тк{а,(3) - член, соответствующий пересечению, которое может произойти, если наложить /3 на q и сдвинуть ее на к позиций вправо:

Г( r.. \K{t + k:a,p:t + k)-\, если < 0; °~\K{a:t-k,t-k:p)-l, если fc > 0.

Например, если d = 2,t-b,a = 01101 и /3 = 10101, то выполняется Са = Р(0)Р(1) х (Р(01)~ -)-Р(101)~ -f-P(l)" - 9). Элемент q/3 ССС поэтому равен P{aj3), умноженному на

Y Е («) Е Е *(* l<Шa, Ь) - 1)Г,(7Ь, Р) 7=t-i о,6=0 fc<t ;<t

Если заданы fc и то произведение Tk{oi,a){K{a,b) - \)Ti{-yb,P) разлагается на восемь членов, к каждому из которых добавляется ±1, до умножения на Piyab), а затем выполняется суммирование по всем 70b. Например, сумма Р{уаЬ)К{2 : а, 70 : 2)К{а, Ь) х К{3 : 76, /3 : 3), когда а = oi .. .ot, /3 = bi .. .bt, 7 = ci .. .ct-i к t > 5, равна сумме P{c4 ... Ct-j), которая равна 1. Если t = 4, та же сумма должна равняться K{ai, bt), но не должна входить в сумму Р{уаЬ)К{2 : а, уа : 2){-1)К{3 : уЬ, /3 : 3). Поэтому результат равен нулю, если только не выполняется неравенство fc < О < в противном случае исключаются А(г : {j : а), (/3 : О : i)-K{i-l : {j : q), (/3 : l+l) : i-l), где г = mm{t+k, t-l) и J = max(0, fc + I). Сумма no fc и Z прибавляется к Со/з-

25. Эмпирическая проверка показывает, что на самом деле, когда (22) обобщено для произвольного t, отнощение соответствующих элементов Cf и СГСС очень близко к -t при t > Ь. Например, когда < = 6, все эти соотнощения лежат между -6.039 и -6.111; когда t = 20, то все они лежат между -20.039 и -20.045. Этот феномен требует объяснения.

26. (а) Вектор (Si,..., S„) является равномерно распределенной точкой в (п - 1)-мерном многограннике, определенном неравенствами Si > О, ..., Sn > О на гиперплоскости Si + • + Sn = 1. Легко доказать по индукции, что

Tdti Hdt Г dtn-г [1 - <1-----tn-i>Sn]= "~Г-1М ""

Чтобы получить вероятности, разделим этот интеграл на его значение в частном случае, когда Si = • • = s„ = О [см. работу Бруно де Финетти (Bruno de Finetti, Giornaie Istituto Italiano degli Attuari 27 (1964), 151-173)].

(b) Вероятность того, что S(i) > s, равна вероятности Si > s, ..., Sn > s.

(c) Вероятность того, что Sk) > «, равна вероятности, что по крайней мере fc - 1 из Sj будет < S. Следовательно, 1 - Fk{s) = Gi{s) + + Gfc i(s), где Gj{s) - это вероятность, что точно j разностей < s. Из соображений симметрии Gj{s) равно ("), умноженному на вероятность того, что Si < s, ..., Sj < s, Sj+i > s, Sn > s, и эта вероятность равна Pr(Si < s,...,Sj-i < s,Sj > 0, Sj+i > s,...,S„ > s) -Pr(Si < s,...,Sj-i < s,Sj > s,...,Sn > s). Повторное применение (a) показывает, что Gj{s) = (;) E, C)(-l)-(l -in- l)s)l-; следовательно.

1 - Fkis)=E(;) ;)(-i"Hi - in - i)s):-\

в частности, наибольшая разность S(„) имеет распределение

[Между прочим, подобная величина ж" (п -1)! F„(i оказывается, является плотно-

cmt)W распределения суммы Ui-{-----hU„ равномерно распределенных случайных величин.]

(d) Из формул Es = r/J(l - F{s))s-ds и sl - ks)l-ds = к-п-{+)- находим ES(jt) = n~{Hn - H„-k) и с помощью алгебры получаем ES(\) = n~(n -Ь 1) х {Hi - Н1\ + {Нп - Hn-kf). Поэтому дисперсия Sk) равна п-\п + 1)-(я1 - Я<, -(Я„-Я„ 07")-

[Распределение Fk{s) впервые было найдено В. А. Витвортом (W. А. Whitworth), который сформулировал вопрос о распределении S(k) как проблему 667 в Choice and Chance (Cambridge, 1867) и дал ее решение в DCC Exercises in Choice and Chance (Cambridge, 1897). Витворт также нашел элегантный метод подсчета математического ожидания любого полинома от функции Gfc(s) = Fk{s) - Fk+i{s). Этот результат был опубликован в буклете, озаглавленном The Expectation of Parts (Cambridge, 1898), и включен в пятое издание Choice and Chance (1901). Упрощенные выражения для среднего, дисперсии и некоторых более общих статистик разностей были найдены Бартоном и Дэвидом (см. работу Barton and David, J. Royal Stat. Soc. B18 (1956), 79-94). Обзор методов, которыми статистики традиционно анализируют разности как ключи к возможным смещениям данных, приведен в работе Р. Пайка (R. Руке, J. RoysJ Stat. Soc. В27 (1965), 395-449).]

27. Рассмотрим многогранник в гиперплоскости Si -Ь • • • -Ь S„ = 1, определенный неравенствами Si > О, ..., Sn > 0. Он состоит из п! конгруэнтных подмногогранников, определенных упорядочением Sj (предполагается, что Sj различны), и операцией сортировки является от п! к одному складывание больших многогранников из подмногогранников, в которых Si < • • • < Sn- Преобразование, которое переводит (S(i),..., S(„)) в (Sl,..., Sn), является взаимно однозначным отображением, разлагающим дифференциальные объемы на п! частей. Оно образует вершины (, • • •, ), (О, i;, , (О,..., 0,1) под-

многогранников в соответствующих вершинах (1,0,..., 0), (0,1,0,..., 0), ..., (О,..., 0,1); линейное растяжение и искажение полностью приспособлены к процессу. (Евклидово расстояние между вершинами (О,..., О, 4,..., j) и (О,..., О, ,..., ) в подмногограннике равно - fc-i преобразование образует регулярный симплекс, в котором все п вершин находятся на расстоянии \/2.)

Поведение итерированных разностей легче понять, если проверить детали графически при п = 3. В этом случае многогранник является простым равносторонним треугольником, точки которого выражены в барицентрических координатах {x,y,z), X + у + Z = 1. На приведенном рисунке иллюстрируются два первых уровня рекурсивного разбиения этого треугольника. Каждый из 6 подтреуголь-ников помечен двузначным кодом pq, где р соответствует подходящей перестановке, когда {x,y,z) = {Si, Si, S3) рассортированы в виде (S(i), S(2), S(3)), а q соответствует перестановке следующей стадии, когда SJ,

(О, О, 1)

х> Z

(1,0,0) х>у

У> Z

х<у (О, 1, 0)

Sj и S3 рассортированы в соответствии со следующим кодом:

0: x<y<Z, 1: x<z<y, 2:y<x<z, 3: y<z<x, 4:z<x<y, Ъ: z<y<x.

Например, для точек подтреугольника 34 выполняются неравенства S2 < S3 < Si и S3 < Sl < Sj. Этот процесс можно продолжить до получения бесконечного числа уровней; все точки треугольника с иррациональными барицентрическими координатами вследствие этого получат единственное представление в системе счисления с основанием 6. Четырехгранник аналогично может быть разделен на 24, 24, 24, ... подчетырехгран-ников; в общем случае эта процедура образует представление с основанием п! для любого (п - 1)-мерного симплекса. Когда п = 2, процесс особенно прост: если х {О, , 1}, при преобразовании образуется разность (ж, \-х) = (х, у) в {2х mod 1, 2у mod 1) либо {2у mod 1, 2х mod 1) в зависимости от того, будет ли х < у или х > у. Повторные испытания - это, по существу, сдвиг бинарного представления влево на один разряд, который, возможно, дополняет результат. После не более чем е + 1 итераций на е-разрядные числа процесс должен сойтись к фиксированной точке (0,1). Перестановочное кодирование для п = 2 соответствует просто свертке и растягиванию линии; первые четыре уровня разбиений имеют следующие четырехразрядные коды.

(0,1) I-.--.--.--.-1-,-,-.-1-.--.-1 (1,0)

0000 0001 ооп 0010 оно 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

Эта последовательность точно совпадает с двоичным кодом Грея, рассматриваемым в разделе 7.2.1. В общем случае в перестановочном коде в системе счисления с основанием п! для п-симплекса смежные области имеют идентичные коды, за исключением одной цифры. После каждой итерации разностного преобразования в представлении каждой точки удаляется крайняя слева цифра. Заметим, что равные разности дней рождения - это точки около границы разложения на первом уровне.

Фундаментальное преобразование из (Si,...,Sn) в (Si,...,Sn) подразумевается в доказательстве Витворта предложения LVI в пятом издании Choice and Chance (см. ссылку на литературу в ответе к упр. 26). Сначала оно было подробно изучено Дж. Дурбиным (J. Durbin, Biometriia 48 (1961), 41-55), которого вдохновил подобными построениями П. В. Сухатме (Р. V. Sukhatme, AnnaJs of Eugenics 8 (1937), 52-56.) Перестановочное кодирование для повторных разностей было введено Г. Э. Даниелем (Н. Е. Daniels, Biometri/ca 49 (1962), 139-149).

28. (а) Число разбиений m на п различных положительных частей равно рп{ш - ("J)), что следует из упр. 5.1.1-16. Эти разбиения могут быть переставлены п! способами, чтобы образовать п-мерные строки (j/i,..., j/n) с О = t/i < j/2 < • • • < j/n < пг, и каждая из этих п-мерных строк приводит к появлению (п - 1)! п-мерных строк, таких, что j/i = О и О < 2/2, •.., j/n <т. Добавим константу по модулю т к каждому yj, что позволит сохранить разность. Отсюда Ьпоо(пг) = mn!(n - l)!p„(m - ("2)).

(b) Нулевые разности соответствуют щарам в одной и той же урне, и я - 1 - их вклад в число равных разностей. Поэтому Ьпг»(пг) = {„" j} b(n-s)(r+i-s)o(»n)-

(c) Так как = (2), вероятности равны

n!(n-l)!m=-"(p„(m-(" + l))-lp„-i(m-(;))).

29. Из предыдущего ответа и упр. 5.1.1-15 получаем b„o{z) = п! (п - 1)! zi 2 )/((! - z) х ... x (1 - z")). Когда г = 1, п! в нащих предыдущих рассуждениях преобразуется в п!/2 и число рещений до О < si < • • • < sjj < Sk+i < < Sn с si + + Sn - m равно числу рещений доО<«1-l<-<sjt-fc< s+i - к < • • • < sn - n -Ь 1 с (si - 1) -Ь