где G - множество

{(х, г/) IX - i < г/ < X или X + i < г/}.

Покажите, что (а) последовательность Vq, Vi, ... равнораспределенная и белая, (Ь) Pr(Vn > Vn+i) = . (Это указывает на слабость критерия сериальной корреляции.)

27. [НМ48] Чему равно наибольшее возможное значение для Pr(V„ > Vn+i) в равно-распределенной белой последовательности? (Д. Копперсмит (D. Coppersmith) построил такую последовательность, для которой это значение достигает .)

► 28. [НМ21] Воспользуйтесь последовательностью (11), чтобы построить 3-распределен-ную [0.. 1)-последовательность, для которой Рг([/2п > j) = f •

29. [НМ34] Пусть Ао, Ai, ... - (2/г)-распределенная двоичная последовательность. Покажите, что

P?(A2„=0)<i+f;)/2-.

► 30. [М39] Постройте (2/г)-распределенную двоичную последовательность, для которой

Р..,. = о, = !.(--)/.».

(Таким образом, неравенство в предыдущем упражнении является наилучшим.)

31. [МЗО] Покажите, что существуют [О.. 1)-последовательности, удовлетворяющие определению R5, однако Un/n > для всех n > О, где Un - число j < п, для которых Un < (Это можно рассматривать как неслучайное свойство последовательности.)

32. [М24] Задана (Хп) "случайная" Ь-ичная последовательность, удовлетворяющая определению R5, nTZ - исчисляемое правило подпоследовательности, точно задающее бесконечную подпоследовательность {Xn)TZ. Покажите, что последняя подпоследовательность не только 1-распределена, но и "случайна" согласно определению R5.

33. [НМ22] Пусть {Ur„) и {U,„) - бесконечные непересекающиеся подпоследовательности последовательности (Un)- (Иначе говоря, го < ri < гг < • • и so < si < S2 < • • • - возрастающие последовательности целых чисел игт ф Sn для любых тп, п.) Предположим, что {Ut„) - комбинированная подпоследовательность, такая, что to < ti < <2 < • • •, и положим {<„} = {гп} и {»„}. Покажите, что если Рг([/г„ & А) = Рг(С4„ е А) = р, то Рг([/,„ еА)=р.

► 34. [М25] Определите правила подпоследовательностей TZi, TZi, TZa, , такие, что с этими правилами можно использовать алгоритм W, чтобы задать эффективный алгоритм построения [О .. 1)-последовательности, удовлетворяющей определению R1.

► 35. [НМ35] (Д. В. Лавленд (D. W. Loyeland).) Покажите, что если двоичная последовательность (Хп) R5-cлyчaйнa и если (sn) - любая исчисляемая последовательность соответственно с определением R4, то Pi(X,„ = 1) > и Pr(As„ = 1) < 5.

36. [НМЗО] Пусть (Хп) - двоичная последовательность, "случайная" согласно определению R6. Покажите, что [0.. 1)-последовательность (Un), определенная в двоичной системе счисления по схеме

t/o = (0.Ao)2, [/l = (O.AlA2)2, С/2 = (0.3X4X5)2, С/з = (О.ХвХ7Х8Х9)2, ... ,

случайна в смысле определения R6.

37. [М37] (Д. Копперсмит (D. Coppersmith).) Постройте последовательность, удовлетворяющую определению R4, но не определению R5. [ Указание. Рассмотрите преобразование Uo, Ui, С/4, U9, ... истинно случайной последовательности.]

38. [М49] (А. Н. Колмогоров.) Пусть заданы N, п и е. Чему равно наименьшее число алгоритмов в множестве А, таких, чтобы не существовали (п, е)-случайные двоичные последовательности длины Л по отношению к А? (Если нельзя задать точные формулы, можно ли найти асимптотические формулы? Суть этой проблемы - обнаружить, как точная грань (37) становится "наилучшей возможной".)

39. [НМ45] (В. М. Шмидт (W. М. Schmidt).) Пусть 1/„ - [О.. 1)-последовательность и пусть Un (и) - число таких неотрицательных целых чисел j < п, что Q<Uj < и. Докажите, что существует такая положительная постоянная с, что для любого Л и любой [О .. 1)-пос-ледовательности (Un) мы получим

\un(u) - ип\ > c\nN

для некоторых п и и при 0<n<JV, 0<и<1. (Другими словами, никакая [О.. 1)-после-довательность не может быть слишком равнораспределена.)

40. [М28] Завершите доказательство леммы Р1.

41. [М21] В лемме Р2 показано существование критерия прогноза, но при доказательстве предполагается существование подходящего к без объяснения, как конструктивно находить к из А. Покажите, что любой алгоритм А можно обратить в алгоритм А с Т(А) < Т(А) + 0(N), который предсказывает Bn по J5i ... Bn-i с вероятностью, по крайней мере равной i + (Р(А, S) - Р(А, $n))/N на любом симметричном сдвиге Л-источника 5.

► 42. [М28] (Попарная независимость.)

a) Пусть Ai, ..., Хп - случайные величины со средним, равным р = Е Xj, и дисперсией

= EXj - (EXj) при 1 < j < п. Докажите неравенство Чебышева

Pr((Ai + ...+Хп- npf > tn<T) < 1/t при дополнительных предположениях, что E(XiXj) = (EXi)(EXj) всякий раз, когда

b) Пусть В - случайная двоичная матрица размера к х R. Докажите, что если с и с - фиксированные не равные нулю двоичные векторьь размерности к, то сВ и сВ - независимые случайные двоичные векторы размерности R (по модулю 2).

c) Примените (а) и (Ь) к анализу алгоритма L.

43. [20] Кажется, точно так же тяжело найти множители любого фиксированного целого числа Блюма М, состоящего из R двоичных разрядов. Как найти множители случайного целого числа, состоящего из R двоичных разрядов? Почему тогда теорема Р сформулирована для случайного, а не фиксированного М?

► 44. [16] (И. Дж. Гуд (I. J. Good).) Может ли правильная таблица случайных чисел содержать точно одну ошибку?

3.6. выводы

в этой ГЛАВЕ было рассмотрено довольно много тем: генерирование случайных чисел, их проверка, их видоизменение при использовании и методы получения теоретических фактов. Возможно, главным для многих читателей был вопрос "Что получено в результате всей этой теории и что такое простой добротный генератор, который можно использовать в программах в качестве надежного источника случайных чисел?".

Подробные исследования в этой главе наводят на мысль, что следующая процедура позволяет получить простейший генератор случайных чисел для машинного языка большинства компьютеров. В начале программы присвойте целой переменной X некоторое значение Xq- Эта величина X используется только для генерирования случайного числа. Как только в программе потребуется новое случайное число, положите

X <- {аХ + с) mod т (1)

и используйте новое значение X в качестве случайной величины. Необходимо тщательно выбрать Хо, а, с и m и разумно использовать случайные числа согласно следующим принципам.

i) "Начальное" число Хо может быть выбрано произвольно. Если программа используется несколько раз и каждый раз требуются различные источники случайных чисел, то нужно присвоить Хо последнее полученное значение X на предыдущем прогоне и.пи, если это более удобно, присвоить Хо текущие дату и время. Чтобы снова запустить программу с такими же случайными числами (например, при отладке программы), нужно напечатать Хо, если иначе его невозможно получить, ii) Число m должно быть большим, скажем, по крайней мере 2°. Возможно, удобно взять его равным размеру компьютерного слова, так как это делает вычисление (аХ + с) modm вполне эффективным. В разделе 3.2.1.1 выбор тп обсуждается более детально. Вычисление (аХ-Ьс) mod т должно быть точным без округления ошибки, ill) Если m - степень 2 (т. е. если используется двоичный компьютер), выбираем а таким, чтобыд mods = 5. Если т - степень 10 (т. е. используется десятичный компьютер), выбираем а таким, чтобы а mod 200 = 21. Одновременный выбор а и с даст гарантию, что генератор случайных чисел будет вырабатывать все тп различных возможных значений X прежде, чем они начнут повторяться (см. раздел 3.2.1.2), и гарантирует высокий "потенциал" (см. раздел 3.2.1.3).

iv) Множитель а предпочтительно выбирать между .01т и .99т, и его двоичные или десятичные цифры не должны иметь простую регулярную структуру. Выбирая несколько случайных констант, подобных а - 3141592621 (которые удовлетворяют обоим условиям в (iii)), почти всегда получаем достаточно хороший множитель. Дополнительная проверка, конечно, нужна, если генератор случайных чисел используется регулярно. Например, частичные отношения не должны быть большими, когда для нахождения gcd а и m используется алгоритм Евклида (см. раздел 3.3.3). Множитель должен пройти спектральный критерий (раздел 3.3.4) и несколько критериев, описанных в разделе 3.3.2, прежде чем он получит сертификат качества.