Столярчук В.А. “Системы моделирования”. Материалы к лекциям. Лекция №20

Лекция № 20

9.4. Получение и преобразование случайных чисел.

Оглавление

9.4.1. Получение равномерно-распределенных случайных чисел. 1

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

9.4.3 Приближенные способы преобразования случайных чисел 17

9.4.4 Моделирование случайных векторов 19

9.4.1. Получение равномерно-распределенных случайных чисел.

Ранее уже упоминалось, что распространены два основных принципа получения случайных чисел. Аппаратурный - когда случайные числа вырабатываются специальной электронной приставкой (датчиком случайных чисел), устанавливаемой на ЭВМ. Реализация этого принципа почти не требует дополнительных операций машины, кроме операции обращения к датчику.

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

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

К исходному распределению предъявляются следующие требования: простота получения чисел с помощью электронных приставок или непосредственно на ЭВМ, а также удобство преобразования в распределение с заданным законом распределения.

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

Напомним свойства равномерного распределения. Непрерывная случайная величина  имеет равномерное распределение в интервале (a,b), если ее

функция плотности: f(x)=

, а функция распределения F(x) =

Это распределение и нужно получить на ЭВМ.

(Для справки: нормальный закон: , где - среднее значение случайной величины,  - дисперсия случайной величины )

Но оказывается, что получить точно такое распределение на ЭВМ невозможно в силу хотя бы того обстоятельства, что ЭВМ, оперирующая с n- разрядными двоичными числами, может формировать не более,

чем 2ⁿ различных чисел, а при равномерном распределении предполагается, что бесчисленное множество возможных значений случайной величины  заполняет непрерывно интервал (a,b). Будем использовать вместо непрерывной совокупности равномерных случайных чисел интервала [0,1], дискретную совокупность 2ⁿ случайных чисел того же интервала, имеющих вероятности 2^-n. Закон распределения такой совокупности носит название квазиравномерного закона распределения. Следует отметить, что при достаточно большом n различие между равномерным и квазиравномерным распределением можно считать практически несущественным. На практике уже при n=20 различие в случайных числах с этими распределениями не сказывается заметно на точности решения задач методом статистических испытаний.

Раcсмотрим известные принципы получения последовательности квазиравномерных случайных чисел:

1) генерирование случайных чисел специальной электронной приставкой путем моделирования некоторых случайных процессов;

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

Идея генерирования случайных чисел, подчиненных квазиравномерному закону распределения на отрезке [0,1] предполагаем следующее.

Для получения n-значного двоичного случайного числа моделируется последовательность независимых случайных величин Zi, принимающих значения 0 или 1 с равной вероятностью. Полученная последовательность нулей и единиц представляет собой случайное двоичное число, квазиравномерно распределенное на отрезке [0,1]. Аппаратурные методы получения квазиравномерного распределения различаются только способами получения последовательности независимых случайных величин Zi.

Один из возможных способов основан на подсчете количества радиоактивных частиц за определенный промежуток времени t. Если число частиц за время t - четное, Zi присваивается значение 1, если нечетное - 0.

Другой способ получения случайных величин Zi использует шумовой эффект электронной лампы. Собственный шум электронной лампы выражается некоторым выходным напряжением U(t) , которое является случайной функцией. Фиксируя значения этого напряжения в определенные моменты времени t_i , получаем последовательность независимых случайных величин U(t_i) . Пользуясь U(t_i) , можем получать Zi следующим образом:

где a - выбирается с таким расчетом,

чтобы: P(Zi=1)=P(Zi=0)=P[U(t_i) a]=0,5

Кроме недостатков аппаратурного принципа получения случайных чисел вообще, изложенные здесь способы имеют свои специфические недостатки. Способ первый предполагает наличие незатухающего или малозатухающего источника радиоактивных частиц, а второй - стационарного режима подачи напряжения, позволяющего сохранять постоянную величину P[U(t_i) ] , в противном случае снижается качество случайных чисел. Кроме того, аппаратурный принцип не позволяет использовать для контроля работы программы так называемый метод двойного просчета, сущность которого заключается в двойной реализации разбитого на части алгоритма и последующего сравнения результатов. Очевидно, что при повторном генерировании не удается получить те же случайные числа.

Равномерно распределенные случайные числа могут выбираться из специальных таблиц (например, из таблицы, изданной Рэнд Корпорейшн).

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

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

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

Один из наиболее простых способов получения псевдослучайных равномерных чисел, известный под названием способа средних квадратов, принадлежит Нейману. Пусть имеется некоторое n-разрядное число в интервале [0,1]. Возведем его в квадрат. Очевидно, что при этом получим уже 2n-разрядное число. Выделим средние n разрядов этого числа. Полученное таким образом новое n - разрядное число опять возведем в квадрат и т.д.

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

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

Опишем еще один алгоритм:

U_i=kU_i-1 ^, где k=8t  3, t - целое число, U_o - нечетное число,

U_i - последняя значащая часть числа U_i’.

Например, положим: U_o=0,37843, t=5, k=8t-3=37

U₁’=kU_o=37 0,37843=14,00191.

Беря последнюю значащую часть вычисленной величины, получаем случайное число U₁=0,00191.

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

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

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

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

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

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

При использовании этого критерия берется N случайных чисел и подсчитывается m чисел, заключенных между 0,2113 и 0,7887, т.е. располагающихся в пределах  (дисперсия).

Если отношение  0,5774, то принимается, что случайные величины распределены приблизительно равномерно.

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

и

Как уже говорилось, подавляющее число способов получения случайных последовательностей основано на рекуррентных соотношениях. Рассмотрим один из наиболее часто применяемых в программах на вычислительных центрах. Он предложен Д.Лемером в 1951г. и называется методом мультипликативного сравнения или методом вычетов.

Способ заключается в получении равномерно распределенной последовательности на интервале [0,1). Отдельные значения этой последовательности r₁, r₂, ... рассматриваются как выборка из реализаций случайных переменных R₁, R₂, ... , являющихся взаимно независимыми и распределенными равномерно на интервале [0,1). Для проверки выполнения этого условия к полученным последовательностям применяют различные статистические критерии.

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

1) число X_i известно из предыдущего шага. Вычисляется произведение аX_i;

2) число аX_i делится на m. Получается целое число q и целочисленный остаток X_i+1, что можно представить в виде: