Бакаев Методы статистических испытаний 2007

Глава 2 Исторические предпосылки возникновения и общие характеристики группы методов Монте-Карло

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

М. Булгаков. Мастер и Маргарита.

Часто вместо слов “методы Монте-Карло” говорят в единственном числе “метод Монте-Карло”, понимая, однако под этим собирательный термин для обозначения группы методов,

объединенных по определенному принципу родства. Кроме того, вместо “метод/методы Монте-Карло” часто применяют термин “метод/методы статистических испытаний”, который является более информативным и более точно определяет специфику используемого подхода.

Официальной датой рождения методов Монте-Карло принято считать 1949 год, когда появилась статья Н. Метрополиса и С. Улама1, посвященная описанию первого метода из этой группы. Поговаривают, однако, что сам термин “метод Монте-Карло” появился еще во время Второй мировой войны, когда Джон фон Нейман и Станислав Марцин Улам работали в Лос-Аламосе над моделированием нейтронной диффузии в расщепляемом материале. Что же это за метод с таким необычным, если не сказать экзотическим названием, и

1 N.Metropolis and S.Ulam, The Monte Carlo Method, J. Amer. Stat. Assos. 44(1949), 335-341.

11

почему он приобрел такую огромную популярность в последующие годы?

Как известно, Монте-Карло – это имя столицы европейского игорного бизнеса, где люди годами ищут удачу, пытаясь реализовать свое счастье в азартных играх. Именно процесс азартной игры, в которой роль Его Величества Случая первостепенна, как считают, послужил стимулом к открытию нового подхода в моделировании. Хотя приемы, присущие методам Монте-Карло, были известны и до 40-х годов ХХ века, считается, что в наиболее оформленном виде эта идея возникла у С. Улама. Вот как он сам описывает открытие нового подхода:

The first thoughts and attempts I made to practice [the Monte Carlo method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires. The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than ‘abstract thinking’ might not be to lay it out, say, one hundred times, and simply observe and count the number of successful plays. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neuron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. Later … [in 1946] I described the idea to John von Neumann, and we began to plan actual calculations.2

2 Первые мысли и попытки, которые я начал реализовывать на практике (в отношении метода Монте-Карло), были навеяны вопросом, занимавшим меня в 1946 году, когда я раскладывал пасьянсы, восстанавливаясь от болезни. Вопрос, привлекший мое внимание тогда, состоял в определении шансов того, что пасьянс Кэнфилда на 52-х картах разложится успешно. Проведя кучу времени в попытках оценить эти шансы чисто комбинаторными расчетами, я затем заинтересовался, а нельзя ли воспользоваться более практичным методом, чем «чисто абстрактное

12

Впоследствии многие источники связывали возникновение и развитие метода Монте-Карло с именем самого Дж. фон Неймана, что можно объяснить тем, что он возглавлял научную группу в Лос-Аламосе, развивавшую данное научное направление. Следует, однако, указать, что Дж. фон Нейман лично инициировал решение некоторых практических задач в ходе реализации метода Монте-Карло – в частности, ему принадлежит метод середины квадрата для генерации случайных чисел (см. главу 3).

Метод Монте-Карло в его современном понимании – это

любая техника статистических испытаний, примененная для решения количественных проблем. Сам С. Улам не изобрел статистические испытания – они уже использовались ранее для количественного решения некоторых задач; при этом, для генерации испытаний использовались определенные физические процессы, такие, например, как выбрасывание игральной кости или вытаскивание карт из колоды. В частности, В.С. Госсетт, публиковавший свои работы под именем Student, делал в 1908 году случайные пробы отпечатков пальцев 3000 преступников для моделирования двух коррелированных нормальных распределений. Вклад же Улама состоял в том, что он осознал потенциальные возможности электронных компьютеров (изобретенных к тому времени) для автоматизации соответствующих статистических испытаний. Работая вместе с Джоном фон Нейманом и

размышление», например разложить пасьянс, скажем, сто раз и просто сосчитать, фиксируя результаты наблюдения, количество успешных раскладок. Такие эксперименты можно было автоматизировать в связи с зарождающейся новой эрой быстрых компьютеров, и я сразу же подумал о проблемах нейронной диффузии и других вопросах математической физики, а заодно и о более общей постановке задачи – каким образом вообще можно было бы характеризовать процессы, описываемые определенными дифференциальными уравнениями, в эквивалентной форме как последовательность случайных операций. Позже…[в 1946 году] я поделился этой идеей с Джоном фон Нейманом, и мы стали уже планировать реальные расчеты.

13

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

Что же касается самого термина метод Монте-Карло, то, как говорят, его придумал Метрополис, обнаруживший большое сходство между новой методологией и процессами на игорных столах в княжестве Монако. Улам и Метрополис опубликовали свою первую статью по методу Монте-Карло в

1949 году.3

Рассмотрим одну из классических задач, демонстрирующих технику, типичную для методов Монте-Карло. Это знаменитая задача об игле Бюффона – задача, которую предложил Джордж Луи Леклерк, граф де Бюффон в 1733 году, - более, чем за 200 лет до того, как Метрополис ввел термин “метод Монте-Карло”. Задача ставится следующим образом: на плоскость, разграфленную параллельными прямыми, отстоящими друг от друга на расстоянии d, наудачу бросается игла длиною l. Требуется определить, какова вероятность того, что игла пересечет одну из проведенных параллелей.

Заметим, что решение этой задачи было дано самим Бюффоном, и искомая вероятность определяется формулой

P =	2l	.	(2.1)
	π d

3 Эта статья уже цитировалась выше.

14

Несмотря на полученное решение, эта задача поглотила умы исследователей того времени, но уже с иной (скажем, довольно неожиданной) стороны, – они пытались применить результат решения задачи об игле Бюффона для практического вычисления числа π.4 Действительно, проводя эксперимент по достаточно большому количеству выбрасываний иглы и заменяя затем приближенно искомую вероятность практически определенной частотой пересечения иглой одной из параллельных прямых по формуле

P ≈ mn ,

где п – общее число выбрасываний иглы, а т – полное число наблюденных пересечений, можно получить следующую практическую оценку числа π:

π ≈	2l n	.	(2.2)
	m d

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

Results of Captain O.C.Fox’s Needle Dropping Experiments

п	т	l	d	surface	theπ ’s
		(inches)	(inches)		estimate
500	236	3	4	stationary	3.1780
530	253	3	4	rotated	3.1423
590	939	5	2	rotated	3.1416

4 Заметим, что задача вычисления числа π является по своей сути задачей в детерминированной постановке.

15

В последних двух экспериментах Фокс поворачивал между бросками поверхность, на которую выбрасывалась игла.5 Он применял этот прием, чтобы по возможности исключить уклон поверхности, который мог бы повлиять на окончательное положение выбрасываемой иглы.6 Кроме того, то, что Фокс использовал в своем третьем эксперименте более длинную иглу, которая при одном броске могла пересекать до 3-х линий одновременно, также считается инновацией, рассматриваемой ныне как одна из первых попыток уменьшить дисперсию (т.е. ошибку) метода. И, действительно, оценка числа π – самая лучшая именно в 3-м эксперименте.7

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

В любом случае, идет ли речь о решении задачи в детерминированной или стохастической постановке, в современном понимании метод Монте-Карло – это любой метод, имеющий дело со стохастической постановкой задачи, а если исходная задача была изначально сформулирована как детерминированная, то она должна быть переформулирована в

5Напомним, что слово” fox” переводится с английского языка как “лиса” – последнее является у многих народов синонимом слова “хитрый”.

6Фактически эта идея Фокса стала предвестником некоторых современных приемов по улучшению качества используемых в методах Монте-Карло псевдослучайных чисел.

7В третьем своем эксперименте Фокс использовал иглу, длина которой в 2,5 раза больше расстояния между параллельными линиями. Оказывается, формула (2.1) сохраняет свой смысл, если величину P, которая в данном случае может принимать значения, большие 1, интерпретировать как среднее число (математическое ожидание числа) линий, пересекаемых иглой при одном броске. Что касается самой оценки числа π по формуле (2.2), то

она применима при любых соотношениях между l и d.

16

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

общего изучения методов Монте-Карло.

Специалисты различают понятия имитационного и численного моделирования: в первом случае моделируется поведение всех компонентов системы, во втором – только наиболее существенных. К какому классу методов отнести методы Монте-Карло? Более ранние методы Монте-Карло следует, по-видимому, рассматривать как имитационные. Имитация не всегда является лучшим способом для моделирования соответствующего процесса или явления; иногда в практических задачах заведомо не используется вся информация, характеризующая процесс/явление, в связи с чем были разработаны методы Монте-Карло с повышенной скоростью расчета, обусловленной отказом от использования определенной лишней информации. Такие методы И.М. Соболь называет численными методами Монте-Карло. Но грань между имитационными и численными методами Монте-Карло довольно условная; точного разделения на два указанных класса методов не существует. Заметим также, что в связи с расширением возможностей современных компьютеров роль имитационных методов в последнее время значительно укрепилась. Рост популярности имитационных методов связан также с тем, что они, как правило, более доступны для интерпретации многими практическими пользователями, среди которых могут быть, например, биржевики, финансисты, маркетологи, социологи, историки и др.

Сразу укажем один из важнейших приемов конструирования методов Монте-Карло – это интерпретация исходной задачи как задачи расчета математического ожидания некоторой случайной величины. Пусть, например, речь идет о вычислении интеграла

I = ∫ f x d x,

Ω

где Ω – некоторая заданная область п-мерного пространства, х – п-мерный вектор (точка), а f(x) – заданная функция. Пусть далее p(x) > 0 – плотность распределения вероятности п-мерной

17

случайной величины Х. Тогда, вводя новую функцию

F( x ) = pf xx , получим

I = M F x = ∫F x p x d x,

Ω

то есть искомая задача сводится к вычислению математического ожидания случайной величины F(х). Такая задача может быть решена следующим образом при помощи техники статистических испытаний: имея в распоряжении N независимых реализаций x1,x2,…,xN случайной величины Х, можно получить статистическую оценку математического ожидания случайной величины F(Х) как

M F x ≈ N F x + F x +...+ F xN .

Из математической статистики также известно, что можно также получить оценку дисперсии для F(Х), то есть фактически оценку для ошибки метода.8 Что касается конструирования значений x1,x2,…,xN случайной величины Х адекватным образом – это также одна из основных задач, подлежащих обсуждению в курсе методов Монте-Карло

8 Такие оценки будут строиться и анализироваться в ходе нашего основного изложения.

18

Глава 3 Генерация случайной величины с равномерным законом распределения

–И доказательств никаких не требуется,

–ответил профессор и заговорил негромко, причем его акцент почему-то пропал: – Все просто…

М. Булгаков. Мастер и Маргарита

Использование случайных величин с некоторыми законами распределения и подчиненных некоторым дополнительным требованиям (например, требованиям определенной корреляции) составляют основу любого метода Монте-Карло. Как будет показано позже, какому бы закону распределения не требовалось удовлетворить при генерации случайной величины, достаточно исходить из того, что в распоряжении имеется процедура генерации одномерной случайной величины, равномерно распределенной на интервале (0;1).1 Поэтому в данной главе вопрос генерации равномерного закона распределения рассматривается отдельно от других вопросов, освещенных в книге.

1 Для целей нашего изложения следует сразу же напомнить, что вероятность попадания непрерывной случайной величины в интервал (a; b) равна вероятности ее попадания в соответствующий отрезок [a; b] или один из полуинтервалов [a; b), (a; b] – одна из упомянутых ситуаций встретится при доказательстве теоремы 3.1 ниже. Таким образом, вместо случайной величины, равномерно распределенной на интервале (0; 1), можно говорить о случайной величине, равномерно распределенной на отрезке [0; 1] или на одном из полуинтервалов [0;1), (0; 1].

19

3.1 Случайные числа и случайные цифры

Определение 3.1. Случайным числом будем называть одномерную случайную величину Γ, равномерно распределенную в интервале (0; 1).

Определение 3.2. Случайной цифрой будем называть дискретную одномерную случайную величину Е, принимающую

значения 0, 1,…, 9 с одинаковыми вероятностями 1 .

10

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

Γ = 0. Е1 Е2… Еk …,

или в более компактной записи

		∞
		Γ = ∑Ek 10−k .
		k =1
Теорема	3.1.	Десятичные цифры Е1, Е2, …, Еk, …
случайного	числа	Γ представляют собой независимые

случайные цифры. Наоборот, если Е1, Е2, …, Еk, … - независимые случайные цифры, то Γ= 0. Е1 Е2… Еk … является случайным числом.

Доказательство. Докажем вначале первую часть утверждения. Пусть Γ – случайное число, то есть случайная величина Γ равномерно распределена в интервале (0;1). Очевидно Еk принимает цифровое значение i тогда и только тогда, когда

0. Е1 Е2… Еk-1 i ≤ Γ < 0. Е1 Е2… Еk- i + 0. 0 … 0 1 , (3.1) k цифр

20