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

Случайные числа - это случайные величины, которые равномерно распределены на интервале [0, 1] и (стохастически) независимы. Случайные, или переменные, величины - это вероятностные переменные; они введены по контрасту с переменными, значения которых можно установить заранее. Случайные числа (независимые)- равномерные случайные величины. Случайные числа имеют следующие две характеристики:

1. Если r_i (i=1, 2, 3,…) есть случайные числа, то их кумулятивное распределение, обозначим его F, удовлетворяет уравнению (21) для всех i

(см. рис. 28).

F(r_i)=P(r<r_i)

=r_i для 0 £ r_i £ 1,

=0 для r_i<0,

=1 для r_i>1. (21)

2. Теоретически случайные числа должны быть непрерывными переменными с функцией плотности f, определяемой следующим выражением:

f(r_i)=1 для 0 £ r_i £ 1,

=0 для всех других значений. (22)

Независимость случайных чисел имеет своим следствием тот факт, что знание r₁, r₂,…,r _i-1 не дает нам никакой информации об r_i.

Случайные числа вырабатываются в машине при помощи чисто детерминированных рекурсивных формул. При этом получаются псевдослучайные числа, их статистические свойства совпадают со статистическими свойствами чисел, генерируемых идеальным случайным механизмом, вырабатывающим числа из интервала [0, 1], независимые и с одинаковой вероятностью. К идеальному генератору применяются следующие требования: полученные с его помощью последовательности должны состоять из

1) равномерно распределенных, 2) статистически независимых, 3) воспроизводимых, 4) неповторяющихся чисел. Кроме этого генератор должен 5) работать быстро и 6) занимать мало места в памяти машины. Разработаны два основных конгруэнтных метода построения случайных чисел: мультипликативный и смешанный.

Все конгруэнтные методы основаны на рекуррентной формуле

n _i+1=(ln_i+m) mod m, (23)

где n_i, m, l, m - целые положительные числа. Запишем первые члены этой последовательности при i=1, 2, 3

n₁=(ln₀+m ) mod m

n₂=ln₁+m =(l²n₀+(l +1)m )mod m

n₃=(l³n₀+(l²+l +1)m =( l³n₀+m (l³-1)/(l -1))mod m (24)

n_i=(lⁱn₀+m (lⁱ -1)/(l -1))mod m

Если дано начальное значение n₀, множитель l и аддитивная константа m, то формула определяет последовательность целых чисел {n₁, n₂,…n_i,…}, составленную из остатков деления на m членов последовательности {(lⁱn₀+m (lⁱ -1)/(l -1))} для любых i>=1, n_i<=m. По целым числам последовательности {n_i} можно построить последовательность {r_i}={n_i/m} рациональных чисел из интервала [0,1]. Обозначим через h - наименьшее положительное число, при котором n_h=n₀ mod m . Число h называется периодом последовательности {n_i}. Величина h существенна, так как выполнение равенства n_h=n₀ mod m влечет за собой n_h₊₁=n₁, n_h₊₂=n₂ и т.д. Таким образом, последовательность {n_i} будет периодической, т.е. значения ее членов будут повторяться через h номеров. Необходимо выбрать такие n₀, l, m и m, чтобы h был максимальным. Рассмотрим алгоритм для случая двоичных машин. В этом случае m=2^b, где b –число двоичных цифр в машинном слове. Максимальным периодом такой последовательности будет 2 ^b-2. Алгоритм построения последовательности с максимальным периодом:

1. Выбрать в качестве параметра n₀ произвольное нечетное число.

2. Вычислить l по формуле l=8*t(+-)3, где t-любое целое положительное число.

3. Вычислить произведение ln₀. Оно содержит не более 2b значащих разрядов. Взять b младших разрядов в качестве первого члена последовательности n₁, остальные отбросить.

4. Вычислить дробь из интервала [0, 1] по формуле r₁=n₁/2^b.

5. Вычислить очередное псевдослучайное число n _i+1 как b правых разрядов произведения ln_i и вернуться к пункту 4.

Рассмотрим пример для b=4. Процедура должна определить 4 разных числа (h=2 ^4-2=4).

1. Положим n₀=7, в двоичной записи n₀=0111.

2. При t=1 коэффициент l можно взять равным 11 или 5, выберем 5 в двоичной записи t=0101.

3. ln₀=5*7=(0101)*(0111)=35=(00100011), выбираем правые 4 разряда n₁=0011 и r₁=3/16=0.1875

4. ln₁=(0101)*(0011)=00001111,отсюда n₂=1111 и r₂=15/16=0.9375

5. ln₂=(0101)*(1111)=01001011,отсюда n₃=1011 и r₃=11/16=0.6875

6. ln₃=(0101)*(1011)=00110111,отсюда n₄=0111 и r₄=7/16=0.4375

Различные наборы параметров изучались на предмет идеального генератора и для 32-x разрядных машин хорошие свойства показали генераторы с l=5¹³=1220703125, n₀=5¹³ и m=2³¹-1. Обозначая n₀=N₁, n=N, r=R, программу генерации случайных чисел можно записать в виде

5 INPUT “ ВВЕДИТЕ N0”;N1

10 N=1220703125*N1

20 IF N>=0 THEN 40

30 N=N+214783647+1

40 N1=N

50 R=N

60 R=R*0.4656613E-9:PRINT R

Число R будет искомым числом, на вход программы подается исходное число n₀=5¹³. В языке GWbasic, к сожалению, эта программа работать правильно не будет, так как максимальные целые числа должны быть в диапазоне –32768, +32767. Хорошими параметрами показали себя также числа l=7⁵=16807 и m=2³¹-1.

Мультипликативный метод является частным случаем предыдущего при l=0, опирается на формулу

n_i₊₁=ln_i mod m (25)

и задает последовательность неотрицательных целых чисел {n_i}, не превосходящих m. Если взять m равным наибольшему простому числу, которое меньше чем 2^b и l=Öm , то максимальный период будет m-1. Для получения случайных чисел предлагается такой алгоритм:

1. Берем число x₀содержащее < 9 знаков.

2. Умножаем его на l с числом знаков >5.

3. Умножаем результат на 1/m.

4. Берем дробную часть результата 3.

5. Исключить из числа, полученного на шаге 4 запятую и использовать его в качестве х умножаемого на l в шаге 2.

6. Повторять шаги 2-5 до получения нужного количества случайных чисел.

В работе Теннат-Смита [6] была предложена аналогичная формула

R _n+1=M*R_n-D*INT(M*R_n/D), (26)

которая при соответствующем подборе целых чисел M и D вырабатывает случайные целые числа в интервале от 1 до D-1. Отличную пару представляют числа M=8192 и D=67101323. Число D должно быть больше M*(M-1) и меньше M² .Числа M=10 и D=97 можно взять для проверки работы нижеследующего алгоритма, который также трудно реализуем на Basic из-за ограниченного диапазона целых чисел.

10 M=8192:D=67101323

20 B=M*M-D

30 INPUT”ВВЕДИТЕ ДЛИНУ СЕРИИ”;N

40 INPUT”ВВЕДИТЕ НАЧАЛЬНОЕ ЦЕЛОЕ ЧИСЛО (ОТ 1 ДО D-1);S

50 R=S

60 FOR I=1 TO N

70 C=INT(R/M)

80 R=B*C+M*(R-M*C)

90 IF R>D THEN R=R-D

100 PRINT R,R/D

110 NEXT

Модели задачи, использующие генераторы случайных чисел