Генератор случайных чисел (стр. 2 из 4)

Представим генерирование чисел в диапазоне [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 должен удовлетворять трем требованиям (для двоичных машин):

a mod 8 = 5;

;

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

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

.

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

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

5. Генерирование чисел с произвольным распределением

Достаточно часто возникает необходимость сгенерировать последовательность случайных чисел y_i, равномерно распределенных на данном конечном интервале [a, b], с помощью ГСЧ, выдающего числа x_i на интервале [0, m]. Приведение диапазона ГСЧ к нужному интервалу в этом случае осуществляется простым линейным преобразованием:

.

Распределение чисел после такого преобразования остается равномерным.

Более сложным случаем является генерирование случайных точек из некоторого множества в n‑мерном пространстве Rⁿ, например, точек из некоторой области на плоскости. Рассмотрим формирование случайных точек для нескольких простых областей: прямоугольника, окружности и круга.

а) б) в)

Рис. 2. Области, из которых выбираются точки

Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис.2, а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки:

,

где u_j – равномерно распределенное случайное число из отрезка [0, m].

Окружность можно представить одномерным множеством точек с угловой координатой φ, принимающей значения на интервале (0, 2π). Таким образом, декартовы координаты очередной точки можно вычислить следующим образом:

.

где u_j – равномерно распределенное случайное число из интервала (0, m); r – радиус окружности.

В случае круга первое, что приходит в голову – воспользоваться полярной системой координат (ρ, φ), в которой данное множество фактически представляет собой прямоугольник (а для него способ генерации чисел известен). Однако при переходе от полярных координат к декартовым нарушается распределение случайных чисел: оно становится неравномерным; плотность распределения в центре круга выше, чем по краям.

Существует несколько способов получения равномерного распределения по кругу. Рассмотрим один из них. Будем генерировать случайные пары (x, y) и для каждой из них ставить внутри круга соответствующую точку, заполняя таким образом эту область. Исходя из представлений о равномерном распределении можно предположить, что при достаточно большой длине сгенерированной последовательности на единицу площади круга будет приходиться примерно одно и то же количество точек вне зависимости от их расположения (другими словами, при равномерном распределении плотность точек по кругу будет одинакова).

Воспользуемся полярной системой координат для генерирования точек. При этом будем выбирать угол φ равномерно распределенным на интервале (0; 2π), а распределение ρ построим следующим образом:

,

где x – равномерно распределенная на отрезке [0; 1] случайная величина. Можно показать, что при таком способе формирования координат случайные точки будут равномерно распределены по всей площади круга.

Помимо выбора из произвольного множества, часто требуется формировать числа с распределением, отличным от равномерного. Распределение обычно задается функцией плотности распределения f(x) либо функцией распределения F(x). Функция распределения в произвольной точке x показывает вероятность того, что случайная величина X окажется меньше данного значения x:

F(x)=P (X<x).

Функция плотности распределения представляет собой производную F(x):

.

Функция F(x) для любой случайной величины является неубывающей на всем интервале (–∞; +∞), стремится к 0 при x→ –∞ и к 1 при x→ +∞. Для получения случайных чисел с заданным распределением F(x) необходимо найти функцию, обратную к F(x), т.е. такую функцию G, что для всех y=F(x) выполняется G(y)=x. Это можно пояснить следующим образом. Предположим, что мы многократно выбираем число y, равномерно распределенное на интервале [0; 1]; каждому y мы ставим в соответствие некоторое x=G(y). Выбору 50000 игреков соответствует выбор 50000 иксов. Таким образом, доля выбранных y, лежащих между двумя фиксированными значениями, скажем y₁ и y₂, в точности равна доле x, лежащих в интервале [x₁; x₂]. Но вероятность первого из названных событий равна | y₂ – y₁ |, если y распределено равномерно; следовательно, верна цепочка равенств:

доля чисел в интервале [x₁; x₂] = доля чисел в интервале [y₁; y₂] = y₂ – y₁ = F(x₂) – F(x₁) =

,

которая и показывает, что в случае равномерного распределения игреков x имеет распределение с плотностью f(τ). Сложной проблемой в этом подходе является достаточно быстрое и точное формирование обратной функции распределения G(y).

Рассмотрим в качестве примера получение случайного числа с экспоненциальным распределением. Это распределение характеризуется одним параметром λ>0 и имеет следующие функции распределения и плотности распределения:

, x≥0;

.

Для этого распределения легко получить F^–1 (y), т.е. разрешить уравнение F(x)=y. Решение имеет вид