Датчики случайных чисел

Для имитации случайных событий необходим некоторый эталон, т.е. то, с чем можно что-то сравнить. Известно, что наука существует там, где есть измерения. Отсутствие измерений приводит к схоластике, лженаукам. В мире существуют эталоны для измерения времени, расстояния, веса и прочее. Такой же эталон должен существовать и в ЭВМ для «измерения» вероятности случайного события. Начало созданию подобного эталона было положено в шестидесятых – семидесятых годах прошлого столетия. Создавались специальные устройства – датчики (генераторы) случайных чисел или случайных величин, авторы которых получали авторские свидетельства на эти устройства. Ученые издавали статьи, книги, посвященные этой проблеме. Однако существовало непреодолимое препятствие – нестабильность электронных элементов, на которых осуществлялась реализация датчиков случайных чисел. Из-за нестабильности эти датчики необходимо было постоянно настраивать.

Появление высокопроизводительной вычислительной техники и развитых языков программирования упростило задачу создания эталонов. Датчики или генераторы случайных чисел стали создавать программным путем. В библиотеках языков программирования присутствуют подпрограммы (процедуры) с названиями random, randomizir, randu и прочее, которые позволяют получать на ЭВМ псевдослучайные числа, квазиравновероятно распределенные в интервале [0, 1].

Строго говоря, для формирования случайных событий с различными функциями распределения в ЭВМ необходимо иметь, как эталон, совокупность случайных чисел с равномерным законом распределения. Эта совокупность случайных чисел будет эталоном, т.е. базовой последовательностью случайных чисел. На рис. 4.1 показан вид функции распределения случайных чисел, равномерно (равновероятно) распределенных в интервале [0, 1].

 

Рис. 4.1

 

Функция распределения вероятностей случайных чисел, равномерно распределенных в интервале [0, 1], имеет вид

(4.1)

Математическое ожидание (генеральное среднее) случайных чисел, равномерно распределенных в интервале [0, 1], будет равно M[х]=0,5, а дисперсия D[х]=1/12.

Однако применение возможностей ЭВМ не позволяет теоретически получить последовательность случайных чисел с равномерным распределением. Действительно, любое число в ЭВМ формируется в регистре. Если число разрядов регистра ЭВМ равно k, то число Х в десятеричной системе счисления будет сформировано согласно формуле

(4.2)

в которой коэффициенты a_iÎ{0, 1} составляют двоичный код a_k-1,a_k,…,a₂,a₁,a₀случайного десятеричного числа Х.

Десятеричное число Х будет случайным и будет иметь равномерное распределение, если коэффициенты a_i=0 с вероятностью р_i=0,5 или a_i=1 с вероятностью р_i=1-0,5. Тогда числа Х={i/(2^k-1)} принимают значения i/(2^k-1) (i=0,1,2,...,2^k-1) с постоянной вероятностью Р=1/2^k.

Но полученные при этих условиях случайные числа Х будут иметь не равномерное, а квазиравномерное равновероятностное распределение в интервале [0,1], вид которого показан на рис. 4.2, что связано с дискретностью чисел Х. Математическое ожидание и дисперсия для данного распределения определяются соотношениями:

(4.3)

. (4.4)

 

Рис. 4.2

 

Таким образом, математическое ожидание квазиравномерного равновероятностного распределения в интервале [0,1] M[х] точно совпадает с генеральным средним для равномерного распределения в интервале [0,1], а дисперсия при kॠасимптотически стремится к дисперсии для равномерного распределения, равной 1/12. Практически при k>15 обеспечивается требуемая точность в имитационных исследованиях.

В ЭВМ нет генератора случайных чисел a_i, принимающих значения либо 0, либо 1 с вероятностью Р=1/2, поэтому аппаратная реализация датчика не имеет смысла. Датчики случайных чисел разрабатывают в виде программ, поэтому случайные числа, получаемые на ЭВМ, не являются случайными. Эти числа формируются на основе детерминированных преобразований в виде алгоритмов, поэтому их называют псевдослучайными. Так как алгоритм представляет собой строгую последовательность действий, то последовательность, получаемых псевдослучайных, квазиравномерно распределенных в интервале [0,1] чисел, имеет период Р, например: Х₀, Х₁, Х₂, Х₃,...,Х_Р-2, Х_Р-1, Х_Р, Х₀, Х₁, Х₂, Х₃,...

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

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

а) аналитические;

б) методы перемешивания.

При использовании аналитических методов в псевдослучайной последовательности Х₀, Х₁, Х₂, …, Х_r-1очередное число Х_r получают с помощью некоторого выбранного рекуррентного соотношения j, аргументами которого являются одно или несколько предыдущих чисел последовательности, т.е. Х_r=j(Х_r-1, Х_r-2,..., Х₀).

Самым простым примером может служить метод вычетов, в котором для получения числа Х_i+1 используется следующее рекуррентное соотношение:

Х_i+1=bХ_i(mod M), (4.5)

где выражение bХ_i(mod M) означает остаток от деления произведения bХ_i на число M; Х_i+1 - очередное случайное число; Х_i - предыдущее случайное число; b - некоторая константа; M - число, определяющее значение получаемых случайных чисел.

Рассмотрим пример. Пусть очередное число Х_i+1 определяется по формуле

, (4.6)

где А и В заданные константы, ]Х_i+1[ - операция взятия мантиссы числа Х_i+1. На рис. 4.3 приведен алгоритм генератора псевдослучайных, квазиравномерно распределенных чисел в интервале [0,1].

 

Рис. 4.3

 

В блоке 1 алгоритма осуществляется задание начального такта моделирования Т=0, заданное число тактов моделирования (генерации) TZ, равное количеству чисел Х, которое должно быть получено от датчика. В блоках 2-6 вычисляется очередное число Х[T+1]. В блоке 8 проверяется условие генерации датчиком заданного числа чисел Х. Если условие Т£TZ выполняется, то наращивается в блоке 9 такт моделирования. Таким образом, генератор псевдослучайных, квазиравномерно распределенных чисел может быть реализован согласно заданной формуле (4.6).

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

На рис. 4.4 показан пример метода перемешивания.

Число Х_i вначале циклически сдвигается на три разряда влево (K=3), а затем полученное после этого сдвига число поразрядно суммируется по модулю два с начальным числом Х_i. Получаем двоичное число Х_i*.

Затем это число циклически сдвигается на два разряда вправо (L=2) и полученный результат суммируется поразрядно по модулю два с числом Х_i*. В результате получим последующее число псевдослучайной последовательности Х_i+1.

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

 

 

Рис. 4.4

 

Для того чтобы числа были распределены в интервале [0,1], необходимо провести соответствующее нормирование, например, считать, что получаемые числа это дробная часть.

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

В блоке 1 алгоритма осуществляется ввод начального такта моделирования Т=0, заданное число тактов моделирования (генерации) TZ, начального массива Х0[I] размерностью IM, значение IM, а также K - число сдвигов влево и L - число сдвигов вправо. В массиве Х0[I] записана начальная константа Х₀. В блоках 3-6 определяется массив ХK[I], полученный из массива Х0[I] в результате циклического сдвига его элементов на K разрядов влево.

Например, если IM=7, а K=3, то при I=0 (блок 4) ХK[3]=Х0[0] (блок 5), при I=1 ХK[4]=Х0[1], при I=2 ХK[5]=Х0[2], при I=3 ХK[6]=Х0[3], при I=4 ХK[0]=Х0[4], при I=5 ХK[1]=Х0[5], при I=6 ХK[2]=Х0[6]. Результатом операции (I+K)modIM будет остаток от деления числа I+K на число IM.

 

Рис. 4.5

Затем в блоках 7-10 алгоритма происходит поразрядное суммирование по модулю два элементов массивов ХK[I] и Х0[I]. В результате будет получен массив ХМ[I].

В блоках 11-14 определяется массив ХL[I], полученный из массива ХM[I] в результате циклического сдвига его элементов на L разрядов вправо. Например, при L=2, при I=0 (блок 12) ХL[0]=ХM[2] (блок 13), при I=1 ХL[1]=ХM[3], при I=2 ХL[2]=ХM[4], при I=3 ХL[3]=ХM[5], при I=4 ХL[4]=ХM[6], при I=5 ХL[5]=ХM[0], при I=6 ХL[6]=ХM[1].

Затем в блоках 15-18 алгоритма происходит поразрядное суммирование по модулю два элементов массивов ХМ[I] и ХL[I]. В результате будет получен массив ХT[I], элементы которого представляют собой двоичный код мантиссы искомого псевдослучайного, квазиравномерно распреде-ленного в интервале [0,1] числа. В блоке 19 элементы массива ХT[I] присваиваются элементам массива Х0[I]. В блоке 21 выполняется условие генерации датчиком заданного числа чисел Х.

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