показали, что, используя маску подобным образом, можно получить жесткое ядро во многих случаях. Наконец, Левин в работе J. Symbolic Logic 58 (1993), 1102-1103, усовершенствовал методы предыдущей работы, введя алгоритм L и проанализировав его.

Свой вклад в теорию внесли многие авторы - особенно Импаглиаззо (Impagli-azzo), Левин, Лаби (Luby) и Хастад (Hastad) [STOC 21 (1989), 12-24; 22 (1990), 395-404], которые показали, что псевдослучайные последовательности можно построить из любой однозначной функции. Однако такие результаты здесь не рассматриваются, так как они применяются, главным образом, в сложной абстрактной теории, а не в практическом генерировании случайных чисел. Практическое применение теоретических работ к псевдослучайности впервые эмпирически исследовано в работе Р. LEcuyer and R. Proulx, Proc. Winter Simulation Conf. 22 (1989), 467-476.

Если числа не случайны, то они по крайней мере в полном беспорядке.

- ДЖОРДЖ МАРСАЛЬЯ (GEORGE MARSAGLIA) (1984)

УПРАЖНЕНИЯ

1. [10] Может ли периодическая последовательность быть равнораспределенной?

2. [10] Рассмотрите периодическую двоичную последовательность 0,0,1,1,0,0,1,1, .... Она 1-, 2- или 3-распределенная?

3. [М22] Постройте троичную периодическую 3-распределенную последовательность.

4. [НМЦ] Докажите, что Pr(S(n) иТ(п)) -Н Pr(S(n) илиТ(п)) = Pr(S(n)) -Ь Рг(Т(п)) для любых двух утверждений S(n) и Т(п), предполагая, что по крайней мере три из этих пределов существуют. Например, если последовательность 2-распределена, то можно найти, что

Pr(ui <Un <Vl или U2 < Un+l < V2) = Vl - Ui + V2 - U2 - («1 - Ul)(i;2 - U2).

► 5. [HM22] Пусть U„ = (2L«("+iV3) mod 1. Чему равна Pr(f/„ < )?

6. [HM23] Пусть 5i(n), S2(n), ... - бесконечная последовательность утверждений о совместных непересекающихся событиях, т. е. Si(n) и Sj{n) не могут выполняться одновременно, если i ф j. Предположим, что Pr(Sj(n)) существует для каждого j > 1. Покажите, что Pr(SJ(n) выполняется для некоторого j > 1) > J2j>i Pr(Sj(n)), и приведите пример, показывающий, что равенство может не выполняться.

7. [НМ27] Пусть {5ij(n)} - семейство утверждений, таких, что Pi{Sij{n)) существует для всех i,J > 1. Предположим, что для всех п > О Sij{n) выполняется для точно одной пары целых чисел Если J2i,j>iiSij{"-)) = li то следует ли из этого, что "Pr(Sij(n) вьшолняется для некоторого J > 1)" существует для всех г > 1 и равна E,>iPr(5i,(n))?

8. [М15] Докажите (13).

9. [НМ20] Докажите лемму Е. [Указание. Рассмотрите ~<*)-]

► 10. [НМ22] Где в доказательстве теоремы С используется тот факт, что тп делит ql

11. [М10] Применяя теорему С, докажите, что если последовательность {Un) оо-распределена, то она является подпоследовательностью {U2n).

12. [НМ20] Покажите, что fc-распределенная последовательность удовлетворяет критерию "максимум-fc" в следующем смысле: Рг(и < max([/n, f/n+i, .., Un+k-i) <v) = v° - и.

► 13. [НМ27] Покажите, что оо-распределенная [О .. 1)-последовательность проходит критерий интервалов в следующем смысле: если О<а<0<1ир = 0-а, пусть /(0) = О и для п > 1 пусть /(п) - наименьшее целое число тп > f{n - 1), такое, что а < Um < 0, тогда

Pr(/(n)-/(n-l) = fe) =р(1-р)*-.

14. [НМ25] Покажите, что оо-распределенная последовательность проходит критерий монотонности в следующем смысле: если /(0) = О и если для п > 1 /(п) - наименьшее целое число тп > f(n - 1), такое, что Um-i > Um, тогда

Pr(/(n) - fin - 1) = fe) = 2fe/(fe + 1)! - 2(fe + l)/(fe + 2)!.

► 15. [НМЗО] Покажите, что оо-распределенная последовательность проходит критерий собирания купонов, в котором существует только два вида купонов, в следующем смысле: пусть Xi, Х2, . . - оо-распределенная двоичная последовательность. Пусть /(0) = О и для п > 1 пусть /(п) - наименьшее целое число тп > f{n - 1), такое, что {Xf(,n-i)+i, , Хщ} является множеством {0,1}. Докажите, что Рг(/(п) - /(п - I) = к) = 2~ для к > 2 (см. упр. 7).

16. [НМ38] Выполняется ли критерий собирания купонов для оо-распределенных последовательностей, когда существует больше двух видов купонов? (См. предыдущее упражнение.)

17. [НМЗО] Для любого заданного рационального числа г Франклин (Franklin) доказал, что последовательность (г" mod 1) не является 2-распределенной. Но существует ли рациональное число г, для которого эта последовательность равнораспределена? В частности, равнораспределена ли последовательность при г = ? [См. К. Mahler, MathematiJca 4 (1957), 122-124.]

► 18. [НМ22] Докажите, что если Uo, Ui, ... fe-распределена, то такой же будет последовательность Vo, Vl, ..., где Vn = [nC/nJ/n.

19. [НМ35] Рассмотрите модификацию определения R4, требуя, чтобы подпоследовательность была только 1-распределенной, а не оо-распределенной. Существует ли последовательность, удовлетворяющая этому более слабому определению, которая не будет оо-распределенной? (Действительно ли это определение более слабое?)

► 20. [НМ36] (Н. Г. де Брейн (N. G. de Bruijn) и П. Эрдеш (Р. Erdos).) Первые п точек любой [О.. 1)-последовательности (Un) с С/о = О делят интервал [0.. 1) на п подынтервалов. Пусть эти подынтервалы имеют длины > п > • • • > п". Очевидно, что /4 > > п",

поскольку 1п-\-----[-4" = 1. Одним из способов измерения равномерности распределения

(Un) является рассмотрение пределов

L ="limsupnгi и L = liminf п/".

П-+00

п-юо

a) Чем являются L и L для последовательности Ван дер Корпута (van der Corput) (29)?

b) Покажите, что llk-i - Дя 1 < А; < п. Используйте этот результат для доказательства того, что L > 1/1п2.

c) Докажите, что L < 1/1п4. [Указание. Для каждого п существуют такие числа oi, ..., 02п, что ijt n+tf для 1 < к < 2п. Кроме того, каждое целое число 2, ..., п появляется самое большее дважды в {oi,... ,а2п}.]

d) Покажите, что последовательность (Wn), определенная равенством Wn = lg(2n-l-l) modi, удовлетворяет 1/1п2 > nln > nl > 1/1п4 для всех п. Следовательно, она достигает оптимальных значений L и L.

21. [НМ40] (Л. г. Рамшоу (L. Н. Ramshaw).)

a) Продолжаем предыдущее упражнение. Будет ли последовательность (Wn) равно-распределена?

b) Покажите, что (Wn) является только [О.. 1)-последовательностью, для которой выполняется J2ji ls(l + i/) всякий раз, как только 1 < А; < п.

c) Пусть {fn{h,...,ln)} - любая последовательность непрерывных функций на множествах строк размерности п h > > U и h + + In = 1}, удовлетворяющая следующим двум свойствам:

Un{M,,...,Mu ... ,ln,...,ln) = fnih,...,ln);

если Е=1> Е*=1для 1 < fe < п, то fn{ll,...,ln)>fn{ll,...,ln). [Примеры: nli; -nli; /4Vi" + • + Пусть

F = limsup/„(/i\...,e)

n-юо

для последовательности (Wn)- Покажите, что fn{ln\---ji) < F для всех п относительно (Wn), а также limsup„ ,go fn(ln\ , 4") > F относительно каждой другой [О.. 1)-последовательности.

► 22. [НМЗО] (Герман Вейль (Hermann Weyl).) Покажите, что [О.. 1)-последовательность (Un) А;-распределена тогда и только тогда, когда

Jim е exp(27ri(ciC/„-(----(-CitI/n+it-i)) = 0

для каждого множества не всех равных нулю целых чисел ci, сг, ..., с*.

23. [М32] (а) Покажите, что [О.. 1)-последовательность (Un) А;-распределена тогда и

только тогда, когда все последовательности ((ciUn + caUn+i -I-----\-CkUn+k-i) mod l) 1-pac-

пределены всякий раз, когда ci, сг, ..., с* - целые числа, не все равные нулю. (Ь) Покажите, что Ь-ичная последовательность (Хп) А;-распределена тогда и только тогда, когда

все последовательности ((аХп + C2Xn+i Н-----1- CkXn+k-i) modb) 1-распределены всякий

раз , когда Ci, сг, ..., с* - целые числа с gcd(ci,..., с*) = 1.

► 24. [М35] (Й. Г. Ван дер Корпут (J. G. van der Corput).) (а) Докажите, что [0.. 1)-после-довательность (Un) равнораспределена всегда, когда последовательности ((Un+k -Un) mod l) равнораспределены для всех А; > 0. (Ь) Следовательно, ((cudn + + сщп + ао) mod 1) равнораспределена, когда d > О и ad - иррациональные числа.

25. [НМ20] Последовательность называется белой, если все сериальные коэффициенты корреляции равны нулю, т. е. если соотношение в следствии S выполняется для всех к > 1. (Согласно следствию S оо-распределенная последовательность является белой.) Покажите, что если [О.. 1)-последовательность равнораспределена, то она белая тогда и только тогда, когда

ц - - 1) = О для всех А > 1.

3 п.

0<j<n

26. [НМ34] (Дж. Франклин (J. Franklin).) Белая последовательность, определенная в предыдущем упражнении, может не быть случайной. Пусть Uo, Ui, ... - оо-распределенная последовательность. Определим последовательность Vo, Vi, ... следующим образом:

(V2n-uV2n) = (U2n-uU2n), если (U2n-uU2n) 6 G,

(F2n-l,V2„) = (U2n,U2n-l), если (U2n-l,U2n) G,