AOP_Tom2 (1021737), страница 54
Текст из файла (страница 54)
Только допустим, что зто количество может быть достигнуто для по крайней мере не слишком малых частей целых чисел Блюма ЛХ, состоящих из Л двоичных разрядов. Тогда можно будет умножить много чисел, состоящих из приблизительно 50 000 двоичных разрядов (15 000 цифр), за 2 х 10зз М1Р-лет. Если генерировать Х = 1000 случайных двоичных разрядов смешанно-квадратичным методом с Н = 50000 и если предположить, что все алгоритмы достаточно хороши, то умножение по крайней мере 4 ' ор на состоящие из 50 000 двоичных разрядов числа Блюма должно выполняться минимум 2 х 10зз М1Р-лет. Из теоремы Р следует, что каждое такое множество из 1 000 двоичных разрядов проходит все статистические критерии на случайность, время счета Т(А) которых меньше 70 000 М1Р-лет: не существует алгоритма А, который мог бы отличить такие двоичные разряды от истинно случайной последовательности с вероятностью > е = +о.
Впечатляет? Нет. Такой результат вряд ли является сюрпризом, так как необходимо точно определить около 150 000 истинно случайных двоичных разрядов, точно начинающихся в смещанно-квадратичном методе с Хо, г, и М, когда Н = 50000. Конечно, можно получить 1 000 случайных двоичных разрядов из такого вклада! Но вообще, формула Т(А) > П,-зН-з ехр(В~I~(1п11)з/4) УДз 1 100000 справедлива при наших умеренных предположениях, когда е = ,ов, ХВ членов 1 3 нвляются незначительными и когда В велико. Положим, В = 200000 и Х = 10'в. Тогда смешанно-квадратичным методом получим десять миллиардов псевдослучайных двоичных разрядов из 311 - 600000 истинно случайных двоичных разрядов, проходящих все статистические критерии, которые требуют меньше 7.486 х 10'в М1Р-лет, что равно 74.86 гигаМ1Р-годам. При Х = 10'з и Л = 333333 время вычисления, необходимое для определения статистического смещения, возрастает до 53.5 тераМ1Р-лет, Простой псевдослучайный генератор 3.2.2-(16), который избегает случайной маски У, что также можно показать, проходит все полиномиальные критерии случайности, если разложение на множители трудно осуществить (см.
упр. 4.5.4-43). Но известные преобразования гарантируют для методов, которые отчасти слабее смешанно-квадратичного метода, порядок роста 0(К~Не ~ 1о8(ХЛе ')) по сравнению с 0(Х~!с~с ~) теоремы Р. Каждый думает, что не существует алгоритма разложения на множители для чисел, состоящих из Н двоичных разрядов, время счета которых равно полиному в степени Н. Если это предположение верно в строгом виде, то нельзя будет получить даже 1/Н~ для целого числа Блюма, состоящего из Н двоичных разрядов, за полиномиальное время для любого фиксированного (с. Теорема Р доказывает, что смешанно-квадратичный метод генерирует псевдослучайные числа, проходящие все полиномпвльные критерии случайности. Сформулируем это другим способом: если генерировать случайные двоичные разряды смешанно-квадратичным методом для подходящим образом выбранных Ж и 77, можно также получить числа, проходящие все разумные статистические критерии, или открыть новый алгоритм разложения на множители.
С. Выводы, история и библиографии. Выше были определены различные степени случайности, которыми может обладать последовательность. Конечная оо-распределенная последовательность удовлетворяет великому множеству полезных свойств, которыми могут обладать случайные последовательности, и существует огромная теория, посвященная оо-распределенным последовательностям. (В упражнениях, которые приводятся ниже, развиваются некоторые важные, не упомянутые в разделе, свойства таких последовательностей.) Определение Н1 поэтому является подходящей основой для теоретического изучения случайности.
' Понятие "оа-распределение Ь-ичной последовательности" было введено в 1909 году Эмилем Борелем (Епп!е Воге1). Он, по существу, ввел понятие (т., сс)-распределенной последовательности и показал, что Ь-ичное представление почти всех действительных чисел является (т,й)-распределенным для всех т и )с. Борель назвал такие чиста нормальными по отношению к основанию Ь.
Превосходное обсуждение этой темы появилось в ега хорошо известной книге Бемоля эпг !а ТЬеопе с!еэ Гопсбопэ, 2пс1 ес!!С!оп (1914), 182 — 216. Понятие оо-распределенной последовательности действительных чисел, также носящее название полностью равнораснределенной последовательности, впервые появилось в заметке Н.
М. Коробова (Доклады Акад. Наук СССР 62 (1948), 21-22). Коробов и несколько его коллег достаточно широко развили теорию таких последовательностей в ряде статей в течение 50-х годов. Полностью равно- распределенные последовательности независимо изучались Джоэлем Н. Франклиным (Лое! К. вагапа!!и, ЛХаС!ь Сотар. 17 (1963), 28-59) в статье, которая особенно заслуживает внимания, так как она была вдохновлена проблемой генерирования случайных чисел.
Книга Б. Кшрегэ апс1 Н. Н!ес(егге!сег, Нп!(огт Р!эсг!Ьис!оп ог" Яессиепсез (Хеи Уог!с: ЪИеу, 1974) является чрезвычайно полным источником информации об огромной математической литературе, содержащей Ь-распределенные последовательности всех видов. Тем не менее мы увидели, что со-распределенные последовательности не обладают достаточным количеством свойств, чтобы их можно было считать совершенно "случайными". Определения В4 — Кб, приведенные выше, предусматривают дополнительные условия; в частности, определение Б6, видимо., было подходящим способом определения понятия бесконечной случайной последовательности.
Это точное количественное утверждение, хорошо совпадающее с интуитивным понятием истинной случайности. Исторически развитие этих определений было стимулировано, главным образом, поисками Р, фон Мизесом (В., топ МВеэ) хорошего определения вероятности. В Маг!ь Ее!гэсЬпгг 5 (1919), 52-99, фон Мизес предложил определение, по духу сходное с определением К5, хотя формулировка была слишком строга (подобно нашему определению КЗ), так что последовательностей, удовлетворяющих этим условиям„не существует. Многие исследователи отмечали это противоречие, и А. Г. Коуплэнд (А. Н. Соре!апг(, Ашег. Х МагЬ. 50 (1928), 535-552) предлагал ослабить определение фон Мизеса заменой„которую он назвал допустимыми числами (или последовательностями Бернулли).
Существует эквивалент оо-распределенных [О .. 1)-последовательностей, в которых все входные У„заменяются 1, если 5'„( р или 0 и если У„> р для заданной вероятности р. Так, Коуплэнд, по существу, предложил вернуться к определению К1. Затем Абрахам Вальд (АЬгаЬаш Жа!д) показал, что нет необходимости так решительно ослаблять определение фон Мизеса, и предложил заменить счетное множество правилами подпоследовательностей.
В важной статье БгйеЬп!ээе ешеэ шаГЬ. Но!!ойшигпэ 8 (Ъ'!еппа, 1937), 38 — 72, Вальд. по существу, доказал теорему 11', хотя он сделал ошибочный вывод, что последовательность, построенная алгоритмом %, также удовлетворяет сильным условиям— РгЩ Е А) = мера А для всех измеримых по Лебегу А С [О ..1). Заметим, что не существует последовательности, которая может удовлетворять этому условию. Понятие "вычисляемость" играло большую роль на ранней стадии, когда Вальд написал статью и А. Черч (А. СЬигсЬ, Вп!!. Ашег.
МагЬ. Яос, 46 (1940), 130 — 135) показал, как точное понятие "эффективный алгоритм" можно присоединить к теории Вальда, делая его определение совершенно строгим. Практически тогда же дополнение к определению Бб было предложено А. Н. Колмогоровым [Яа~й!~уа А25 (1963), 369-376], как и определение !42 для конечных последовательностей.
Другое определение случайности для конечных последовательностей, находящееся где-то между определениями 111 и О2, намного раньше сформулировал А. С. Безикович (А. Я. Веэ!сог!!сЬ, МагЛ, ЕейэсЬг!!! 39 (1934), 146 — 156). В публикациях Черча и Колмогорова рассматривались только двоичные последовательности, для которых Рг(Х„= 1) = р с заданной вероятностью р.
В этом разделе анализировалась более общая ситуация, поскольку [0..1)-последовательностгч по существу, представляет все р сразу. Определение фои Мизеса-Вальда-Черча еще одним интересным способом усовершенствовал Дж. В. Говард (3. У. Новап(, '2ечэсйг. гйг тагЬ. 7 оез(г ипИ Стинг(!аяеп г!ег Ма!!ь 21 (1975), 215 — 224) . Следующий важный вклад был сделан Дональдом В. Лавлендом (Ропа1~! 1г'.
1лче!апб, Хе!гэсЬг. Гбг тагЬ. Бо8й ипг! Сгиш!!айеп Иег Маг!ь 12 (1966), 279.294), который обсудил определения Б4-К6 и несколько других понятий. Лавленд доказал, что существуют К5-случайные последовательности, не удовлетворяющие определению К4. В связи с этим он установил, что необходимо более строгое определение, такое как Кб. На самом деле Лавленд определил простую перестановку (!(и)) неотрицательных целых чисел н алгоритм %', сходный с алгоритмом Ж, такой, что Р~(17>( ) '~ г) Р (1!У! ! — г) - 5 для каждой К5-случайной последовательности ((>'„), выдаваемой алгоритмом Ж', когда он задан бесконечным множеством правил подпоследовательнастей Еь Хотя определение К6 интуитивно строже определения В4, очевидно, строго доказать это совсем не просто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
