коэффициента при 2;("+"/ единицам, а вторую - нулям. (Этот коэффициент равен

34. Число строк длиной п, не содержащих заданные двухбуквенные подстроки или пары подстрок, - это коэффи1Ц1енты при z" в соответствующей производящей функции. Они могут быть записаны в виде се"т" +0{1), где сиг можно разложить по степеням е = 1 /т.

(Здесь a,b,c,d обозначают буквы и р(г) = 1 - (т - l){z + z). Оказывается, что эффект исключения {ab,ba} или {аа,аЬ} эквивалентен исключению {aa,bb}; исключение {аЬ,ас} эквивалентно исключению {ab,cd}.) Пусть Sn - коэффициент при z" в случае j и пусть X - общее число двухбуквенных комбинаций, которые не появляются. Тогда

ЕХ = {mSi + mSi>)/m и

EX = {mSi + m(Sf + 65) + 2mHsL + S< + S") + mSi)/m".

35. (a) ESm = iV-Eo E7=V n+j = N-Z7=oEnZoZn+j = NEJo = i/N, так как J]! Z„+j = 2" - (2*=- - 1) = 1.

(b) Пусть 4* = oif* + • • • -b ojt. Определим линейную функцию /, как и в первом ответе к упр. 3.2.2-16. Тогда У„ = а отсюда следует, что Yn+i + Yn+] = /(4"") + /(4"+-) = /(4"+ + С) = fiCoi) (по модулю 2), где а не равно нулю, когда г ф j (по модулю iV). Отсюда ESl= N E?=V Е7=о Eno n+.n+j = JV-TJo Eo n+i -2 Eo<.<,<™ E no n) = m - m(m - l)/iV.

(c) ЁЕ7Го Zn+, = E7=o En+, = 0 и Е(Е7Го Zn+jf = E7=o E7=o Zn+Zn+j =

E7=o E-n+j +Eo<i<j<m(E»+>)(E.r.+j) = m, когда каждое действительно случайно. Таким образом, среднее и дисперсия Sm очень близки к истинным значениям, когда m < iV.

(d) ESl-= ЕТГо E7="o Е7="о Eo Zn+hZn+rZn+j. Если любые h, i и j равны, сумма по п равна 1; следовательно,

ESl =

\ 0<h<i<j<m п=0 /

0<h<i<j

Так же, как и в (Ь), покажем, что сумма по п равна 1, если ф 0; иначе она рав-

на -N. Таким образом, Е5 = тЗ-6В(У + 1)/У, где В = Eo</.<i<j<m[f =0] =

So<i<j<m[l -Ь 4 -Ь 4 = 0] (m - j). Наконец заметим, что 1 -Ь = f- тогда и только тогда, когда /(4+) = f{ij) для О < / < fc. Предполагаем, что О < г < j < iV.

(е) Для г = 31 и j = 55 появляются только ненулевые члены; значит, В = 79 - 55 = 24. (Следующий ненулевой член появится, когда г = 62 и j = 110.) В настоящей случайной ситуации е Sm должно быть равно О, так что значение Е S79 и -144 определенно говорит о неслучайности. Любопытно, что это значение отрицательное, хотя в упр. 31 показано, что 579 обычно положительное. Значение 579 стремится быть основательно отрицательным, когда оно оказывается ниже 0.

Литература. IEEE Trans. IT-14 (1968), 569-576. M. Matsumoto and Y. Kurita, ACM Trans. Modeling and Сотр. Simul. 2 (1992), 179-194; 4 (1994), 254-266. M. Мацумото и Й. Курита утверждают, что генераторы с троичным основанием не удовлетворяют таким критериям, проверяющим распределения, даже когда смещение достаточно больщое. См. также работу АСМ Trans. Modeling and Сотр. Simul. 6 (1996), 99-106, в которой они демонстрируют длинную подпоследовательность низкой плотности.

РАЗДЕЛ 3.3.3

2. См. упр. 1.2.4-38 и 1.2.4-39(а, Ь, g).

3. ((i)) = - Еп>1 ;;sin27rni, ряд сходится для всех х. (Представление в (24) можно рассматривать как" "конечный" ряд Фурье в случае, когда х рационально.)

4. dmax = 2° • 5. Заметим, что неравенство Xn+i < Хп имеет вероятность j + е, где

£<d/(2-10)<l/(2-5).

Следовательно, каждый генератор с потенциалом 10 приемлем с точки зрения теоремы Р.

5. Промежуточный результат:

Ех s(x) 1 , N , пг

m m 12 4

...... - . 2m 2m

0<a:<m

6. (a) Используйте индукцию и формулу

<ь) и-«"-*-((¥)) =-((А-В - ((t))-4-()-

7. Положите m = Л, п = fc. А: = 2 во второй формуле упр. 1.2.4-45:

е (¥-((¥))-0 (¥-Ш 4) - е ((ВЧ) >-м.-...

0<j<k 0<j<h

Суммы в левой части упрощаются, а после стандартных преобразований получим h2fc hfc + g + A+ l k, 0) - a(fc. Л, 0) + a(l, fc, 0) = - hk.

Так как a(l,fc,0) = (fc - l)(fc - 2)/fc, это приводит к закону взаимности.

8. См. работу Duke Math. 3. 21 (1954), 391-397.

9. Начните с интересного тождества

ELfcp/d Lfc-?/rJ + yikqlp\ [kr/p\ + ELfcr/gJ Lfcp/-?J = (P -!)(-? - i)(r -1),

fc=0 fc=0 *;=0

для доказательства которого можно применить простой геометрический метод, предполагая, что pLq, qLrnrLp. См. работу У. Дитера (U. Dieter, Abh. math. Sem. Univ. Hamburg 21 (1957), 109-125).

10. Очевидно, что из (8) следует равенство а{к - h, fc, с) = -а(Л, fc, -с). Заменим j на к - j в определении (16), чтобы доказать равенство (т(Л, fc,c) = (т(Л, fc, -с).

0<j<dfc 0<i<d

0<j<fc

рования no i.

(()) - (()) -1 - нт-

12. Так как (()) принимает те же значения, что и (()) в другом порядке, неравенство Коши влечет неравенство a{h,k,cf < cr{h,k,0) и сг{1,к,0) может быть легко просуммирована непосредственно (см. упр. 7).

- "<M,.).2tt=¥ е,„-.::;,-,1-->-к(т)).

если hh! = 1 (по модулю fc).

14. (2* - 3 2° -Ь 5)/(2™ - 1) и 2~. Весьма удовлетворительное глобальное значение вопреки локальной неслучайности!

15. Замените с в (19) на [cj["c].

16. По индукции можно доказать, что тождество, приведенное в указании, эквивалентно т\ = prmr+i -)-pr-inir+2 для 1 < г < t. (См. также упр. 4.5.3-32.) Теперь заменим Cj на Ej<r<t сравним коэффициенты при 66 в обеих частях тождества, которое необходимо доказать.

Замечание. Для всех показателей е > 1 аналогичные соображения дают

у- = - Е (-1)+ь.р.-ь

17. В этом алгоритме выполняются равенства к = rrij, h = rrij+i, с = Cj, р = pj-i, р =

Pj-2,S = {-iy + ДЛЯ j = l, 2, ...,t + l.

Dl. [Инициализация.] Присвоить A <- О, В <- h, p <- 1, p <- О, s <- 1. D2. [Деление.] Присвоить о <- [fc ij, Ь <- [c/hj, г <- с mod h. (Теперь о = Oj, Ь = bj и r = Cj+i.)

D3. [Накапливание.] Присвоить А 4- A-)-(a-6b)s, В <- B + 6bp{c. + r)s. Если г / О или с = О, присвоить А <- А-Зя. Если h = 1, присвоить В 4- В+ря. (Здесь вычитаем 3e(mj+i,Cj) и также принимаем во внимание члены E(~l)V"*j"*j+i)

D4. [Подготовка к следующей итерации.] Присвоить с <- г, я <--s; присвоить г <-

к - ah, к h, h +- г; присвоить г ар + р, р р, р г. Если h > О, возвратиться к шагу D2.

По окончании работы этого алгоритма р будет равно истинному значению fco величины fc, так что требуемый ответ - А + В/р. Окончательное значение р будет равно h, если S < О, иначе р будет равно ко - h. Хорошо было бы, чтобы В благодаря подходящей корректировке А не выходило из области О < В < fco. Поэтому используются только операции с обычной точностью (с двойной точностью выполняются умножение и деление), если fco - число, заданное с обычной точностью.

18. Можно моментально увидеть, что формула

S{h, fc, с, z) = Eo<j<.(b7fcJ - LO - )AJ) ({{hj + c)lk)) определена для всех z > О не только тогда, когда fc > z. Записав [j/fcj - L(j ~ z)/k\ = f -Ь (()) - ((fc)) -Ь <5jo - \{) и выполнив суммирование, получим

S(M,c,., = f (()) . i„M,.. .0, - . l((f)) - K()).