появятся в последовательности (Jn), для алгоритма В будут выполняться неравенства V[{] < т/к, О <j <к, а также Y < т/к.

Доказательство. Пусть 5„ - множество позиций г, таких, что V[i] < т/к точно перед тем, как генерируется Хп, и пусть jn - такой индекс, что V[j„] 4- Хп. Если j„ Sn и Л = О, то Sn+i = SnU {jn} и jn+i > 0; если же j„ е 5„ и J„ = О, то S„+i = 5„ и jn+i = 0. После к + 2 последовательных нулей должно выполняться О € Sn я jn+i = 0. Тогда после "1 0*"*"" должно выполняться {0,1} С Sn и = 0; после "2 О*" выполняется {0,1,2} С5„ и =0; ИТ. д.

Следствие. Пусть / = (к + 7к - 2)/2. Если \> 1к, то либо алгоритм В обеспечивает длину периода А, либо последовательность {Хп) плохо распределена.

Доказательство. Вероятность того, что любая данная схема J длиной / не появляется в случайной последовательности длиной А, меньше, чем (1 - к~) < ехр(-/сА ) < е~; следовательно, фиксированные схемы могут появляться. После того как это произойдет, дальнейшее поведение алгоритма В будет таким же каждый раз, когда он достигнет этой части периода. (Когда А; > 4, то требуется А > 10\ поэтому данный результат чисто академический, но возможны также меньшие границы.)

29. Следующий алгоритм в худшем случае осуществляет около А операций. Но среднее время выполнения операций намного меньше; возможно, 0(logA;) или даже 0(1).

XI. Присвоить (ао,а\,...,ак) {xi,... ,Хк, т-1).

Х2. Пусть г - минимум для а; > О и г > 0. Реализуйте программу Y для j = г + 1, ..., к, пока ак > 0.

ХЗ. Если ао > ак, f{xi,... ,Хк) = ао; иначе, если ао > О, f{xi,... ,Хк) = ао - 1; иначе f{xi,...,xk) =ак. I

Y1. Присвоить I 4- 0. (Программа на шагах Y1-Y3 проверяет лексикографическое отношение {at,... ,ai+k-i) > {aj,... ,aj+k-i). Убывание ак необходимо, чтобы сделать это неравенство верным. Предполагается, что ak+i = ai, ajt+2 = аг и т. д.)

Y2. Если ai+i > aj+i, выйти из программы. Иначе, если j+l = к, присвоить а*, 4- at+i. Иначе, если ai+i = Oj+i, перейти к шагу Y3. Иначе, если j + I > к, уменьшить ак на 1 и выйти из программы. Иначе присвоить а 4- О и выйти из программы.

Y3. Увеличить Z на 1 и возвратиться к шагу Y2, если I < к.

Эта проблема впервые была решена Г. Фредриксеном (Н. FYedricksen) для тп = 2 [J. Combinatoria/ Theory 9 (1970), 1-5; А12 (1972), 153-154]. В этом частном случае алгоритм проще и может быть задан с /г-разрядным регистром. См. также работу S. Xie, Discrete Applied Math. 16 (1987), 157-177.

30. Из упр. 11 следует, что достаточно показать, что длина периода по модулям 8 равна 4(2*° - 1). Это будет выполняться тогда и только тогда, когда i2(2-i) i (до модулям 8 и f{x)), а также тогда и только тогда, когда i-i j {lo модулям 4 и f{x)). Запишем f{x) = fe{x) + xfo{x\ где /.(х) = А(/(х) + /(-х)). Тогда /(х) + f{-xf = 2f{x) (по модулю8) тогда и только тогда, когда/е(х)+х/о(х) = /(х) (помодулю4); ипоследнее условие имеет место тогда и только тогда, когда /е(х) = -х/о(х) (по модулям 4 и /(х)), так как /е(х) + х/о(х) = /(х) + 0{х~). Более того, работая по модулю 2 и /(х), мы получим /е(х) = /е(х) = х/о(х) = х2/о(х). Следовательно, /е(х) = х"]fo{x). Поэтому /е(х) = хfa{xY (по модулям 4 И /(х)), отсюда следует утверждение указания. Рассуждая подобным образом, можно доказать, что х*" = х (по модулю 4 и /(х)) тогда и только тогда, когда /(х) + /(-х) = 2(-1)*/(-х) (по модулю 8).

(b) Условие может выполняться только тогда, когда I нечетно и к = 21. Но в таком случае f{x) является первообразным полиномом по модулю 2, когда к = 2. [Math. Сотр. 63 (1994), 389-401.]

31. Соотношение Хп = (-1)"3" mod 2 выполняется для некоторых Y„ и Zn по теореме 3.2.1.2С. Следовательно, ¥„ = (У„ 24 + Уп-55) mod 2 и Z„ = {Zn-24 + Zn-ьь) mod 2". Так как Zk нечетно тогда и только тогда, когда Хк mod 8 = 3 или 5, из предыдущего упражнения следует, что длина периода равна 2~(2"* - 1).

32. Можно не обращать внимания на mod тп и вернуться к этому позже. Производящая функция g(z) = Xnz" - это полином, кратный 1/(1 - г"* - z); поэтому J2n nZ" = (5(2)+5(-г)) -это полином, деленный на (1-г2-2")(1-2+г") = l-2z4z - z°. Первое требуемое рекуррентное соотношение поэтому имеет вид Х2п = (2X2(-12) - А2(„-24) + A2(n-55))modTn. Аналогично 5]„ 2" = lig{z) + g(u>z) + g{u>z)), где w = ег/з, и можно найти, что Хзп = (ЗАз(„ 8) - ЗАз(„ 1б) + Аз(„ 24) + Аз(„ 55)) mod тп.

33. (а) gn+tiz) = zg„(z) (по модулю тп и 1 + г - г**) индукцией по (. (Ь) Так как г"" mod (1 + 21 - 2") = 7922 + г + Пг + 7152* + 362! is 36416 2102» + 1052 + 4622 + 1б2° + 12872 + 92 + 182 + 10012"° + 1202" + 2"" + 4552" + 4622° + I2O2 (см. алгоритм 4.6.1D), то получим А500 = (7922 + As Ч-----h 120А"54) modTn.

[Интересно сравнить подобную формулу Aies = (Ао + ЗА7 + Xi4 + ЗХ31 + 4Аз8 + А45) modTn с "прореженным" рекуррентным соотношением для (Аз„) в предыдущем упражнении. Метод Люшера для генерирования 165 чисел, в котором используются только первые 55 чисел, очевидно, не лучше идеи генерирования 165 чисел с помощью только Аз, Хб, ..., Ai65.]

34. Пусть до = О, gi = 1, g„+i = cg„ +ag„ i. Тогда выполняется равенство (° 1)" = ("tgn gill) " - (Qn+iXo + aq„)/{qnXo + aq„-i) и x" mod/(i) =g„i-f ag„ i для n > 1. Таким образом, если Ао = О, то An =0 тогда и только тогда, когда i" mod /(i) - не равная нулю константа.

35. Из условий (i) и (ii) получаем, что f{x) неприводима. Если /(i) = (1 - ri)(i - гг) и Г1Г2 ф О, то i" = 1, если п Ф Г2, и 1 = Г1, если п = гг.

Пусть - первообразный корень поля, имеющего р элементов, и предположим, что = Ск + йк. Квадратичные полиномы, как было установлено, - это точно полиномы fk{x) = х - СкХ - ак, где 1 <к<р-1ик±р+1. (См. упр. 4.6.2-16.) Каждый полином появляется для двух значений к; следовательно, число решений равно

i(p - 1)П,\р+1,,простое(1 - 1/9)-

36. в данном случае А„ всегда нечетно, поэтому Х существует по модулю 2°. Последовательность (qn), определенная в ответе 34, имеет вид О, 1, 2, 1, О, 1, 2, 1, ... по модулю 4. Справедливы также дгп = qniqn+i +agn-i) и g2n-i = ag-i +ql, поэтому g2n+i -ag2n-i = (g„+i -ag„ i)(g„+i --ag„+i). Следовательно, g„+i -l-ag„+i = 2 (no модулю 4), когда n четно. Получим, что g2« - это нечетное кратное 2 и g2«+i - ag2«-i - это нечетное кратное 2+ для всех е > 0. Поэтому

д2« + ag2«-i = g2+i + адг» + 2" (по модулю 2+).

ИАгс-з = (g2c-2+i+ag2.-2)/(g2e-2+ag2.-2 i) 1 (по модулю 2), в то время как А2.-1 = 1. И обратно: необходимо, чтобы а mod 4 = 1 и с mod 4 = 2, иначе Агп = 1 (по модулю 8). [См. работу Эйхенауэра, Лехна и Топазогли (Eiciienauer, Leiin, and Topuzoglu, Math. Сотр. 51 (1988), 757-759).] Младший двоичный разряд этой последовательности имеет короткий период, поэтому предпочтителен обратный генератор с простым модулем.

37. Можно предположить, что bi = 0. Из упр. 34 следует, что типичным вектором в V будет вектор

(i, {siX + as2)/is2X + as2),(sax + asd)l{sdx + asd)),

где Sj - qbj, sj - Qbj+i, Sj = qbj-i- Он принадлежит гиперплоскости Н тогда и только тогда, когда

ггг Tdtd 1-1 I -1 , ч

ПХ Ч---\-----\--= Го - r2S2S2----- rdSdSd (пО МОДуЛЮ р) ,

X U2 X Ud

где tj = а - asjSjSj" = -{-aysj и Uj = asjsj. Но это соотношение эквивалентно полиномиальной сравнимости степени < d, поэтому для d + 1 нельзя найти значения х, если это соотношение не выполняется для всех х, включая различные точки i = иг, • • •, X = Ud. Следовательно, гг = • • • = r<i = О и п =0. [См. работу Ю. Эйхенауэр-Геррмана (J. Eichenauer-Herrmann, Matii. Сотр. 56 (1991), 297-301).]

Замечание. Если рассмотреть матри1;у М размера (р + 1 - d) х (d + 1) со строками {{l,vi,... ,Vd) I {vi,...,Vd) e V}, TO это упражнение будет эквивалентно утверждению, что любые d + 1 строк матрицы М линейно независимы по модулю р. Интересно было бы построить график точек (Xn,Xn+i) для р и 1000 и О < п < р; тогда можно увидеть больше следов от окружностей, чем от прямых линий.

РАЗДЕЛ 3.3.1

1. Есть к = 11 категорий, поэтому следует использовать строку и = 10.

49 > 49 49 49 49 49 49 49 49 49 49

- V = 7 только немногим больше, чем значение, полученное при использовании хороших игральных костей! Существует два объяснения, почему мы не определили, что игральная кость поддельная, (а) Новые вероятности (см. упр. 2) в действительности не очень далеки от тех, которые заданы в (1). Сумма показаний двух игральных костей стремится к сглаживанию вероятностей. Если подсчитать вместо сумм каждую из 36 возможных пар значений, скорее всего, можно будет определить разни1;у быстрее (предполагая, что игральные кости различимы). (Ь) Намного более важное объяснение состоит в том, что п является слишком малым для того, чтобы фиксировать значимое различие. Если бы этот же эксперимент был проведен для достаточно большого п, то подделка была бы раскрыта (см. упр. 12).

4. Ps = y2 для 2 < S < 12 и S / 7; р7 = . Значение V равно 1б. Оно попадает между значениями 75% и 95% табл. 1, так что критерий подтверждает гипотезу, хотя выпало слишком мало семерок.

5. K}q = 1.15; = 0.215. Значения находятся приблизительно между уровнями 94% и 86% и поэтому не противоречат предположению, но они очень близки. (Данные для этого упражнения взяты из приложения А, табл. 1.)

6. Вероятность, что Xj < х, равна F(x), поэтому имеем биномиальное распределение, обсуждавшееся в разделе 1.2.10. F„(x) = s/n с вероятностью (") F{x){l - F(i))"~*; среднее равно F{x)\ стандартное отклонение - i/F(i)(l - F(x))/n [см. равенство 1.2.10-(19)]. Это указывает на то, что немного лучшей статистикой была бы

C+ = твх {Fn{x)-F{x))/y/F{x){l-F{x));

-<х<х<<х

см. упр. 22. Можно вычислить среднее и стандартное отклонения для F„(y) - F„(i) при X < у и получить ковариацию между F„(i) и Fn{y). Используя данные факты, можно показать, что при больших п функция F„(i) ведет себя, как броуновское движение, и методы из этого раздела теории вероятностей можно использовать для ее изучения.