Нет необходимости в том, чтобы алгоритм А задавали статистики. Любой алгоритм можно рассматривать как статистический критерий случайности согласно определению Р. Мы позволяем А бросать монеты (т. е. использовать истинно случайные двоичные разряды), а также выполнять вычисления. Единственное требование - А должен выдавать на выходе О или 1.

Конечно, в действительности существуют другие требования: мы утверждаем, что алгоритм А должен давать результат на выходе за разумное время, по крайней мере в среднем. Нам не интересен алгоритм, который работает много лет, потому что мы никогда не заметим какого-нибудь несоответствия между 5 и §7v, если наш компьютер не сможет обнаружить их в течение нашей жизни. Последовательности S содержат только lg5 двоичных разрядов информации, так что, несомненно, существуют алгоритмы, которые в конечном счете обнаружат избыточность. Но ведь нас интересует, как долго S будет проходить все реально имеющие значение критерии.

Эти качественные идеи можно выразить, как мы сейчас увидим, в количественной форме. Такая теория весьма тонкая, но она достаточно красивая и важная, так что читатель, нашедший время внимательно изучить детали, будет вознагражден.

В последующем обсуждении время выполнения Т{А) алгоритмом Л на Л двоичных строк определяется как максимальное ожидаемое число шагов, необходимых для выхода А{В), максимум берется по всем В € $n, ожидаемое число является средним по распределению, соответствующему подбрасьшанию монеты.

Первый шаг количественного анализа - показать, что можно ограничиться критерием очень специального вида. Пусть Ак - алгоритм, зависящий только от первых к двоичных разрядов во входной строке В = Bi... Bf, где О < к < N, и пусть АР{В) = [Ак{В) + Вк+1 +1) mod 2. Тогда А выводит 1 тогда и только тогда, когда Ак успешно предсказало Bk+i; назовем А критерием прогноза.

Лемма Р1, Пусть S - N-источник. Если S не проходит критерий А с допустимым отклонением е, то существует целое число A;e{0,l,...,iV - l}if критерий прогноза А сТ{АР) < T{A)-{-0{N), такой, что S не проходит А с допустимым отклонением e/N.

Доказательство. Дополнительно при необходимости можно предположить, что Р{А, S)-P{A, $n) > е. Рассмотрим алгоритмы Ек, которые начинают подбрасывать N -к монет, и заменим Bk+i... Вм случайными двоичными разрядами ... Bj до выполнения А. Алгоритм Ejv такой же, как и Л, в то время как Eq действует на S, как А действует на $n. Пусть рк = P{Fk,S). Поскольку Y!,Jo (Pk+i - Рк) = pn - Ро = Р{Л, S) - Р{А, $n) > е, существуют к, такие, что pk+i - Рк > /N.

Пусть А - алгоритм, выполняющий вычисления Ек и предсказывающий значение {Е{В) -Ь Bf. .y -Ь 1) mod 2. Другими словами, он выводит

А{В) = {Ек{В) + + Вк+г) mod 2. (39)

Внимательный анализ вероятностей показывает, что P(>lf, 5) - P{Af,$i) = Pk+i - Рк (см. упр. 40). I

Большая часть iV-источников S, имеющих практическое преимущество, являются источниками с симметричным сдвигом в том смысле, что каждая подстрока

Bi... Bk, B2...Bk+1, Вм-к+1 Bi длины к имеет одно и то же вероятностное" распределение. Это выполняется, например, когда S соответствует линейной конгруэнтной последовательности, как в (38). В таких случаях лемму Р1 можно улучшить, взяв к = N - \.

Лемма Р2. Если S является N-источником с симметричным сдвигом, который не проходит критерий А с допустимым отклонением с, то существует алгоритм А с Г(Л) < Т{А) + 0{N), который предсказывает В из Вх... Bn-x с вероятностью, равной по крайней мере + e/N.

Доказательство. Если P{A,S) > P{A,$n), пусть А есть А в доказательстве леммы Р1, только примененное к Bf-k. . В-хО- О вместо Вх... В- Тогда А в среднем ведет себя так же из-за симметричного сдвига. Если P{A,S) < P{A,$f), пусть А есть 1 - в том же виде. Ясно, что Р{А, $м) = I

Введем более жесткие ограничения на S. Предположим, что каждая из последовательностей ВхВ2 ...Bn имеет вид f {giXo)) f {д{д{Хо))).. .f{g\Xo)), где Xq - это упорядочение некоторого множества X, д является перестановкой X и /(х) равно О или 1 для всех х е X. Наш линейный конгруэнтный пример удовлетворяет этим ограничениям с X = {0,1,..., 2 - 1}, д{х) = (ах + с) mod 2 и f{x) = старший значащий двоичный разряд х. Такие iV-источники назовем итеративными.

Лемма РЗ. Если S - итеративный N-источник, который не удовлетворяет критерию А с допустимым отклонением е, то существует алгоритм А с Т{А) < Т{А) -Ь 0{N), предсказывающий Вх по • • • по крайней мере с вероятностью -f e/N.

Доказательство. Итеративный iV-источник является источником с симметричным сдвигом. Значит, он является своим отражением 5 = {Bjv... Вх \ Вх... Bjv € S}. Следовательно, лемма Р2 применима к 5.

Перестановка д{х) = {ах -Ь с) mod 2 легко обратима в том смысле, что х можно определить через д{х) всякий раз, когда а нечетное. Однако множества легко вычисляемых функций перестановок являются "односторонними" (трудно обратимыми), и мы увидим, что это делает их вероятно хорошими источниками псевдослучайных чисел.

Лемма Р4. Пусть S - итеративный N-источник, соответствующий /,диХ. Если S не удовлетворяет критерию А с допустимым отклонением е, то существует алгоритм G, который правильно оценивает f{x) по заданной д{х) с вероятностью > + e/N, когда х - случайный элемент из X. Время вычисления T(G) будет не более чем Т(А) -I- 0(7V)(r(/) -I- Т{д)).

Доказательство. Зададим у = д{х). Требуемый алгоритм G вычисляет В2 = f{g{x)), Вз = /{д{д{х))), Вдг = f{g~4x)) и применяет алгоритм А леммы РЗ. Он приближенно оценивает f{x) = Вх с вероятностью > + /N, так как д является перестановкой X, и Вх... Вдг - элемент S, соответствующий начальному значению Хо, для которого выполняется д{Хо) = х.

Для того чтобы использовать лемму Р4, нужно усилить способность приближенно оценивать один двоичный рг1зряд f{x) для того, чтобы уметь оценивать х только по значению д{х). Для этого существует только тонкий общий способ -

использовать свойства булевых функций, если расширить S так, что появится потребность приближенно оценивать множество различных функций f{x). (Однако метод является несколько техническим. Так, при первом чтении следует, возможно, перейти к теореме G, прежде чем внимательно рассматривать следующие ниже детали.)

Предположим, G{zi...zr) - бинарнозначная функция (принимающая значения О или 1) на строках из R двоичных разрядов, которая хорошо приближает функцию вида f{zi... zr) = (xiZi -- • • • -Ь хдгд) mod 2 для некоторого фиксированного х = xi... хд. Удобно измерять, насколько это приближение успешно, вычисляя среднее значение

S = Е((-1)<(-«)++-+««), (40)

где усреднение берется по всем возможным значениям zi...zr. Это сумма правильных оценок минус неправильные оценки деленная на 2; так, если р - вероятность того, что G правильно, то получим s = р - (1 - р) или р = -Ь s.

Например, предположим, что Л = 4 и 6(21222324) = [21 ф Z2][z3 -Ь 24 < 2]. Функция дает хорошую оценку s = (и р = ), если х = 1100, так как она равна X • 2 mod 2 = (21 -Ь 22) mod 2 для всех строк 2, содержащих 4 двоичных разряда, исключая 0111 или 1011. Она также дает хорошую оценку i, когда х = 0000, ООП, 1101 или 1110, так что существует пять вероятных возможностей для х. Остальные одиннадцать Хк дают s < 0.

Следующий алгоритм магически находит х в большинстве случаев, когда G успешно оценивает в только что описанном смысле. Точнее, алгоритм строит короткий перечень элементов, имеющих хорошую возможность содержать х.

Алгоритм L {Усиление линейных оценок). Пусть задана бинарнозначная функция G(2i .. .zjt) и положительное целое число к. Этот алгоритм дает таблицу 2* двоичных последовательностей х = xi... хд с таким свойством, что х, вероятно, находится в этой таблице, когда G(2i... zr) является хорошим приближением функции (xi2i -ь----1-хл2л) mod 2.

L1. [Построение случайной матрицы.] Генерировать случайные двоичные разряды Bij для 1 < г < fc и 1 < j < Л.

L2. [Подсчет знаков.] Для 1 < г < Л и для всех двоичных разрядов строк b = bi...bk вычислить

hi{b) = ( l)6c+G(cB+e,) (41)

где et - строка, содержащая R двоичных разрядов, О... 010... О с 1 на позиции г

и где сВ - строкаdi.. .Urc dj = (BijCiН-----VBkjCk) mod2. (Другими словами,

двоичный вектор ci ... является кратным двоичной матрице В размера fcx Л.) Сумма взята по всем 2*-1 строкам двоичных разрядов, ci... Cfc 7 О... 0. Для каждого i можно оценить hi{b) к 2* сложениями и вычитаниями с помощью метода Ятеса (Yates) для преобразования Уолша (см. замечание к равенству 4.6.4-(38)).

L3. [Вывод оценок.] Для всех 2* выборов 6 = 61... 6 вывод строки х{Ь) = [hi{b) < 0] ...[hR{b)<Q]. I