Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 53
Текст из файла (страница 53)
Если Р(А,5) будет очень близким к Р(А, Уи) для всех статистических критериев А, то мы ничего не смажем сказать о различии между последовательностями 5 и истинно случайными двоичными последовательностями. Определение Р. Мы говорпм, что ЛГ-источник 5 проходит статистический крнтерпй А с допустимым отклоненцем е, если 1Р(А,5) — Р(А,Юм)~ ( е. Критерий "проваливается", если ~Р(А, 5) — Р(А, Зм) ! > е. Нет необходимости в том, чтобы алгоритм А задавали статистики. Любой алгоритм можно рассматривать как статистический критерий случайности согласно определению Р. Мы позволяем А бросать монеты (т.
е. использовать истинно случайные двоичные разряды), а также выполнять вычисления. Единственное требование — А должен выдавать на выходе О или 1. Конечно, в действительности существуют другие требования: мы утверждаем, что алгоритм А должен давать результат на выходе за разумное время, по крайней мере в среднем. Нам не интересен алгоритм, который работает много лет, потому что мы никогда не заметим какого-нибудь несоответствия между 5 и йн, если наш компьютер не сможет обнаружить их в течение нашей жизни. Последовательности 5 содержат только 1к ф двоичных разрядов информации, так что, несомненно, существуют алгоритмы, которые в конечном счете обнаружат избыточность, Но ведь нас интересует, как долго 5 будет проходить все реально имеющие значение критерии.
Этн качественные идеи можно выразить, как мы сейчас увидим, в количественной форме. Такая теория весьма тонкая, но она достаточно красивая и важная, так что читатель, нашедший время внимательно изучить детали, будет вознагражден. В последующем обсуждении время вмяолиенил Т(А) алгоритмом А на Х двоичных строк определяется как максимальное ожидаемое число шагов, необходимых для выхода А(В), максимум берется по всем В е Фл, ожидаемое число является средним по распределению, соответствующему подбрасыванию монеты. Первый шаг количественного анализа — показать, что можно ограничиться критерием очень специального вида. Пусть Аь — алгоритм, зависящий только от первых й двоичных разрядов во входной строке В = В~... Вн, где О < й < Х, и пусть А~~(В) = (Аг(В) + Вг л + 1) шоб 2.
Тогда А~~ выводит 1 тогда и только тогда, когда Аг успешно предсказало Вь+~., назовем Аг критерием прогноза. Лемма Р1. Пусть 5 — Х-источник. Если 5 ие проходит критерий А с допустимым отклонением е, то существует целое число й О (О, 1,..., Л' — 1) и критерий прогноза А~~ с Т(А~~) < Т(А)+ О(М), такой, что 5 не проходит А~~' с допустимым отклонением Е~М. Доказательство. Дополнительно при необходимости можно предположить, что Р(А, 5) — Р(А, йн) > е. Рассмотрим алгоритмы Гы которые начинают подбрасывать Х вЂ” к монет, и заменим Вь~ы .. Вк случайными двоичными разрядами Вг ь,... Вь ° до выполнения А. Алгоритм Гл такой же, как и А, в то время как Го действует на 5, как А действует на Юк. Пусть рг = Р(ры 5). Поскольку 2 'г а (рьм — рг) = рк — ро = Р(Л, 5) — Р(А, Зн) > е, существуют к, такие, что рь г — рг > г/Х. Пусть А„— алгоритм, выполняющий вычисления Рь и предсказывающий зна- Р чение (Рь(В) + В„'.+, + 1) пкк1 2. Другими словами, он выводит Аг (В) = (Рг (В) + Вь г + Вь+~ ) шод 2.
(ЗО) Внимательный анализ веРоотностей показывает, что Р(Агн,5) — Р(А~~,Ь') рг+~ — рг (см. упр. 40). Большая часть Х-источников 5, имеющих практическое преимущество, являются источниками с симметричным сдвигом в том смысле, что каждая подстрока В1 ° ° ° Вы Вз... Вь~„..., Вм ьем ..
Вк длины й имеет одно и то же вероятностное распределение. Это выясняется, например, когда 5 ссютветствует линейной конгрузнтиой последовательности, квк в (38). В таких случаях лемму Р1 можно улучшить, взяв Й = Х вЂ” 1. Лемма Р2. Если 5 является Х-источником с симметричным сдвигом, который не проходит критерий А с допустимым отклонением с, то существует алгоритм А' с Т(А') < Т(А) + О(/д), который предсказывает В,ч из Во...
Ви ~ с вероятностью, равной по крайней мере ~~ + с/1т'. Доказагпельстао. Если Р(А,5) > Р(А,дм), пусть А' есть Аьг в доказательстве леммы Р1„только примененное к Ви ь... Ви ~0...О вместо Вм .. Вю Тогда А' в среднем ведет себя так же из-за симметричного сдвига. Если Р(А, 5) < Р(А, дм), пусть А' есть 1 — Аьг в том же виде.
Ясно, что Р(А', дм) = -'. $ Введем более жесткие ограничения на 5. Предположим, что каждая из последовательностей В~Во... Вк имеет вид /(д(Хо))/(д(д(Хо))) У(д(я)(Хо)), где Хо— зто упорядочение некоторого множества Х, д является перестановкой Х и У(х) равно 0 или 1 для всех х с Х. Наш линейный конгрузнтный пример удовлетворяет этим ограничениям с Х = (0,1,...,2' — 1), д(х) = (ах+ с) шод2" и /(х) = старший значащий двоичный разряд х. Такие /т'-источники назовем итеративными. Лемма РЗ. Если 5 — итеративный Ы-источник, который ие удовлетворяет критерию А с допустлмым отклонением с, то существует алгоритм А' с Т(А') < Т(А) + 0(Х), предсказывающий В~ юю Вз...
Вч по крайней мере с вероятностью ~1 + с/Х. Доказательство. Итеративный Л'-источник является источником с симметричным сдвигом. Значит, ои является своим отражением 5Я = (Вм... В~ ( В~... Ви б 5). Следовательно, лемма Р2 применима к 5л. 1 Перестановка д(х) = (ах+ с) шоб 2' легко обратима в том смысле, что х можно определить через д(х) всякий раз, когда а нечетное, Однако множества легко вычисляемых функций перестановок являются "односторонними" (трудно обратимыми), и мы увидим, что зто делает их вероятно хорошими источниками псевдослучайных чисел. Лемма Р4.
Пусть 5 — итеративный Ю-источник, соответствующий У, д и Х. Если 5 ие удовлетворяет критерию А с допустимым отклонением с, то существует алгоритм б', который правильяо оценивает /(х) по заданной д(х) с вероятностью > 1 + е/Х, когда х — случайный элемент из Х, Время вычисления Т(0) будет не более чем Т(А) + 0(Ю)(Т(/) + Т(д)). Доказашельстлво. Зададим д = д(х), Требуемый алгоритм 6 вычисляет Вз = У(д(х)), Вз = /(д(д(х))),, Вм = /(д('~ ')(х)) и применяет алгоритм А' леммы РЗ. Он приближенно оценивает /(х) = В, с вероятностью > ~+ с/11', так как д является перестановкой Х, и В~...
Вм — элемент 5, соответствующий начальному значению Хо, для которого выполняется д(Хо) = х. 1 Для того чтобы использовать лемму Р4, нужно усилить способность приближенно оценивать один двоичный разряд /(х) для того, чтобы уметь оценивать х только по значению д(х). Дли этого существует только тонкий общий способ— в Е(( 1)С(м..лв)+г1 1+- +гкчс) )~ (40) где усреднение берется по всем возможным значениям г1... гл. Это сумма правильных оценок минус неправильные оценки деленная на 2л; так, если р — вероятность того, что С правильно, то получим в = р — (1 — р) или р = ~1 + уж Например, предположим, что В = 4 и С(г) гггггв) = (г1 ~ ггИгв + г4 < 2). Функция дает хорошую оценку в = 4 (и р = 1), если х = 1100, так как она равна х г пюб 2 = (г) + гг) шоб 2 для всех строк г, содержащих 4 двоичных разряда, исключая 0111 илн 1ОУЬ Она также дает хорошую оценку -', когда х = 0000, 0011, 1101 или 1110, так что существует пять вероятных возможностей для х.
Остальные одиннадцать хв дают в < О. Следующий алгоритм магически находит х в большинстве случаев, когда С успешно оценивает в только что описанном смысле. Точнее, алгоритм строит короткий перечень элементов, имеюпщх хорошую возможность содержать х. Алгоритм Ь (Усиление линейных оценок). Пусть задана бинарнозначиэл функция С(г) ... гл) и положительное целое число Ь. Этот алгоритм дает таблицу 2" двоичных последовательностей х = х~... хл с таким свойством, что' х, вероятно, находится в этой таблице, когда С(г1... гл) является хорошим приближением функции (х1г1 + ° ° +хлгл) шо42.
Ь1. (Построение случайной матрицы.) Генерировать случайные двоичные разряды ВО для 1 < 1 < й и 1 < у < В. 1 2. (Подсчет знаков,) Для 1 < 1 < В и для всех двоичных разрядов строк Ь = Ь1... Ьь вычислить й (Ь) ~~ ( 1)ьс~.о)он+о) сФО (41) где с; — строка, содержащая В двоичных разрядов, 0... 010... 0 с 1 на позиции 1 и где с — строка о1 ... ол с и' = (В)зс) + .. + Ву,.
св) шоб 2. (Другими словамн, двоичный вектор с~ ... св является кратным двоичной матрице В размера Й х В.) Сумма взята по всем 2" — 1 строкам двоичных разрядов, с~... сь ~ О... О. Для каждого 1 можно оценить Ь;(Ь) Й 2 сложениями и вычитаниями с помощью метода Ятеса (Уасеэ) для преобразования Уолша (см.
замечание к равенству 4.6.4-(38)). ЬЗ. (Вьшод оценок,) Для всех 2ь выборов Ь = Ь)... Ьь вывод строки х(Ь) = [о1(Ь) < О] ' ... (Ьл(Ь) <0).'! использовать свойства булевых функций, если расширить 5 так, что появится потребность приближенно оценивать множество различных функций у(х). (Однако метод является несколько техническим. Так, при первом чтении следует, возможно, перейти к теореме О, прежде чем внимательно рассматривать следующие ниже детали.) Предположим, С(г1... гл) — бинарнозначная функция (принимающая значения 0 или 1) на строках из В двоичных разрядов, которая хорошо приближает функцию вида У(г~... гя) = (х~ г1 + - ° + хлгл) щи 2 для некоторого фиксированного х = х1...
хл. Удобно измерять, насколько это приближение успешно, вычисляя среднее значение Для доказательства того, что алгоритм Е хорошо работает, необходимо показать, что заданная строка х, вероятно, выводится всякий раз, когда она этого заслуживает. Сначала заметим, что, если заменить С на С', где С'(г) = (С(х) + гу) шоб 2, начальное С(х) будет хорошим приближением х ° г щи 2 тогда и только тогда, когда новое С'(х) будет хорошим приближением (х + еу) х пкк1 2, где еу— единичный вектор-строка, определенная на шаге Е2. Кроме того, если применить алгоритм С' вместо С, можно получить Ь1(Ь) — т, ( 1)ь с<-а(свес )+(си~-е ) ю — ( 1)Аэ Ь,((Ь+ В„) щод 2), сне где Ву —,у-й столбец В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
