где d = gcd(/i, к). [Эта формула позволяет выразить вероятность того, что X„+i < Хп < а при заданном а в терминах обобщенных сумм Дедекинда.]

19. Требуемая вероятность равна

\x-l3 \/ six)-а s{x)-p

- ™- е (()) - (()) - -

- (()) - (()) - -

/3 - q /3 - q 1 / , , , ,

=-----1- -- а(о, т,с + аа - а ) - а(о, т,с + аа - р )

т т 12т \

+ а(о, т, с + о/З - /3) - <г{а, т, с + о/З - а)) + «,

где е < 2.5/т.

[Этот подход предложен У. Дитером (U. Dieter). Разница между истинной вероятностью и идеальной величиной ~° ограничена величиной Ej=i оу/4т в соответствии с теоремой К. Обратно, выбирая а, /3, а, 0 приближенно, получим разницу, равную по крайней мере половине этой границы, когда существуют большие частичные отнощения, если учитывать тот факт, что теорема К является "наилучшей из возможных". Заметим, что, когда о и \/т, разница не может превышать 0(1 т), так что даже локально неслучайный генератор из упр. 14 будет хорошо выглядеть для критерия серий для полного периода. Это объясняет, почему мы должны требовать, чтобы разница была очень малой.]

20. Ео<.<тГ( - s{x))lm]\{s{x) - s{s{x)))lm]lm = Eo<x<m(( - +

(((bx+c)/m)) + )((s(x)-«(«(x)))/m+((a(bx+c)/m)) + i)/mHx/m = ((x/m)) + i-i<J(x/m), s{x)/m = {{{ах+с)/т)) + -Щ{ах+с)/т), s{s{x))/m = {{{ax+ac+c)/m))+- Щ{ах + ac + c)/m). Положим, что s{x) = s{s{x")) = 0 и d = gcd(b, m), тогда сумма сведется к виду

- ((())-((а)ч($))ч())-(())-((а)-о.

где Si = а{а,т,с), S2 = сг{а,т,ас + с), S3 = а{аЬ,т,ас), S4 = ст(1,т, 0) = (т - 1) х (т - 2)/т, Ss - (7{а,т,с), Se = m,c), S7 = -ст(о - 1,т,ас) и Ss = -(т(о(о - 1), т, (о)с), если аа = 1 (по модулю т). И окончательно

е (())(())

0<а:<т

= 12d

е..(())(())

0<x<m/d

=4"<»*".->--S((t))-4())).

где Со = cmodd. Общая сумма будет составлять около , когда d мало и когда все дроби а/т, {а тоАт)/т, {abmodm)/m, Ь/т, {а - 1)/т, {а{а - l)modm)/m, {{ad) modm)/m имеют малые частичные отношения. (Заметим, что а-1 = -6 + 6 - • • •, как в упр. 3.2.1.3-7.)

21. Сначала заметим, что основной интеграл точно разлагается следующим образом:

Г"+ , , 1 П в п\ п-в

Sn = J х{ах + в} dx =-(--- + -), если X. = -;

s = l\{ax + e}dx = so + si + --- + s.-i+f{ax + e)dx=-l + +.

-в/а

Поэтому C = {s- (i))/( - (i)) = (1 - 66 + 6в)/а.

22. Неравенство s{x) < х выполняется на непересекающихся интервалах [-Еу)! • • frf )> • • •, [7 • • 1), имеющих общую длину, равную

(Й)-е()---«--«4

0<j<a-l 0<j<a

23. Справедливо s{s{x)) < s{x) < х, когда х находится в [f-frf) и ах + в - к принадлежат интервалам .. jf) для О < j < к < а или когда х принадлежит .. 1)

и ах + в-а принадлежит либо ff) Для О < j < [aJ, либо ["" --в). Требуемая вероятность равна

0<j<fc<a 0<j<[a9\

1«±1 (0Ла.}-..-1)),

1 j 2.

~ 6 6а 2а а2

т. е. I + (1 -Зе--Зе)/6а--0(1/а) для больших а. Заметим, что 1 -36 +36 > \, поэтому в не может быть выбрано так, чтобы сделать данную вероятность близкой к требуемой.

24. Поступите, как в предыдущем упражнении; сумма длин интервалов равна

V ji 1 /a + t-2\

а-Ча-1) a-i(a-l)V t )

Ча-1) а-Ча-1)

Чтобы подсчитать среднюю длину, положим pk равным вероятности того, что длина серии > fc. Тогда среднее равно

E sr(a-\-k - 2\ 1 fay а

k>i~hS /а=-Ча-1) ~ U-J а-\

Эта величина для истинной случайной последовательности равна е - 1, а наше значение равно е - 1 + (е/2 - 1)/а + 0(1/а). [Зал<ечание. Тот же результат справедлив для возрастающих серий, так как неравенство Un > Un+i выполняется тогда и только тогда, когда 1 - Un < 1 - Un+i- Это приводит к предположению, что серии в линейной конгруэнтной последовательности могут быть немного длиннее, чем нужно, поэтому к таким генераторам следует применять критерий монотонности.]

25. X должен принадлежать интервалу [(fc + а - б)/а .. (fc + /3 - в)/а) для некоторых fc и также интервалу [а .. /3). Пусть fco = faa + б-/31, fci = fa/3 + б - /3]. С учетом граничных условий получим вероятность

(fci - fco)(/3 - а)/а + max(0, /3 - (fci + а - в)/а) - max(0, а - (fco + а - в)/а).

Рис. А-1. Области перестановок для генератора Фибоначчи.

Рис. А-2. Области длин серий для генератора Фибоначчи.

Это равно {/3 - а)ЦЗ - а) + е, где € < 2(/3 - а)/а.

26. См. рис. А-1. Неравенства Ui < Us < U2 я U2 < Us < Ux невозможны; каждое из остальных четырех имеет вероятность i.

27. и„ = {Fn-xUo + F„Ux}. Необходимо, чтобы выполнялись оба следующих неравенства: Fk-iUo + FkUi < 1 и FkUo + Fk+xUi > 1. Половина единичного квадрата, в которой Uo > Ui, отброшена, как показано на рис. А-2, с различными отмеченными значениями к. Вероятность для серии длиной к равна , если А: = 1, и равна l/Fk-x Fk+x - l/Fk Fk+2, если к > 1. Соответствующие вероятности для случайной последовательности равны 2к/{к + 1)! - 2{к + 1)/{к + 2)!. В приведенной ниже таблице сравниваются пять первых величин.

к: 12 3

Вероятности для последовательности Фибоначчи: i Вероятности для случайной последовательности:

5 12

± ± ±

10 24 65

И 19 29

60 360 2520

28. На рис. А-3 показаны различные области для общего случая. Область 213 означает, что U2 <Ux < Us, если Ui и U2 выбраны наудачу; область 321 означает, что Us < U2 < Ux, и т. д. Вероятности для 123 и 321 равны - а/2 + а/2; вероятности для всех остальных случаев равны +а/4 - а/4. Чтобы все вероятности были равны , должно выполняться равенство 1 - 6а + 6а = 0. [Утверждение этого упражнения установлено в теореме Дж. Н. Франклина (J. N. Franklin), (см. работу J. N. Franklin, Math. Сотр. 17 (1963), 28-59, теорема 13); другие результаты статьи Франклина имеют отношение к упр. 22 и 23.]

РАЗДЕЛ 3.3.4

1. Для генераторов с максимальным периодом 1-D точность vx всегда равна т к цх = 2.

2. Пусть V - матрица со столбцами, равными Vx,...,Vt. Минимизация У • У при условии, что У ф (О,..., 0) и VY - вектор-столбец X, состоящий из целых чисел, равносильна минимизации {V~X) {V~X) при условии, что X - это вектор-столбец, состоящий из целых чисел, не равных нулю. Столбцами являются Ux, ..., Ut-

3. = 2а - 1 и = За - 2 (по модулю т). Рассматривая все короткие решения (15), найдем, что 1/3 = 6 и 14 = 4 для соответствующих векторов (1,-2,1) и (1,-1,-1,1), за