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

 

>> см. Методические указания «Генераторы случайных величин»

 

Определение случайных чисел: Случайные числа являются реализацией последовательности взаимно независимых и одинаково распределенных случайных величин с произвольным законом распределения F. Если случайные числа имеют дискретное равномерное распределение на множестве чисел 0,1, …, 9, говорят о равномерно распределенных случайных цифрах. Группировка по s смежным случайным цифрам дает s -значные случайные числа, являющиеся реализациями случайной величины, которая может принимать соответствующие целочисленные значения с одинаковыми вероятностями 0.1^S. Если каждую группировку из s цифр разделить на 10^S получится реализация случайной величины, принимающей s-разрядные значения в диапазоне        [0.. 1-10^-S]  с равными вероятностями 0.1^S. Образованные таким образом случайные числа имеют распределение, близкое к непрерывному равномерному на интервале [0, 1).

Реализации случайных чисел программным путем получают с помощью генераторов псевдослучайных последовательностей. Алгоритмы функционирования ГПП основаны на рекуррентных соотношениях вида:

x_n+1=F(x_n, x_n-1, x_n-2,…, x_n-k, ), n = k, k+1, k+2,…; k>1, где                                    (2)

n – порядковый номер члена последовательности случайных чисел,

   – вектор параметров алгоритма,

F – детерминированная функция.

Наиболее широко используется ГПП со связью на один шаг:

x_n+1=F(x_n ,)                                                                                                               (3)

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

, где                                                                (4)

x₀ – начальное значение, x₀ > 0;

a_i – множители, целые неотрицательные числа;

c – приращение, c >= 0;

M – модуль, M > 0.

Генератор выдает целые неотрицательные числа в диапазоне [0, M-1].

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

r_n+1=x_n+1/M                                                                                                                  (5)

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

 

Свойства случайных чисел, вырабатываемых ГПП

 

1. Повторяемость, обусловленная конечностью разрядной сетки.

2. Вырождение, приводящее к тому, что при некоторых значения параметров ГПП числа, вырабатываемые ими, не похожи на случайные. Вырождение приводит к тому, что мощность ГПП не превышает M-1.

 

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

 

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

 

>> см. Методические указания «Генераторы случайных величин»

 

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