3. Применение гсч

Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R – подмножество n‑мерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.

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

.

Сначала необходимо определить прямоугольную область, из которой будут выбираться случайные точки. Это может быть любая область, полностью содержащая фигуру, площадь которой требуется найти. Возьмем в качестве исходной области прямоугольник с координатами углов (0; –1) – (1; 1). Будем последовательно генерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. Если точка удовлетворяет всем неравенствам, значит, она принадлежит фигуре. При достаточно большом числе таких экспериментов отношение числа точек N_F, удовлетворяющих неравенствам, к общему числу сгенерированных точек N_R показывает долю площади прямоугольника, которую занимает фигура. Площадь прямоугольника S_R известна (в нашем случае она равна 2), площадь фигуры S_F вычисляется тривиально:

.

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

Другим примером приближенного взятия определенного интеграла с помощью ГСЧ является вычисление объема шара в n‑мерном пространстве. Объем n‑мерного шара выражается формулой:

,

где Γ(z) – некоторая гамма-функция, определяемая следующим соотношением:

Γ (z+1)=z·Γ(z),

Γ(1)=1.

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

:

.

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

4. Генерирование равномерно распределенных случайных чисел

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

x_k+1 = f(x_k)

Число x_k часто называется зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ и следующее генерируемое значение.

Поначалу функции f выбирались как можно более сложные и трудно понимаемые. Например, f(x) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62‑разрядного квадрата числа x (модификация метода средин квадратов). Но отсутствие теории относительно f приводило к катастрофическим последствиям. Для метода средин квадратов это уже упоминавшееся зацикливание при обращении очередного числа в нуль. Поэтому уже довольно давно перешли к использованию функций, свойства которых вполне известны. Всякая последовательность целых чисел из интервала (0, 2³¹–1) должна содержать повторения самое большое после 2³¹≈10⁹ элементов. Используя теорию чисел, можно выбрать такую функцию f, для которой наперед будет известно, что ее период максимально возможный или близкий к максимальному. Этим избегается преждевременное окончание или зацикливание последовательности. Дальнейшее использование теории чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел.

Представим генерирование чисел в диапазоне [0; 1] рекуррентым методом графически (см. рис.  1). Очевидно, функция f(x) должна быть определена на всем отрезке [0; 1] и иметь на этом отрезке непрерывную область значений [0; 1], в противном случае генерируемые числа будут составлять лишь несобственное подмножество указанного отрезка.

а) б)

Рис. 1. Графическое представление рекуррентного ГСЧ:

а) с «плохой» функцией f(x); б) с «хорошей» функцией f(x).

Считается, что функция f(x) тем лучше подходит для генерирования случайных чисел, чем более плотно и равномерно ее график заполняет область x[0; 1], y[0; 1]. Например, функция, приведенная на рис.  1, а, будет давать последовательность чисел с сильной корреляционной зависимостью соседних элементов. В случае функции, приведенная на рис.  1, б, эта зависимость будет значительно слабее.

В настоящее время широкое распространение получили линейные конгруэнтные ГСЧ. В таком ГСЧ каждое следующее число получается на основе единственного предыдущего, при этом используется функция f вида:

f(х) = (ах+с) mod m,

где для n‑разрядных двоичных целых чисел m обычно равно 2ⁿ.

Конгруэнтный ГСЧ выдает псевдослучайные целые числа в интервале (0, m). Параметры x₀, a и c – целые числа из той же области, выбираемые исходя из следующих соображений:

1. x₀ может быть произвольно. Для проверки программы возможно x₀=1. В дальнейшем в качестве x₀ можно брать текущее время, преобразованное в число из интервала (0, m). Такой подход обеспечивает различные последовательности для различных запусков программы.

2. Выбор a должен удовлетворять трем требованиям (для двоичных машин):

1. a mod 8 = 5;

2. ;

3. двоичные знаки а не должны иметь очевидного шаблона.

3. В качестве c следует выбирать нечетное число, такое, что

.

Более подробные рекомендации по выбору параметров можно найти у Д. Кнута [2].

При использовании конгруэнтного ГСЧ следует помнить, что наименее значимые двоичные цифры x_k будут «не очень случайными». Поэтому, если, например, вы хотите использовать число x_k для случайного выбора одной из 16 возможных ветвей, берите наиболее значимые разряды x_k, а не наименее значимые. Наконец, для большей надежности полезно предварительно испытать случайные числа на какой-либо задаче с известным ответом, схожей с реальным приложением.