Глава II. ПОЛУЧЕНИЕ И ПРЕОБРАЗОВАНИЕ СЛУЧАЙНЫХ ЧИСЕЛ

5. Случайные числа

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

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

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

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

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

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

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

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

Напомним свойства равномерного распределения.

Непрерывная случайная величина имеет равномерное распределение в интервале если ее функция плотности

а функция распределения

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

что бесчисленное множество возможных значений случайной величины заполняет непрерывно интервал Будем использовать вместо непрерывной совокупности равномерных случайных чисел интервала , дискретную совокупность случайных чисел того же интервала, имеющих вероятности Закон распределения такой совокупности носит название квазиравномерного закона распределения. Следует отметить, что при достаточно большом различие между равномерным и квазиравномерным распределением можно считать практичёски несущественным. На практике уже при равном 20, различие в случайных числах с этими распределениями не сказывается заметно на точности решения задач методом статистических испытаний.

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

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

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

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

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

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

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

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

выходным напряжением которое является случайной функцией. Фиксируя значения этого напряжения в определенные моменты времени получаем последовательность независимых случайных величин

Пользуясь значениями можем получать следующим образом:

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

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

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

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

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

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

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

Следует отметить, что программы для получения псевдослучайных чисел не всегда работают достаточно устойчиво и надежно. Во-первых, рекуррентный процесс может оборваться (выродиться), например, получившийся при очередном просчете нуль повлечет за собой нулевую последовательность. Кроме того, последовательность случайных чисел может оказаться периодической (ведь число различных чисел не более чем При использовании большого количества случайных чисел, полученных рекуррентным способом, по упомянутым здесь причинам величины статистических характеристик их могут существенно исказиться. Для ослабления влияния возмущающих факторов существует несколько способов, например, применение периодически работающих спаренных программ с различными алгоритмами, где случайное число, полученное с помощью одного из алгоритмов, является исходным для другого; если же обращаться к парной программе случайным образом, то это дает еще больший эффект. Полученные таким образом случайные числа требуют проверки на «случайность», на «близость» к заданному закону распределения, на отсутствие корреляции и т. д., после чего они пригодны к использованию.