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

Возможно использование трех способов генерации случайных чисел:

- аппаратный (физический);

- табличный (файловый);

- алгоритмический (программный);

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

Один из вариантов реализации заключается в следующем.

Возьмем фиксированный промежуток времени Δt. Если в его течение уровень напряжения превысит пороговое значение четное число раз – записывается ноль, нечетное – единица.

Для получения m-разрядного случайного числа параллельно соединяют m – генераторов.

Достоинства метода:

- запас чисел не ограничен;

- не занимается место в памяти ЭВМ;

Недостатки:

- требуется периодическая проверка и настройка;

- нельзя воспроизвести последовательности;

- требуется специальное устройство;

Табличный способ основан на использовании специальных таблиц, в которых размещены случайные числа, распределенные по какому-либо закону.

В компьютерных моделях такой способ применяется довольно редко.

Достоинства метода:

- требуется однократная проверка;

- можно воспроизвести последовательности;

Недостатки:

- ограниченный запас чисел;

- занимает существенное место в памяти (при обращении к внешней памяти требуется время);

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

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

Достоинства:

- требуется однократная проверка;

- можно многократно воспроизводить последовательности чисел;

- занимает мало места в памяти;

- не используются внешние (аппаратные) устройства.

Недостатки:

- запас чисел ограничен периодом генератора;

- более высокие затраты машинного времени на расчет.

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

Чаще всего используются так называемые конгруэнтные методы (наиболее распространенный – мультипликативный).

В основе конгруэнтных процедур лежит понятие конгруэнтности.

Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что a-b = km, т.е. если разность a-b делится на m и если числа a и b дают одинаковые остатки от деления на абсолютную величину m.

Рекуррентное соотношение имеет вид:

X_i+1 = λX­_i mod M,

где λ,X₀ – целые положительные нечетные числа;

М – наиболее удобно выбирать так: M = p^g;

где p – основание используемой системы счисления.

g – количество разрядов в получаемых случайных числах.

Пример:

Пусть необходимо получить случайное число , равномерно распределенное в интервале (0;1).

Пусть λ (ядро) = 5167;

X₀ = 3729

M = 10⁴ = 10000;

Тогда λX_i = 19267743 и случ. число = 0,7743

на 2-м шаге X_i = 7743 , λX_i = 40008081, случ. число = 0,8081

и т.д…

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

Метод обратной функции и его использование для гененрирования непрерывных случайных величин

Предположим, нам необходимо генерировать случайную величину Х, являющуюся непрерывной и имеющую функцию распределения F – непрерывную строго возрастающую, когда 0 < F(x) < 1, из этого следует, что если x₁ < x₂ и 0 < F(x₁) < F(x₂) < 1, то F(x₁) < F(x­₂).

Примем, что F^-1 – это обратная функция F. Две функции y = f(x) и y = phi(x) называются взаимно обратными, если для каждой пары значений a,b, удовлетворяющих условию b = f(a), удовлетворяется также условие a = phi(b), а для каждой пары , удовлетворяющих условию a = phi(b), удовлетворяется также условие b = f(a).

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

Пример: y = x² и y = +-sqrt(x)

y = e^x и y = ln x

На первом шаге строится интегральная функция распределения F(x).

Т.к. F(x) изменяется в интервале от 0 до 1, полагают F(x) = R,

где R – случайная величина, равномерно распределенная в интервале (0,1).

Тогда: x = F^-1(R)

где x – случайная величина с функцией плотности распределения f(x),

F^-1‑ - функция, обратная по отношению к F.

Метод обратной функции и его использование для гененрирования дискретных случайных величин

Для дискретной величины X является функция распределения F(X) = P(X<=x) = ∑p(x_i) (если x_i<=x)

где p_i(x) является вероятностной мерой p(x_i) = P(X = x_i)

Допускается, что величина X может иметь только значения x₁,x₂,… для которых x₁<x₂<…

Тогда алгоритм будет иметь следующий вид:

1. Генерируем U ~ U(0,1)

2. Определяем положительное наименьшее число I, для которого U <= F(x_I) и возвращаем X = x_I .