+ (sk - к) + {sk+i - fc) Н----+ (Sn - n + 1) = m - (2) - fc. Следовательно, b„i(z) =

n! (n - 1)! Eliiz - z") z(2)/(l 2)... (1 - г"). Аналогично можно показать, что

Jvfe Е (-Л(--)+Е(-)(*--))

(1-2)...(1-2")-

Можно получить Ьпг {z) для произвольных г из формулы

n!(n-l)!z" ci...cn-i(l-z)...(l-z") • U>

где cfc = l + bfc +bjtbjt i + • +6)1... 6261 = l + bfccfc-i. (Частный случай для w = \ интересен, поскольку левая часть суммируется до (1 - z)-"/n!.)

30. Это хорошая задача для метода перевала [см. работу Н. Г. де Брейна (N. G. de Bruijn, Asymptotic Methods in Analysis (Nortii-Holland, 1961), Chapter 5)]. Справедливо равенство Pn(m) = /e(, где f(z) = -mln - ELi Ml - )- Пусть p = n/m и <J = /ш; интегрирование по пути z = е"""" дает р„{т) = JJgexp{f{e~"))dt. Удобно использовать равенство

.9(«е) = Е + Г "V(«e-")d«,

где g = g(z) - любая аналитическая функция и i? - оператор z-. Когда функция вычислена в точке е, результат будет таким же, как и тогда, когда д{е) дифференцируется j раз по Z. Этот принцип приводит к получению формулы

Пе-П = -mU = 1] + $ + (-1) Е Е -ЙТР- fc=i i>j

из другого удобного равенства,

BnZ"

п>1

Таким образом, получена асимптотическая формула для подынтегрального выражения ехр/(6-"+"*) = ехрЕ -fie")) = e+f" ехр{Ш - c,t - + ),

где С1 = (iiBi + 2i2±i!i±ii52p)<J + 0{п~) и т. д., и оказывается, что cj = 0{п-) для j > 8. Вынеся за скобки константу, получим

П-") = -ехр(-УУ -Лр]

2ж 27гп!р"е-™ i6t f>t " /

,уКт"-е"+° 18а-а lOSa - Зба» + а"

= 2пп\пп- + +-10368;-+(" V

что приводит к интегралу, подынтегральное выражение которого является экспоненциально малым, когда jtj > п. Можно пренебречь большими значениями t, поскольку разложение на элементарные дроби показывает, что подынтегральное выражение имеет

порядок 0{{т/п)"). Ни один из других корней единицы не появляется более п/2 раз как полюс знаменателя. Следовательно, было допущено существование "тяжелых хвостов" [см. CMath, §9.4] и выполнено интегрирование по всем t. Формулы е~ t- dt = и - l)(i - 3)... (1)\Л7Г [j - четное] и п! = (n/e)"v/27mexp(n" + 0{п~)) достаточны для заверщения вычислений.

С qn{m) = Pn(m- ("2)) вместо Рп{т) вычисления производятся таким же образом, но с ci, возрастающим, как а{п - п~), и с дополнительным множителем ехр(-р(")). Получаем

, , т"-е-"/ л 13q ХбЭа" - 2016q - 1728q+ 41472q "" п!(п-1)! +-165888-V

что совпадает с формулой для рп{т), но а заменено на -а. Действительно, если определить р„(т) = Гп(2т + и qn{m) = r„(2m- ("J)), производящая функция

Rn{z) = Е™"(™) = nfc=i(" -*)" удовлетворит равенству Rn{l/z) = (-l)"fl„(z). Отсюда следует формула двойственности г„(-т) = (-1)" Vn(m) в том смысле, что уравнение превратится в равенство, когда Гп{т) выражается через полином по m и корни единицы. Поэтому можно сказать, что qn{m) = Рп(-т). В общем случае интерпретацию такой двойственности можно найти в работе Дж. Пойа (см. G. Polya, Math. Zeitschrift 29 (1928), 549-640, §44). (Дополнительно см. работу Дж. Шекерса (G. Szekeres, Quarterly J. Math. Oxford 2 (1951), 85-108; 4 (1953), 96-111.)

Точное значение qn{m), когда m = 2" и n = 512, равно 7.08069 34695 90264 094... x 10"; наща аппроксимация дает оценку 7.080693501 х Ю.

Вероятность того, что критерий дней рождения обнаружит R = О разностей, равна bnoo("i)/"i" = п! (п - 1)! m~"g„(m) = е""" + 0{п~) согласно упр. 28, поскольку вклад от bnoi{m) равен и e"""* = 0{п~). Включение множителя gn{z) = YZii ~ 1) в подынтегральное выражение qn(m) дает тот же эффект, что и умножение результата на +0{п-), поскольку g„(e-+) = ()р + 0(nV) + гЮ{пЧ) - «0(п<5) + • . Подобным же образом экстрамножитель Jjy.j..,j(z~--l)(z~* - l), по существу, умножает на пр = и добавляет 0{п~). Другие вклады в вероятность того, что Д = 2, имеют порядок 0{п~). Таким же образом найдем, что вероятность получения г равных разностей равна e~"{a/4Y/r\ + 0(п~), т. е. число равных разностей приближенно имеет распределение Пуассона. Более сложные члены возникают, если осуществить разложение до порядка С>(п").

31. 79 двоичных разрядов содержат 24 множества троек {Y„,Y„+3i,Y„+ss}, {Yn+i,Yn+32,

Yn+бб}, {Yn+23,Yn+54,Yn+7s}, ПЛЮС 7 дополнительных разрядов Yn+24, ,Yn+30-

Последний двоичный разряд с равной вероятностью является О или 1, но в каждой группе троек с вероятностью двоичные разряды имеют вид {О, О, 0} и с вероятностью I они будут иметь вид {0,1,1}. Поэтому производящая функция для суммы двоичных разрядов равна f{z) = ()(f) (это полином 55-й степени). (Данная формула не точна; строго говоря, она имеет вид (2/(z) - 1)/(2 - 1), поскольку все О-случаи исключены.) Коэффициенты 2f{z) легко подсчитать на вычислительной машине, и, следовательно, можно найти, что вероятность того, что единиц больше, чем нулей, равна 18509401282464000/(2" - 1) и 0.51374.

Замечание. Это упражнение основано на открытии Ваттулайнена, Ала-Ниссила и Канкаала (см. работу Vattulainen, Ala-Nissila, and Kankaala, Physicai Review Letters 73 (1994), 2513-2516), состоящего в том, что генератор Фибоначчи с запаздыванием не удовлетворяет более сложному критерию двумерного случайного блуждания. Заметим, что и последовательность Угп, У2п+2, ... не удовлетворяет этому критерию, поскольку она описывается тем же рекуррентным соотношением. Смещение в сторону единиц распростра-

няется на подпоследовательности, которые состоят из четных элементов, генерируемых последовательностью Хп = {Xn-ss ± Хп-24) mod 2; ей присуща тенденция иметь больше случаев (... 10)2, чем (... 00)2 в двоичной записи.

Нет ничего магического в числе 79 в этом критерии. Эксперименты показывают, что значимые отклонения в сторону единиц присущи также случайным блужданиям длиной 101, 1001 или 10001. Но формальное доказательство этого, вероятно, будет трудным. После 86 шагов производящая функция равна (t )7(i-(-2z +4г +г затем получим множители (1 + 2z4 5z + Ъz + 10z4 Зг" + z)/32, (1 + 2z4 Iz + Iz + 15z4 25z« + 29z + 28z* + 13z* -b z)/128 и т. д. Анализ становится все более и более сложным с удлинением блужданий.

Интуитивно ясно, что преобладание единиц на первых 79 шагах будет продолжаться столько, сколько числовые подпоследовательности умеренно колеблются между О и 1. Сопутствующая диаграмма показывает результаты более простого случая, а именно - использования генератора Уп = (Уп-2 + Уп-п) mod 2, который можно легко проанализировать. Для него случайные блуждания длиной 445 имеют 64% шансов закончиться справа от начальной точки. Это смещение пропадет только тогда, когда длина блужданий возрастет до половины периода (после чего, конечно, нули станут более вероятны, хотя в полном периоде будет недоставать одного нуля).

0.7 0.6 0.5 0.4 0.3

m = 0 256 512 768 1024 1280 1536 1792 2047 Вероятности, что число 1 превосходит число О в случайных наборах из т чисел, когда Уп = Уп-2 ® Уп-11-

Техника отбрасывания Люшера (Liischer) может использоваться для того, чтобы избежать смещения в сторону единиц (см. окончание раздела 3.2.2). Например, со смещениями 55 и 24 отклонений от случайности в наблюдениях за случайными блужданиями длиной 1001 нет, если генерировать числа группами по 165 и использовать только первые 55 чисел.

32. Нет, если они принимают значения (-1 - 2е, е - 2е, 1 - 2е) с соответствующими вероятностями (5 - е, е, 5). Тогда А-ЬУ > О с вероятностью (5 -Ье) < 5, если е достаточно мало. [Таким образом, два игрока в гольф могут быть в среднем одинаково сильными, но один из них может с большей вероятностью выиграть один раунд, тогда как другой с большей вероятностью выиграет два раунда. См. работу Т. М. Кавера (Т. М. Cover, Amer. Statistician 43 (1989), 277-278), в которой обсуждаются подобные феномены.]

33. По существу, нужно рассмотреть [z+-]{)>-"{У/{1 - z). Пусть m = к - 21, п = I а требуемые коэффициенты равны е- z{i-z) Д si) = niln(i) +

nln(") - ("*"*") Inz. Удобно (и разумно) интегрировать вдоль пути z = е", где = 4/( + Зп) и и = -1 +it для -оо < t < оо. Получим д{е") = -еи/2 + 4/2 + сзеи + С4еи + , где Ск = еЧ>д{1)/к\ = 0(1), а также 1/(1 - е") = -f- - В2еи/2\ -Вынеся множители из подынтегрального выражения и используя тот факт, что

1 ГИ 27Г1 J1-

1+ioo и/2 du I

= I И 27 с::: du = {-l){2k - тк - З)... WV, получаем

асимптотическую формулу I + (27г)-/п(т + Зп) + 0{{т + Зп)-). Если m -1- Зп четно, то справедлива та же асимптотическая формула, поскольку мы даем одну половину