AOP_Tom2 (1021737), страница 52
Текст из файла (страница 52)
К. и Левин Л. А. Успехи мат. наук 25,6 (Ноябрь, 1970), 85-127; Левин Л. А. Доил. Акад. наук СССР 212 (1973), 548-550; Левин Л. А. Информация и контроль 61 (1984), 15-37. Р. Псевдослучайные числа. С теоретической точки зрения утешительно знать, что существуют случайные конечные последовательности с разными особенностями, но такие теоремы не дают ответов на вопросы, с которыми сталкиваются в действительности программисты. Недавние исследования привели к более практичной теории, основанной на изучении множеств конечных последовательностей. Точнее, рассмотрим мультпимножесгпва, в которых последовательности могут появляться более одного раза.
Пусть 5 — мультимножество, содержащее двоичные строки длины Х; назовем 5 г1-исгпочником. Пусть 8су означает определенный Х-источник, содержащий все 2~ возможных 1г'-двоичных строк. Каждый злемент 5 представляет последовательность, которую можно использовать в качестве источника псевдослучайных двоичных разрядов, выбор различных "начальных" значений приводит к различным злементам 5. Например, возможно такое множество 5 (В~Вз...
Вм ~ В, старший значащий двоичный разряд Х,) (38) в линейной конгруэнтной последовательности, определенной равенством Хг, (аХ1 + с) шоб 2', в котором существует одна строка В~Вз... Вьч для каждого из 2' начальных значений Хо. Основной идеей псевдослучайных последовательностей, как будет показано в этой главе, является получение 1г' двоичных разрядов, появляющихся случайно, несмотря на то что мы используем лишь несколько "истинно случайных" двоичных разрядов, когда выбираем начальное значение, В только что рассмотренном примере понадобилось е истинно случайных двоичных разрядов для выбора Хв. Вообще, для использования отбирается 1815~ из 5 истинно случайных двоичных разрядов, после чего процедура становится детерминированной, Если 1г' = 10в и ~5~ = 2з~, получаем более 30 ООО "кажущихся случайными" двоичных разрядов из выбранного истинно случайного двоичного разряда.
Прн 8ч вместо 5 мы не получим такого большого числа "случайных разрядов", поскольку 18 ~8л ~ = Х. Что означает "кажусцихся случайныьш"? Э. Ч. Яо (А. С. т'ао) в 1982 году предложил хорошее определение; рассмотрим любой алгоритм .4, который при применении к строке двоичных разрядов В = Вы .. Вм выдает значение А(В) = 0 или 1, Можно рассматривать А как критерий случайности, например алгоритм А может вычислить распределение серий последовательных нулей н единиц, выдавая на выходе единицу, если длины серий значительно отличаются для ожидаемого распределения.
Что бы ни делал А, вероятность Р(А,5) можно рассматрявать как вероятность того, что .4(В) = 1, когда  — случайно выбранный элемент из 5, и можно сравнивать с вероятностью Р(А,8л) того, что А(В) = 1, когда  — истинно случайная строка двоичных разрядов длины Х, Если Р(А,5) будет очень близким к Р(А,8м) для всех статистических критериев А, то мы ничего не сможем сказать о различии между последовательностями 5 и истинно случайными двоичными последовательностями. Определение Р.
Мы говорим, что Х-источник 5 проходит статистический критерий А с допустимым отклонением е, если )Р(А,5) — Р(.4,8к)~ < е. Критерий "проваливается", если ~ Р(А, 5) — Р(А, 8м) ~ > е. Нет необходимости в том, чтобы алгоритм .4 задавали статистики. Любой алгоритм можно рассматривать как статистический критерий случайности согласно определению Р. Уйы позволяем А бросать монеты (т. е. использовать истинно случайные двоичные разряды), а также выполнять вычисления.
Единственное требование — А должен выдавать на выходе 0 или 1. Конечно, в действитечьности существуют другие требования: мы утверждаем, что алгоритм А должен давать результат на выходе за разумное время, по крайней мере в среднем. Нам не интересен алгоритм, который работает много лет, потому что мы никогда не заметим какого-нибудь несоответствия между Я и Зн, если наш компьютер не сможет обнаружить их в течение нашей жизни. Последовательности Я содержат только 1к(Я~ двоичных разрядов информации, так что, несомненно, существуют алгоритмы, которые в конечном счете обнаружат избытачносю. Но ведь нас интересует, как долго 5 будет проходить все реально имеющие значение критерии, Эти качественные идеи можно выразить, как мы сейчас увидим, в количественной форме.
Такая теория весьма тонкая, но она достаточно красивая и важная, так что читатель, нашедший время внимательно изучить детали, будет вознагражден. В последующем обсуждении врегьв выполнения Т(А) алгоритмом А на Л' двоичных строк определяется как максимальное ожидаемое число шагов, необходимых для выхода А(В), максимум берется по всем В б Зьь ожидаемое число является средним по распределению, соответствующему подбрасыванию монеты.
Первый шаг количественного анализа — показать, что можно ограничиться критерием очень специального вида. Пусть Аь — алгоритм, зависящий только от первых К двоичных разрядов во входной строке В = В,... Вн, где 0 ( к ( Х и пусть Аь~(В) = (Аь(В) + Вь~~ + 1) шод 2. Тогда А~я выводит 1 тогда и только тогда, когда Аь успепша предсказало Вьч Н назовем А' критерием прогноза. Лемма Р1. Пусть 5 — Х-источник. Еат 5 не проходят критерий А с допустимым отклонением е, то существует целое чпсло к б (О, 1,..., Х вЂ” 1) и критерий прогноза А~~ с Т(А~ ) ( Т(А)+ 0(М), такой, что 5 не проходит А~' с допустимым отклонением е/Х.
Доказвтпельстео. Дополнительно при необходимости можно предположить, что Р(А, Я) — Р(А, Зсе) > е. Рассмотрим алгоритмы Ры которые начинают подбрасывать Х вЂ” к монет, и заменим Вь ы .. Вн случайными двоичными разрядами Вь~ы .. Вк до выполнения А. Алгоритм Рн такой же, как и А, в то время как Ро действует на Я, как А действует на Зн. Пусть рь = Р(Гю5). Поскольку 2 ь в (рьм — рь) = рн — ро = Р(А, Я) — Р(А, Зн) > е, существуют /с, такие, что рьч.1 — рь > е/Х Пусть А~ — алгоритм, выполняющий вычисления Рь и предсказывающий значение (Рь(В) + В,',, + 1) шоб 2. Другими словами, он выводит А~(В) = (Рь(В) + В,, + В~ьч,) шоб 2.
(39) Внимательный анализ вероятностей показывает, что Р(А~~,Я) — Р(А~~,Зн) рь+1 — рь (см. упр. 40). ! Большая часть Х-источников 5, имеющих практическое преимущество, являются источниками с сим.мешричнмм сдвпгом в том смысле, что каждая подстрока В~ Вь Вэ... Вььм ..., Вм-ььы,. Вя длины )с имеет одно и то же вероятностное' распределение. Это выполняется, например, когда Е соответствует линейной конгруэнтной последовательности, как в (38). В таких случаях лемму Р1 можно улучшить, взяв й = Х вЂ” 1. Лемма Р2. Егли 5 является г1-источником с симметричным сдвигом, который не проходит критерий А с допустимым отклонением «, то существует алгоритм А' с Т(А') < Т(А) + 0(М), который предсказывает Вк яз Вы ..
Вм > с вероятностью, равной по крайней мере —. + «/Х. Докаэательсшео. Если Р(А,5) > Р(А,дм), пусть А' есть А~' в доказательстве леммы Р1, только примененное к Вм ы.. Вк «О...О вместо Вы Вм. Тогда А' в среднем ведет себя так же из-за симметричного сдвига. Если Р(А, В) < Р(А, дм), пугть А' есть 1 — А~' в том же виде.
Ясно, что Р(А', д;ч) = 1 1 Введем более жесткие ограничения на 5. Предположим, что каждая из последовательностей В«Вз... Вм имеет вид /(д(Хе))/(д(д(Ле)))... /(дР«)(Хе)), где Хэ— это упорядочение некоторого множества Л", д является перестановкой Л и /(х) равно О или 1 для всех х б Х. Наш линейный конгрузнтный пример удовлетворяет этим ограничениям с Х = (0,1,...,2' — 1), д(х) = (ах+ с) шаб2' и /(х) = старший значащий двоичный разряд х.
Такие Х-источники назовем ишерашивимми. Лемма РЗ. Егля  — итеративный Х-источник, который не удовлетворяет критерию А с допустимым отклонением «, то существует алгоритм А' с Т(А') < Т(А) + 0(г«), предсказывающий В~ по Вэ... Вм по крайней мере с вероятностью 1 + «/д'. Докаэашельстлво. Итеративный Х-источник является источником с симметричным сдвигом. Значит, он является своим отражением а~ = (Вя... В~ ( В~... Вя б В).
Следовательно, лемма Р2 применима к он. 1 Перестановка д(х) = (ах+ с) ша«) 2' легко обратима в том смысле, что х можно определить через д(х) всякий раз, когда а нечетное. Однако множества легко вычисляемых функций перестановок являются "односторонними" (трудно обратимыми), и мы увидим, что это делает их вероятно хорошими источниками псевдослучайных чисел. Лемма Р4. Пусть 5 — итеративный Х-источник, соответствующий /, д и Х. Если В не удовлетворяет критерию А с допустимым отклонением «, то существует алгоритм с ', который правильно оценивает /(х) по заданной д(х) с вероятностью > э~ + «/Х, когда х — случайный элемент из Х. Время вычисления Т(б) будет не более чем Т(А) + 0(Х) (Т(/) + Т(д)).
Докаэашельсшео. Зададим д = д(х). Требуемый алгоритм 0 вычисляет Вэ = /(д(х)), Вэ = /(д(д(х))),, Вч = /(д~~ ')(х)) и применяет алгоритм А' леммы РЗ. Он приближенно оценивает /(х) = В~ с вероятностью > -' + «/Л', так как д является перестановкой Л; и Вм .. Вя — элемент В, соответствующий начальному значению Хе, для которога выполняется д(Хэ) = х. 3 Для того чтобы использовать лемму Р4, нужно усилить способность приближенно оценивать адин двоичный разряд /(х) для того, чтобы уметь оценивать х только по значению д(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
