Получение ряда равномерно распределенных псевдослучайных чисел с использованием ЭВМ

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

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

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

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

 

2. Получение на ЭВМ равномерно распределенных псевдослучайных чисел.

 

При моделировании систем на ЭВМ  программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. Таким базовым процессом является последовательность чисел {х_i} = х₀, х₁, ¼, х_N, представляющих собой реализации независимых, равномерно  распределенных  на  интервале  ( 0, 1 )  случайных  величин  { e_i } = e₀, e₁, ¼, e_N. Но  на  ЭВМ невозможно  получить  идеальную последовательность  случайных  чисел  потому, что  на  ней  можно  оперировать  только  с  конечным  множеством  чисел. Кроме того, для получения  значений  х  случайной  величины  e  используются  формулы ( алгоритмы ). Поэтому такие последовательности, являющиеся  по  своей  сути  детерминированными, называются  псевдослучайными.

Наибольшее  применение  в  практике  моделирования  на  ЭВМ  для  генерации  последовательностей  псевдослучайных  чисел  находят  алгоритмы  вида

х_i+1 = F (хi),

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

 

1. Метод соединенных квадратов.

Пусть  имеется  2n-разрядное число, меньшее 1

х_i  = 0, a₁  a₂  ¼  a_2n.

Возведем  его  в  квадрат

х_i² = 0, b₁  b₂  ¼  b_4n,

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

х_i+1 = 0, b_n+1  b_n+2  ¼  b_3n.

        Этому  методу  соответствует  рекуррентное  соотношение               

х_i+1 = D [ 10^-2n Ц [ 10³ⁿ х_i² ] ],

 где  D [ × ]  и Ц [ × ]  означают  соответственно  дробную и целую часть числа в квадратных  скобках.

Недостаток  метода - наличие  корреляции  между  числами  последовательности, а  в  ряде  случаев  случайность  вообще  может  отсутствовать. Кроме  того, при  не-которых   i^*  может   наблюдаться   вырождение   последовательности,  т.е.  х_i = 0   при     

i  ³ i^*.

1. Метод середины произведений.

Метод  является  модификацией  метода серединных  квадратов  и  состоит  в том, что  два  2n-значных  числа  перемножаются  и  средние  2n  цифр  этого произведения  принимаются в качестве  следующего  числа последовательности. Таким  образом, если         

х_i-1 = 0,  a₁  a₂  ¼  a_2n,

х_i = 0, b₁  b₂  ¼  b_2n,

то  для  получения  числа  х_i+1  необходимо  перемножить  х_i-1  и х_i

х_i-1 × х_i = 0, c₁  c₂  ¼  c_4n,

а  затем  отобрать  средние  2n  цифр  этого произведения

х_i+1 = 0, c_n+1  c_n+2  ¼  c_3n.

Данному  методу  соответствует  рекуррентное  соотношение

х_i+1 = D [ 10^-2n  Ц [ 10³ⁿ х_i × х_i-1 ] ]

при  заданных  двух  начальных  числах  х₀  и х₁.

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

1. Мультипликативный метод.

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

                                                       Х_i = lХ_i + m (mod M),                                             

где  Х_i, l, m, M - неотрицательные целые числа.

Раскрывая  получим

                                          Х_i = lⁱ Х₀ + (lⁱ - 1) m / (l - 1)(mod M).                             

Если  задано  начальное  значение  Х₀, множитель l  и аддитивная  константа  m, то  однозначно  определяет  последовательность  целых чисел  { Х_i }, составленную  из  остатков  от  деления на  М, членов  последовательности

 { lⁱ×Х₀ + m ( lⁱ - 1 ) / ( l - 1 )}.     

Таким  образом, для  любого  i ³ 1  справедливо  неравенство  Х_i < M. По  целым числам  последовательности  { Х_i }  можно построить последовательность          { х_i } = { Х_i / M }  рациональных  чисел из  единичного  интервала  ( 0, 1 ).

Мультипликативный  метод  задает  последовательность  неотрицательных  целых  чисел  {Х_i}, не  превосходящих М, по  формуле    

                                                         Х_i+1= l Х_i (mod M),                                               

т.е.  это  частный  случай  при  m = 0.

Для  машинной  реализации  наиболее  удобна  версия  М = p^g,  где p - число цифр  в системе счисления, принятой  в ЭВМ, а g - число бит в машинном  слове.

Алгоритм  построения  последовательности  для  двоичной  машины  М = 2^g  сводится  к  выполнению  следующих  операций:

1. выбрать  в  качестве  Х₀  произвольное  нечетное  число; 
2. вычислить  коэффициент  l = 8t ± 3, где t - любое целое положительное  число;
3. найти  произведение  l Х₀, содержащее  не  более 2g  значащих  разрядов;
4. взять  g  младших разрядов  в качестве  первого  числа  последовательности  Х₁, а остальные отбросить;
5. определить  дробь  х₁ = Х₁ / 2^g  из  интервала ( 0, 1 );           
6. присвоить  Х₀ = Х₁;
7. вернуться  к  пункту  3.

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

1. Методы проверки качества псевдослучайных чисел с равномерным законом распределения.

Методы проверки  качества  псевдослучайных  чисел  делятся  на  три  группы:

1. проверки   ²случайности²  последовательности  псевдослучайных чисел;
2.   проверки  равномерности закона  распределения;
3.   проверки  независимости последовательности.

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

Пусть  имеется  h - случайная величина, о законе  распределения которой  выдвигается  некоторая  гипотеза, Х - множество  возможных  значений  h. Разобьем  Х на  m  попарно непересекающихся  множеств  Х₁, Х₂, ¼ ,Х_m, таких, что

P { hÎХ_j } = p_j > 0  при j = 1, 2, ¼, m,

p₁ + p₂ + ¼ p_m = P { hÎХ } = 1.

Выберем  N  независимых значений  h₁, h₂, ¼ ,h_N  и  обозначим  через количество  значений  hÎХ_j. Очевидно,  что математическое  ожидание  равно Np_j, т.е.  М [ ] = Np_j. 

В  качестве  меры  отклонения  всех

от  Np_j выбирается  величина

При  достаточно  большом  N  величина хорошо  подчиняется закону  распределения с ( m - 1)  степенью  свободы:

P {

< } ,

где - плотность распределения с  ( m - 1)  степенью  свободы.

С  помощью  формулы  при  заданном  уровне  значимости b ( обычно b = 0.95 )  можно определить  нижнюю и верхнюю границы области возможного  принятия  гипотезы  ( доверительного  интервала ). Для  этого  нужно  решить  соответственно  следующие  уравнения:

P {

> } = =  b,

P {

> } = =  g,

где  g = 1 - b, r = m - 1.

 

Список используемых источников:

1. Бобнев М.П. Генерирование случайных сигналов. – Изд. 2-е, перераб. И доп. – М.: Энергия, 1971. – 240 с.
2. Браммер Ю.А., Пащук И.Н., Импульсные и цифровые устройства, 2005.
3. Бруслова О.В. Моделирование систем: учебно-методическое пособие/ Тюмень: ТюмГНГУ, 2012.-60 с
4. Бусленко Н. П. Моделирование сложных систем. - М.: Наука, 1978
5. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. – М.: Наука, 1988. – 480 с.
6. Ермаков С.М., Михайлов Г.А., Статистическое моделирование. М. Наука. 1982. 294 с.
7. Манджалагидзе П.В., Морозов А.М. Формирование случайных цифр в произвольной системе счисления // Труды Вычислительного центра АН Груз. СССР. Т.21. № 2. 1981. С. 74-104.
8. Фомин С.В. Системы счисления. М. Наука. 1987. 40 с.
9. www.electronica.ru
10. www.wikipedia.ru
11. www.google.com