6Simulation systems Лекция 20 Случайные числа (1014328), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

аX_i=qm+ X_i+1 0  X_i+1  m-1 (a)

3) так как X_i+1 - число между 0 и m, то нужно его еще разделить на m, чтобы получить число между 0 и 1:

r_i+1=X_i+1/ m (б)

Соотношение (а) записывается обычно в виде:

X_i+1= аX_i(mod m) (в)

При этом говорят, что числа аX_i и X_i+1 сравнимы по модулю m, т.е. они являются равноотстоящими при делении на m.

Формулу (в) называют сравнением по модулю, а остаток X_i+1 - наименьшим положительным вычетом по модулю m.

Этим объясняются оба названия алгоритма - метод мультипликативного сравнения или метод вычетов.

Положим, что а=7, m=5 и в качестве исходного числа выбрано значение Xo=3.

Получение равномерно распределенной последовательности можно представить в следующем виде:

Начиная с i=4 числа повторяются, т.к. Х₄ = Х_о. Итак, должно быть задано какое-то исходное число Х_о, чтобы можно было выполнить рекурсию. Это число однозначно определяет всю последовательность случайных чисел, так как речь идет о детерминированном способе вычислений. По этой причине число Х_о называют также начальным или “зародышем” последовательности случайных чисел. Как видно из примера, нельзя считать, что любой произвольный выбор исходного числа Х_о, коэффициента а и модуля m даст по методу мультипликативного сравнения числовую последовательность, которая могла бы рассматриваться как случайная.

Последовательности случайных чисел, полученные методом мультипликативного сравнения, периодически повторяются. Это связано с тем, что числа Х_i могут принимать только значения 0,1,2,..., m-1.

Итак, самое большее через m-1 шагов уже один раз полученное число должно появиться опять, а за ним повторяется и вся последовательность. Таким образом, длина периода при модуле m не может превышать m-1.

В приведенном примере длина периода составляет m-1=4.Нетрудно убедиться, что она может быть и меньше m-1, например, если выбрать а=9, m=5, Хо=1.

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

Пусть а=6, m=8, Хо=3, тогда

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

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

Рассмотрим способ, состоящий из двух этапов:

а) получение последовательности случайных чисел с помощью любого физического генератора;

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

Сущность этого способа заключается в том, что вначале получают две последовательности случайных чисел, одну - длиной n₁, другую - длиной n₂ в двоичной либо десятичной системе счисления. Из каждой образуют две бесконечные периодические последовательности:

первая - с периодом U₁ элементов, вторая - с периодом из U₂ элементов. Обозначим через а_ij - j-ый член (j=1,2,3...) i-ой последовательности (i=1,2) и через b_j - j-ый член новой последовательности, образующейся по формуле: b_j=(a_{1 j}+a_{2 j})(mod m)

Положим m=10, n₁=3, n₂=4. Пусть с помощью рулетки или любого другого физического датчика получены последовательности (5,3,2) и (1,6,2,8) По приведенной формуле получим:

а_1j 5 3 2 5 3 2 5 3 2 5 3 2 5 3 2 .......

а_2j 1 6 2 8 1 6 2 8 1 6 2 8 1 6 2 8 .......

b _j 6 9 4 3 4 8 7 1 3 1 5 0 6 9 4 ...

Если первоначальные последовательности {а_{1 j} } j=1,...,n₁ и {а_{2 j} } j=1,..., n₂ не периодические, а n₁ и n₂ - простые числа, т.е. их наибольший общий делитель равен 1, то результирующая последовательность b_j} - периодическая с периодом n₁n₂ . Эту процедуру можно обобщить путем увеличения числа первоначальных последовательностей. Пусть число этих последовательностей r и n₁ , n₂ , ..., n_r - количество цифр в этих последовательностях.

Предположим, что числа n₁ , n₂ , ..., n_r - простые, и ни одна из первоначальных последовательностей не является периодической. Тогда последовательность b_j=

является периодической с периодом n₁ , n₂ , ...,n_r .

При моделировании процессов желательно, чтобы длина периода была больше используемого ряда чисел. Как видно из примеров, для достижения нужной длины периода важен не только модуль m, но также множитель а и начальное число Х_о.

Подбор этих чисел осуществляется с помощью теоретико-числовых приемов (Кнут Д. Искусство программирования для ЭВМ т.2 - М: Мир, 1977).

В условиях ограниченной памяти ЭВМ иногда следует выбирать модуль m = 2¹⁵. В результате максимальная длина периода 2¹³=8192.

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

Модуль m может быть выбран достаточно большим. Длина слова компьютера определяет наибольшее целое число. При длине слова “b” бит один бит закрепляется за целым числом так, что наибольшее предлагаемое число равно 2^b-1. Наибольший возможный модуль таким образом, m = 2^b-1.

При использовании пакета прикладных программ SSP в подпрограмме RAND выбирается m = 2³¹ при длине слова 32 байта.

Если модуль имеет вид 2^S, то в теории чисел доказывается, что максимально возможная длина периода последовательности чисел равна

2^S-2. При этом, если множитель а отличается на 3 или 5 от числа кратного 8, и начальное число Х_о является нечетным, то период вырабатываемой последовательности достигает длины 2^S-2.

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

a_n+1={Ma_n} a_o=2^-m

где М - достаточно большое число, фигурные скобки означают дробную часть, m - число двоичных разрядов в мантиссе ячейки ЭВМ

1. Процедура RAND на фортране (среднее) время получения одного числа на ЕС-1033 - 100 мкс).

FUNCTION RAND (IN)

IN=IN*331804469 (=331804464+5)

IF(IN)1,1,2

1 IN=IN+2147483647+1 (2147483647 = 2³¹)

2 RAND=IN  0.465661 E-09 (0.465661 E-09 = 1 / 2³¹)

RETURN

END

2. Процедура получения псевдослучайных чисел на языке PL-1.

Обращение к процедуре в программе U=RAND(IN) описано как BIN FIXED (31). Перед первым обращением IN присваивается некоторое целое значение, сравнимое с 1 по mod 4. Среднее время на 1 число - 2500 мкс (ЕС-1033).

RAND: PROC(IN) RETURNS (BIN FLOAT)

DCL IN BIN FIXED(31)

DCL FLTBIN FLOAT INIT(0,46566129E-9) STATIC;

DCL MULT BIN FIXED(31) INIT(331804469)STATIC;

(NOFOFL): IN=MULT-IN

RETURN (IN  FLT);

END RUND;

(С.М.Ефремов, Г.А.Михайлов “Статистическое моделирование” М.Наука, 1982).

9.4.2 Получение случайных чисел с заданным законом распределения

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

Такими вероятностными объектами, в первую очередь, являются:

а) случайные события, наступающие с заданной вероятностью,

б) случайные величины с заданным законом распределения Рi=Pi(x) и некоторые виды случайных векторов и процессов.

Рассмотрим, как можно моделировать с помощью равномерно распределенных случайных чисел случайные события, наступающие с заданной вероятностью. Эту процедуру называют еще “реализацией жребия”. Пусть событие А наступает с вероятностью Р, тогда процедура моделирования этого события с помощью равномерно распределенных в интервале (0,1) случайных чисел выглядит следующим образом:

Характеристики

Список файлов лекций