Лекционные материалы (стр. 4 )

где . (1.12)

При этом – случайная величина, равномерно распределенная отрезке [0, 1].

Введем

Будем использовать в качестве оценки числа p

(1.13)

Данная оценка также является несмещенной.

Случайность и имитация случайности

Всякий, кто питает слабость
к арифметическим методам
получения случайных чисел,
грешен вне всяких сомнений.

Джон фон Нейман

В данном разделе мы кратко коснемся инструментального аппарата методов Монте-Карло – случайных чисел и способов их получения.

Случайность и непредсказуемость

Случайность – интереснейшая тема, рассмотрением которой издревле занималась не только математика, но и философия, теология… Судя по всему, одни из первых замеченных людьми проявлений случайности – это гадание и игра. Гадание – определение судьбы человека по неким магическим надписям и событиям, и карточные игры со всеми своими атрибутами, несомненно, являют собой яркие примеры того, как случайность в отличие от свободного выбора влияет на жизнь человека. Разница между свободным выбором и определенностью всегда являлась предметом ожесточенных споров в философии и теологии.

Хотя азартные игры и гадание были приняты у многих культур и во многих странах, на них почти всюду долго существовало некоторое гласное или негласное табу. В лучшем случае, это считалось чем-то неприличным. Скорее всего, основой такого отношения явились церковные запреты. Тем не менее, еще Галилей и Кардано писали про азартные игры и проявление случайности, а Паскаль, Ферма и Гюйгенс направили исследования в направлении сегодняшней теории вероятности.

В первую очередь математики фокусировали внимание на статистической случайности и изучали частоты появления отдельных элементов и блоков элементов при экспериментах в качестве меры случайности. Впоследствии этот подход был расширен в теории информации (понятие энтропии – меры хаотичности информации). В 60-х годах XX века математики Колмогоров, Хаитин и Соломонофф независимо друг от друга представили важное понятие, которое известно как Колмогоровская сложность. В поисках точного и универсального определения закономерности и хаотичности они пришли к выводу, что оптимальной единицей измерения сложности любой информации является длина наиболее короткой программы, способной генерировать данную информацию.

Случайность не нужно путать с непредсказуемостью. Часть систем могут рассматриваться как случайные, но предсказуемые, а часть таковыми не являются. Действительно, рассматривая демографическую ситуацию в мире и рост популяции человечества, мы можем считать этот рост случайным, хотя он в целом является предсказуемым. Напротив, время жизни и точное время смерти каждого конкретного человека является не только случайным, но и непредсказуемым.

Непредсказуемость крайне необходима в некоторых приложениях, таких как, например, криптография. Напротив, при имитации, как правило, требуется предсказуемость[4].

Подводя некоторые итоги сказанному, необходимо отметить тот факт, что случайность по сей день остается сложной и актуальной проблемой современной науки, находящей массу приложений на практике.

Случайные числа и генераторы случайных чисел

В вычислениях, генераторы случайных чисел – устройства, которые генерируют эти числа из непредсказуемого физического процесса.

Допустим, мы хотим обеспечить настоящую «случайность» при получении чисел. Как это сделать? Получить их из какого-то процесса, который мы не только не контролируем полностью, но и не можем предсказывать. Устройства, базирующиеся на таких процессах, обычно работают с микроскопическими явлениями, такими как термический шум, фотоэффект или квантовые явления. Теоретически, эти процессы полностью непредсказуемы.

Обычно, квантовые генераторы случайных чисел содержат усилитель, который превращает выход физического процесса в некоторые макроскопические параметры, которые можно регистрировать, и преобразователь, который конвертирует выход процесса в цифровой сигнал.

Генераторы случайных чисел могут быть также получены из макроскопических явлений, таких как, например, игральные карты, игральные кости, рулетка. Их непредсказуемость связана с теорией неустойчивых динамических систем и теорией хаоса. Эти теории утверждают, что хотя макроскопические явления и являются детерминированными в рамках Ньютоновой механики, реальные системы развиваются непредсказуемо на практике из-за необходимости знания всех начальных условий. Заметим также, что эта необходимая точность начальных условий растет экспоненциально с ростом времени.

Реальные физические процессы являются сложными, трудно наблюдаемыми, плохо предсказуемыми. Таким образом, использование генераторов случайных чисел на основе физических процессов на практике сильно затруднено. Вместо них обычно используют так называемые генераторы псевдослучайных чисел4.

Генераторы псевдослучайных чисел (PRNG)

Генератор псевдослучайных чисел (ГПСЧ, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел. [5]

Поскольку качество используемых случайных чисел проверяется с помощью специальных тестов, можно не интересоваться тем, как эти числа получены: лишь бы они удовлетворяли принятой системе тестов. Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными числами. Под словом «имитирующие» подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины. [22]

Первый алгоритм для получения псевдослучайных чисел был предложен Джоном фон Нейманом. Он называется методом середины квадратов. Поясним его на примере. Пусть задано 4-значное целое число n1 = 9876. Возведем его в квадрат. Получим, вообще говоря, 8-значное число 97 535 376. Выберем четыре средние цифры из этого числа и обозначим n2 = 5353. Затем возведем его в квадрат (28 654 609) и снова извлечем 4 средние цифры. Получим n3 = 6546. Далее, 42 850116, n4 = 8501 и т. д. В качестве значений случайной величины предлагалось использовать значения 0,9876; 0,5353; 0,6546; 0,8501; 0,2670; 0,1289 и т. д. [22]

Но этот алгоритм не оправдал себя: получалось больше чем нужно малых значений. Поэтому разными исследователями были разработаны другие алгоритмы. Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, linear feedback shift registers, generalized feedback shift registers.

Из современных ГПСЧ широкое распространение получил Mersenne twister, предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (219937-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью Mersenne twister, как неслучайную. Это в частности делает Mersenne twister неподходящим для криптографии.

Достоинства метода псевдослучайных чисел довольно очевидны.

Во-первых, на получение каждого числа затрачивается всего несколько простых операций, так что скорость генерирования случайных чисел зависит от скорости работы компьютера.

Во-вторых, любое из чисел может быть легко воспроизведено.

В-третьих, нужно лишь один раз проверить «качество» такой последовательности, затем ее можно много раз безбоязненно использовать при расчете сходных задач.

Один из главных недостатков метода – ограниченность «запаса» псевдослучайных чисел (наличие периода, ГПСЧ рано или поздно зацикливается). Однако существуют генераторы с очень большим периодом. Подавляющее большинство расчетов по методам Монте-Карло в настоящее время осуществляется с использованием псевдослучайных чисел.[6]

Заключение

Итак, в данном разделе мы заложили фундамент для дальнейшего рассмотрения материалов курса. Так, мы познакомились со следующими основными понятиями и фактами:

-  статистическое моделирование;

-  метод статистических испытаний (методы Монте-Карло);

-  общая схема методов Монте-Карло;

-  области применения статистического моделирования;

-  примеры применения методов Монте-Карло;

-  случайность;

-  непредсказуемость;

-  случайные числа;

-  псевдослучайные числа;

-  генераторы случайных чисел;

-  генераторы псевдослучайных чисел.

В следующих разделах мы поговорим об этом подробнее.

Литература

1.  Gamerman, D. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Boca Raton, FL: CRC Press, 1997.

2.  Gentle J. Random Number Generation and Monte Carlo Methods. Springer-Verlag NY, 1998.

3.  Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. (Eds.). Markov Chain Monte Carlo in Practice. Boca Raton, FL: Chapman & Hall, 1996.

4.  Gourdon X., Sebah P. p and its computation through the ages. April 16, 2003. [http://putation. free. fr/Constants/constants. html]

5.  Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth. New York: Hyperion, pp. 238-239, 1998.

6.  Kuipers, L. and Niederreiter, H. Uniform Distribution of Sequences. New York: Wiley, 1974.

7.  Manno, I. Introduction to the Monte Carlo Method. Budapest, Hungary: Akadémiai Kiadó, 1999.

8.  Metropolis N., Ulam S. The Monte Carlo method, J. Amer. statistical assoc., 1949, 44, N247, 335-341.

9.  Metropolis, N. "The Beginning of the Monte Carlo Method." Los Alamos Science, No. 15, p. 125. [http://jackman. stanford. edu/mcmc/metropolis1.pdf]

10.  Mikhailov, G. A. Parametric Estimates by the Monte Carlo Method. Utrecht, Netherlands: VSP, 1999.

11.  Niederreiter, H. and Spanier, J. (Eds.). Monte Carlo and Quasi-Monte Carlo Methods 1998, Proceedings of a Conference held at the Claremont Graduate University, Claremont, California, USA, June 22-26, 1998. Berlin: Springer-Verlag, 2000.

12.  Sobol, I. M. A Primer for the Monte Carlo Method. Boca Raton, FL: CRC Press, 1994.

13.  Weisstein Eric W. "Monte Carlo Method." From MathWorld – A Wolfram Web Resource. [http://mathworld. /MonteCarloMethod. html]

14.  Большая Советская Энциклопедия. Издание 3-е.–М., Советская энциклопедия, 1970.

15.  , , Шреацидер стохастических испытаний (метод Монте-Карло).–М.: ГИМФЛ, 1962.

16.  , Шрейдер статистических испытаний Монте-Карло и его реализация в цифровых машинах.–Физматгиз, 1961.

17.  Гмурман вероятности и математическая статистика.–М.: Высшая школа, 1977.

18.  Ермаков Монте-Карло и смежные вопросы.–М., 1971.

19.  , Михайлов моделирование. М: Наука, 1982.

20.  , Михайлов статистического моделирования.– М.:Наука, 1976.

21.  . Математические методы статистики. М: Мир, 1975.

22.  Соболь методы Монте-Карло.–М.:Наука, 1973.

23.  Моделируя жизнь // Hard’n’soft, №8, 2001. [http://www. hardnsoft. ru/magazine. php? issue=86&article=18&page=2]

[1] Заметим для любопытных читателей, что как справедливо подчеркнул в своей книге [21] , метод Монте-Карло никак не помогает выигрывать в рулетку и вообще не имеет к этому никакого отношения!

[2] Georges Louis Leclerc Comte de Buffon (7.09.1707 – 16.04.1788, Франция)

[3] – определение сходимости по вероятности.

[4] При подготовке раздела использованы материалы Интернет-библиотеки Wikipedia.

[5] При подготовке раздела использованы материалы Интернет-библиотеки Wikipedia.

[6] По материалам Wikipedia и книги Соболя [22]