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

Известен одновременно забавный и грустный факт, состоящий в том, что после более чем 20 лет работы в конце XIX века англичанин В. Шенкс нашел 707 знаков числа, но в 1945 году при помощи компьютера определили, что он ошибся в 520-м знаке и дальнейшие вычисления оказались неверными.

В эру современных компьютеров не составляет проблемы вычислить число p с необходимой точностью (так, в 2002 году было вычислено 1 241 100 000 000 знаков числа). Все эти вычисления обычно проводятся при помощи суммирования некоторых рядов.

Мы в данном разделе рассмотрим подход к нахождению числа p методом статистического моделирования.

Игла Бюффона

В 1777 году французский естествоиспытатель Жорж Луи Леклерк де Бюффон[2] сформулировал задачу о нахождении вероятности того, что брошенная на разграфленный лист бумаги игла пересечет одну из линий. Оказалось, что эта вероятность связана с числом p, что сделало возможным поиск этого числа вероятностными методами, т. е. методом Монте-Карло! Эта задача захватила умы многих исследователей. И сейчас, уважительно называемая теоремой, она имеет ряд интересных приложений [23].

Изучим проблему с точки зрения математики.

Для этого рассмотрим на плоскости параллельные прямые x = 0 и x = d, образующие бесконечную полосу ширины d. Пусть теперь мы произвольным образом бросаем на плоскость иглу длины . Вопрос: какова вероятность того, что игла пересечет одну из прямых?

Для решения задачи посмотрим на рис. 1.2.

Рис. 1.2 Игла Бюффона. Положение иглы

Интересующее нас положение иглы на плоскости (y-координата неинтересна) описывается двумя параметрами (двумя независимыми случайными величинами): координатой одного из концов h и углом поворота относительно горизонтальной оси . Очевидно, .

Множество возможных положений иглы целиком определяется случайным выбором точки из области F(h, ) = .

Рассмотрим событие A – игла пересекает по прямую x = d.

(1.4)

Нарисуем в плоскости область, соответствующую событию A.

Рис. 1.3 Игла Бюффона. Условие пересечения

Найдем площадь S+ этой области. Обозначим через S площадь всего прямоугольника, отвечающего пространству элементарных исходов, а S- – площадь под кривой

По определению S = S+ + S-.

Найдем .

Теперь вероятность события A может быть вычислена как

Итак, вероятность того, что игла пересечет прямую теоретически есть

(1.5)

Будем проводить эксперимент по бросанию иглы N раз, регистрируя в каждом эксперименте факт наступления/не наступления события A.

Рассмотрим случайную величину .

Введем частота наступления события A.

Тогда , причем данные исходы не равновероятны.

Известно, что случайная величина подчиняется биномиальному распределению. Определим параметры распределения.

Будем рассматривать – частоту наступления события A – в качестве оценки величины p – вероятности того, что игла пересекает одну из прямых. Зная теоретическую вероятность этого события , мы можем оценить эту вероятность по достаточно большой выборке () и рассмотреть следующее равенство:

(1.6)

Тогда

(1.7)

Попробуем понять, насколько хороша оценка (1.7).

Для этого докажем ряд утверждений.

Утверждение

, т. е. – несмещенная оценка значения p.

Доказательство:

Учитывая, что величина SN есть результат выполнения N независимых испытаний (биномиальное распределение), имеем:

, ч. т.д.

Несложно показать, что – эффективная оценка p (оценка с наименьшей дисперсией), а также состоятельная оценка p (сходится по вероятности[3] к p).

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

Для того чтобы подобрать параметры эксперимента так, чтобы дисперсия была минимальной, необходимо решить задачу минимизации

(1.8)

Решив задачу, получаем, что минимум достигается при l = d.

Тогда .

Для исключения вырожденного случая SN = 0 определим нашу оценку числа p следующим образом:

(1.9)

Можно показать, что оценка (1.9) сходится по вероятности к p.

Метод Hit-Or-Miss

Еще один метод оценивания числа p называется Hit-Or-Miss («попал – не попал»). Метод состоит в следующем: рассмотрим единичный квадрат на координатной плоскости и четверть окружности единичного радиуса с центром в начале координат (рис. 1.4).

Рис. 1.4 Метод Hit-Or-Miss

Пусть единичный эксперимент состоит в том, что в единичном квадрате случайно выбирается любая точка. Рассмотрим событие A, состоящее в том, что точка попала в рассматриваемый сектор окружности.

Площадь квадрата Smax = 1, площадь выделенной области .

Рассмотрим случайную величину .

Введем частота наступления события A.

Тогда , случайная величина подчиняется биномиальному распределению. Определим параметры распределения.

Будем рассматривать – частоту наступления события A – в качестве оценки величины p – вероятности того, что точка попала в указанный сектор окружности. Зная теоретическую вероятность этого события , мы можем оценить эту вероятность по достаточно большой выборке () и рассмотреть следующее равенство:

(1.10)

Тогда можно рассмотреть

(1.11)

, таким образом (1.11) дает несмещенную оценку.

Метод Выборочного среднего

Рассмотрим функцию .

Рассмотрим .

Заметим, что что определяет функцию q(x) – плотность равномерного распределения на отрезке [0; 1].

Тогда