Закрыть

Парадокс метода Монте-Карло.

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Теория вероятности

История парадокса

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

Хотя идея этого метода довольно стара, его настоящее применение началось лишь с появлением компьютеров, когда Е. Нейман, С. Улам и Э. Ферми использовали метод Монте-Карло для приближенного решения трудных вычислительных задач, связанных с ядерными реакциями. Название метода объясняется тем, что в нем применяются последовательности случайных чисел, в качестве которых могли бы выступать регулярно объявляемые результаты игр, проводимых в казино, например, в Монте-Карло. Однако на практике случайные числа, необходимые для метода, выдает сам компьютер. Следовательно, симпатичное название (его впервые использовали в 1949 г. Н. Метрополис и С. Улам) вводит в заблуждение (метод вряд ли поможет выиграть в Монте-Карло). Идея метода Монте-Карло впервые появилась в 1777 г. в работе Бюффона , где излагался метод оценки числа я путем бросания иголки наугад. Предположим, что на столе проведены параллельные прямые на единичном расстоянии друг от друга, и на стол наугад бросается иголка длиной $L \leq 1$, при этом угол между прямыми и иглой и расстояние от середины иглы до ближайшей прямой являются независимыми случайными величинами, равномерно распределенными соответственно на $(0,2 pi)$ и $(-1/2, 1/2)$. Тогда игла пересечет какую-нибудь прямую с вероятностью $2 L/n$. Если проводить эксперимент много раз, то относительная частота пересечений будет очень близка к теоретической вероятности $2 L/n$, и таким путем можно вычислить значение $\pi$. Этот метод нахождения приближенного значения имеет чисто теоретическое значение, так как для получения двух точных знаков после запятой нужно совершить несколько тысяч бросаний. Задача Бюффона об игле показывает, что метод Монте-Карло не подходит для очень точных вычислений. Даже для получения результатов с точностью до двух или трех знаков требуется проведение тысяч или миллионов экспериментов. Следовательно, метод Монте-Карло применим только тогда, когда проведение экспериментов моделируется компьютером. Вместо бросания иглы выдаются два независимых случайных числа, которые определяют положение (предполагаемой) иглы и произошло ли ее пересечение с (предполагаемыми) прямыми. Поскольку компьютер способен выдавать несколько миллионов чисел в минуту, моделирование миллионов экспериментов не займет слишком много времени; без компьютера для этого потребовалась бы вся жизнь.

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

В связи с псевдослучайными числами возникает следующий вопрос. В каком смысле их можно считать случайными, если они получены с помощью детерминированных (неслучайных) алгоритмов? После статьи фон Мизеса, вышедшей в 1919 г., некоторые выдающиеся математики исследовали эту проблему.

Парадокс

В 1965—1966 гг. Колмогоров и Мартин-Лёф представили понятие случайности в новом свете. Они определили, когда последовательность, состоящую из 0 и 1, можно считать случайной. Основная идея состоит в следующем. Чем сложнее описать последовательность (т. е. чем длиннее «самая короткая» программа, конструирующая эту последовательность), тем более случайной ее можно считать. Длина «самой короткой» программы, естественно, различна для разных компьютеров. По этой причине выбирают стандартную машину, называемую машиной Тьюринга. Мерой сложности последовательности является длина наиболее короткой программы на машине Тьюринга, которая генерирует эту последовательность. Сложность — мера иррегулярности. Последовательности, длина которых N, называются случайными, если их сложность близка к максимальной.  Мартин-Лёф доказал, что эти последовательности можно считать случайными, так как они удовлетворяют всем статистическим тестам на случайность. Таким образом, сложность и случайность тесно взаимосвязаны. Если программист собирается получить «настоящие» случайные числа, то в силу результатов Колмогорова и Мартин-Лёфа он может это сделать только с помощью достаточно длинной программы. В то же время на практике генераторы случайных чисел очень короткие. Как совместить эти два факта?

Объяснение парадокса

Последовательности, генерируемые короткими программами и используемые в качестве случайных, в действительности удов¬летворяют лишь некоторым, а не всем тестам на случайность. Однако в приложениях это почти не создает проблем. Например, для численного интегрирования достаточно иметь псевдослучайные числа, равномерно распределенные на некотором иyтервале. Предположим, что надо проинтегрировать функцию ограниченной вариации на интервале (0, 1). Величина

$\displaystyle{I= \int_{0}^{1} f(x)dx$

приближается арифметическим средним

$\displaystyle{I_N = \frac{1}{N} \sum_{i=1}^{N} f(x_i)}$

не только тогда, когда последовательность $x_1 , x_2 , ... , x_N$ случайна и равномерно распределена на интервале (0, 1). Достаточно потребовать равномерную распределенность этой последовательности. Это означает, что при $N \to infty$

$\displaystyle{D_N = \sup_{0 \lt x \lt 1} | c (x, N) - x| \to 0},

где $c(x, N) - отношение числа элементов последовательности $x_1 , x_2 , ... , x_N$, принадлежащих $(0, x)$, к N, т. е. относительная частота. Можно показать, что

$|I - I_N| \leq V_f D_N$

где $V_f$ - постоянная, зависящая от функции f (полная вариация функции f). Отсюда следует, что приближение для I тем точнее, чем меньше $D_N$. Однако значение $D_N минимально не тогда, когда берут случайную последовательность. Для случайной последовательности порядок приближения равен $N^{-1/2}$, а для неслучайной последовательности можно получить точность порядка $N^{-1} log N$.

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

Замечания

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

2) Последовательности случайных чисел применяются достаточно широко. Они нужны для численного интегрирования, для численного решения дифференциальных уравнений, для моделирования на ЭВМ физических, химических, биологических, технических и экономических задач и т. д. Они помогают при решении задач уличного движения, транспортных и других оптимизационных задач, а также при создании астрономических моделей. С помощью случайных чисел можно проверять эффективность различных программ на ЭВМ.

Оригинал на: Парадоксы теории вероятностей и математической статистики

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей