Получение и тестирование случайных чисел.

Все методы моделирования, рассматриваемые в настоящем пособии, основаны на применении численных значений случайных величин – так называемых “случайных чисел”. Наиболее часто возникает необходимость получения последовательности численных значений случайной величины равномерно распределённой на интервале (0,1).

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

Итак, как получить последовательность значений непрерывной случайной величины, равномерно распределённой на интервале (0,1).

Очевидный способ – использовать хорошую рулетку, на которой вероятности выпадения всех цифр от 0 до 9 строго одинаковы. С помощью такой рулетки можно получать случайные числа с любым количеством значащих цифр. Первые таблицы случайных чисел были получены с помощью рулеток. Такие таблицы несколько раз издавались в виде книг. К такой таблице термин «случайные числа», строго говоря, неприменим. Это таблица чисел, которые обладают свойствами случайных чисел.

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

Преимущества этого способа состоят в том, что запас случайных чисел неограничен, числа получаются очень быстро и не требуется памяти для их хранения. Недостатки состоят в необходимости специального электронного устройства, которое требует периодической проверки, и в невозможности воспроизведения последовательности чисел, а следовательно, и расчёта. Для отладки работы программы желательна возможность проведения серии расчётов с одной и той же последовательностью случайных чисел [3-7].

В настоящее время наибольшее распространение получили генераторы случайных чисел, которые вычисляют последовательность чисел с помощью рекурентного соотношения.

Рис.1.1 Функция

Рекуррентное соотношение позволяет последующее числовычислять путём подстановки предыдущего числа в определённую формулу, или алгоритм:

(1.6)

Первый алгоритм такого рода было предложен Дж. Нейманом и Н. Метрополисом Он получил название «метод середины квадрата». Очередное число последовательности в нём получается так: предыдущее число возводится в квадрат и в полученном результате берутся средние цифры. Например: 6725; 45225625; 2256. На первый взгляд, метод представляется безупречным, так как трудно усмотреть какую либо причину для корреляции значений двух последовательных чисел. Однако оказалось, что метод даёт больше, чем нужно малых значений.

Линейный конгруэнтный метод.

Чтобы получить представление о свойствах функции , попытаемся представить вид её графика на плоскости Будем для определённости иметь в виду равномерное распределение случайных чисел на отрезке Тогда график функции будет расположен внутри квадрата со стороной равной единице (Рис.1). По обеим осям будут отложены фактически одни и те же равномерно распределённые точки. Это означает, что график должен как можно более равномерно заполнять квадрат 1x1.

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

(1.7)

Здесь значокозначает дробную часть. Рис. 1.1, построенный для m=8 поясняет принцип алгоритма (1.7). На самом деле, надо использовать в качестве – большое число. На этой идее основан метод получения случайных чисел, предложенный Д. Лемером. Сейчас он чаще всего называется «линейный конгруэнтный метод». Его исследованию посвящена обширная литература.

Наиболее часто линейный конгруэнтный метод применяется в следующем виде: Выбирают четыре целых положительных числа [6,7]:

1. Множитель a;

2. Сдвиг c;

3. Модуль m;

4. Первое число последовательности x₀.

Последовательность случайных чисел определяется формулой:

(1.8)

где индекс n пробегает значения 0, 1, 2, ... Символ b mod m означает остаток от деления числа b на m. Очевидно, что b mod m < m. Поэтому все числа последовательности x_n удовлетворяют неравенству x_n < m. Последовательность чисел y_n, равномерно распределенных в интервале от нуля до единицы, получается по формуле:

(1.9)

Далеко не любой выбор четырех исходных чисел ведет к хорошим результатам. Заметим прежде всего, что последовательность чисел x_n неизбежно должна быть периодической, причем период не может быть больше, чем m. Действительно, так как все x_n – целые числа, причем x_n < m, количество различных чисел не может превышать m. Поэтому, начиная, по крайней мере, с n = m, появится число, которое уже встречалось, и все повторится заново.

Однако получить последовательность с максимально возможным периодом L = m далеко не просто. Если выбирать исходные числа не задумавшись, то, как правило, будут получаться последовательности с маленьким периодом.

Итак, чтобы получить генератор с максимально возможным периодом L, нужно взять в качестве m самое большое число, с которым может оперировать данная ЭВМ, и выбрать остальные числа в соответствии с следующей теоремой.

Теорема. Если последовательность определяется формулой (1.8) с c ≠ 0, тот ее период равен m тогда и только тогда, когда выполнены следующие условия:

а) c и m – взаимно простые числа (не имеют общих делителей, кроме единицы);

б) b = k–1 кратно p для любого простого числа p, являющегося делителем m;

в) b кратно 4, если m кратно 4.

Разработана сложная система тестов, которая позволяет определить качества генератора случайных чисел. Поэтому рекомендуется использовать только проверенные генераторы. При выборе генератора свойства ЭВМ важны не только для того, чтобы выбрать максимально возможный период. От выбора параметров генератора зависит скорость генерации случайных чисел. При этом оказывается, что для ЭВМ разных конструкций оптимальными являются разные генераторы. В частности, приводятся данные для генератора, работающего на основе линейного конгруэнтного метода с периодом 2³⁸ ≈ 2,75 × 10¹¹ [7].

За последнее время получили распространение генераторы случайных чисел, основанные на другой идее.

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) рекомендуется сейчас для получения генерации псевдослучайных чисел в статистических алгоритмах, критичных к качеству случайных чисел.

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

если и (1.10)

если

где — вещественные числа из диапазона [0, 1), a, b — целые положительные числа, называемые «лагами». Для работы фибоначчиеву датчику требуется знать max(a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max(a, b) случайных чисел, которые могут быть генерированы простым конгруэнтным датчиком.

Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: a = 55, b = 24; a = 17, b = 5; a = 97, b = 33. Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения a = 17, b = 5 можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения a = 55, b = 24 позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения a = 97, b = 33 позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев датчик случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab.

Тестирование случайных чисел

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

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

При этом проверяется (1) частота различных цифр, (2) проводится проверка частот различных двузначных чисел, (3) проверяется частота интервалов между последовательными нулями, Проверяются частоты различных типов четвёрок и т.п.

В настоящее время широко рекомендуется для проверки генераторов случайных чисел система тестов DIEHARD. Это набор из 11 тестов, каждый из которых представляет собой проверку одного из принципиальных результатов теории вероятности.

1.3 Преобразование случайных величин [3,5]

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

Любой закон распределения может быть получен из равномерного на интервале (01).

Получение (разыгрывание) дискретной случайной величины

Значения случайной величины и вероятности их реализации представим в виде таблицы:

Соотношение (1.4) позволяет разбить интервал (0,1) на интервалов, так что длина каждого интервала равна вероятности реализации соответствующего значения .(рис.). Такое разбиение предоставляет следующий способ получения распределения дискретной случайной величины с помощью равномерного распределения на интервале (0,1).

Берётся случайное число из равномерного распределения на интервале (0,1) и определяется, в какой из интервалов это число попало. Если оно попало в интервал с номером , то случайной величине приписывается значение Затем берётся новое число из равномерного распределения, и вся процедура повторяется.

Рис.1.2 Рулетка, поделённая на секторы разного размера так, что размер сектора пропорционален вероятности дискретной случайной величины. Простой способ реализации распределения этой величины

Разыгрывание непрерывной случайной величины с произвольной плотностью распределения.

Существует несколько методов преобразования равномерного распределения на интервале (0,1) в распределение с заданной плотностью на интервале . Один из них состоит в решении следующего уравнения:

(1.11)

где число из равномерного распределения на (0,1), а значение случайной величины, распределённой с плотностью на .

Функция является монотонно возрастающей, так как . Любая прямая параллельная оси абсцисс пересекает функцию в единственной точке. Абсцисса этой точки является искомым значением случайной величины , распределённой с плотностью . Таким образом , уравнение имеет всегда единственное решение.

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

(1.12)

Так как величина равномерно распределена на отрезке (0,1), то

(1.13)

Применение доказанного соотношения для плотности распределения в виде затухающей экспоненты.

Интегралы редко берутся. В этом главный недостаток рассмотренного метода. На практике часто достаточно использовать численное интегрирование. Плотность Распределение непрерывной величины часто достаточно рассматривать в конечном числе точек и плотность распределения представить в виде гистограммы. Значения интеграла удобно заранее вычислить для нужных точек и ввести в память в виде массива F. Тогда получение нового случайного числа с распределением по случайному числу из равномерного распределения сведётся просто к перебору элементов массива F.

Получение приближённого нормального распределения

В теории вероятностей и её приложениях большое значение имеет т.н. «нормальное распределение». Это непрерывное распределение с плотностью, записываемой в виде.

(1.14)

Оно характеризуется двумя параметрами и . Первый параметр равен математическому ожиданию и характеризует среднее арифметическое значение. Второй параметр равен квадратному корню из дисперсии и характеризует ширину распределения.

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

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

Эта теорема даёт теоретическое обоснование для следующего метода получения нормально распределённых случайных чисел на основе стандартного генератора случайных чисел, дающего равномерно распределённые числа на промежутке (0,1).

Чтобы разыграть возможное значениенормальной случайной величины с параметрами и , надо сложить 12 случайных чисел из равномерного распределения на интервале (0,1) и из полученной суммы вычесть 6.

(1.15)

Число 12 в этом правиле возникло из-за того, что дисперсия для равномерного распределения равна 1/12. Дисперсия суммарного распределения равна сумме дисперсий. Чтобы дисперсия суммарного нормального распределения равнялась 1 необходимо складывать случайные числа 12ти равномерных распределений. Число 6 вычитается, чтобы центр нормального распределения был расположен на нуле. Точность получения нормального распределения может быть повышена за счёт увеличения числа слагаемых в сумме, но при этом, разумеется, значения и изменятся.

Основные положения главы 1

Необходимым элементом получения статистических моделей является генератор случайных чисел, который должен удовлетворять набору жёстких требований:

удовлетворять статистическим тестам;

иметь как можно более длинный период;

работать как можно более быстро;

воспроизводить одну последовательность чисел необходимое число раз.

Существует набор методов, которые, используя равномерное распределение случайных чисел на интервале (0,1), позволяют получить распределение случайных чисел с любой заданной плотностью распределения.