Псевдослучайные последовательности и процедуры их машинной генерации

ПЛАН ЗАНЯТИЯ:
Эталон генератора случайных чисел.
Непрерывное распределение случайных чисел.
Дискретное распределение случайных чисел.
Требования к генератору случайных чисел.
Основные способы генерации случайных чисел:
аппаратный (физический);
табличный (файловый);
алгоритмический (программный).
Алгоритмические методы:
метод серединных квадратов;
метод серединных произведений;
метод перемешивания;
линейный конгруэнтный метод.
Приближенные способы преобразования случайных чисел.
Универсальный способ преобразования случайных чисел.
Проверка качества работы генератора случайных чисел.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 5

ЭТАЛОН ГЕНЕРАТОРА СЛУЧАЙНЫХ ЧИСЕЛ
При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий
Результаты статистического моделирования существенно за­висят от качества исходных (базовых) последовательностей случай­ных чисел
За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0; 1).
Непрерывная случайная величина ξ имеет равномерное рас­пределение в интервале (а, b), если ее функция плотности (а) и функция распределения (б) примет вид :
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

НЕПРЕРЫВНОЕ РАСПРЕДЕЛЕНИЕ СЛУЧАЙНЫХ ЧИСЕЛ
Числовые характеристики случайной величины, принимающей значения х— это математическое ожидание, дисперсия и среднее квадратическое отклонение соответственно:
При моделировании систем на со случайными числами из интервала (0, 1), где границы интервала соответственно a=0 и b=1, частным случаем равномерного распределения является функция плотности и функция распределения, соответственно имеющие вид:
Такое распределение имеет математическое ожидание М [ξ] = 1/2 и дисперсию D[ξ] = 1/12.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ДИСКРЕТНОЕ РАСПРЕДЕЛЕНИЕ СЛУЧАЙНЫХ ЧИСЕЛ
Получить такое распределение на цифровой ЭВМ невозможно, так как машина оперирует с n-разрядными числами. На ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2n случайных чисел того же интервала.
Закон распределения такой дискретной последовательности называют квазиравномерным распределением.
Случайная величина ξ, имеющая квазиравномерное распределе­ние
в интервале (0, 1), принимает значения с вероят­ностями , .
Математическое ожидание и дисперсия квазиравномерной слу­чайной величины соответственно имеют вид
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ТРЕБОВАНИЯ К ГЕНЕРАТОРУ СЛУЧАЙНЫХ ЧИСЕЛ
Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны:
состоять из квазиравномерно распределенных чисел;
содержать статистически независимые числа;
быть воспроизводимыми;
иметь неповторяющиеся числа (серии, последовательности);
получаться с минимальными затратами машинного времени;
занимать минимальный объем машинной памяти.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ОСНОВНЫЕ СПОСОБЫ ГЕНЕРАЦИИ СЛУЧАЙНЫХ ЧИСЕЛ
На практике используются три основных способа генерации случайных чисел:
аппаратный (физический);
табличный (файловый);
алгоритмический (программный).
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

Генерация случайных чис­ел вырабатываются специальной электронной приставкой — гене­ратором (датчиком) случайных чисел,— служащей в качестве одно­го из внешних устройств ЭВМ
Реализация этого способа генерации не требует дополнительных вычислительных опе­раций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику).
В основе лежит какой-либо физический эффект, чаще всего используются:
шумы в электронных и полупроводнико­вых приборах;
явления распада радиоактивных элементов;
механические устройства;
и т. д.
Достоинства способа:
запас чисел не ограничен;
расходуется мало операций;
не занимается место в памяти.
АППАРАТНЫЙ СПОСОБ ГЕНЕРАЦИИ ЧИСЕЛ
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6
Недостатки:
требуется периодическая проверка;
нельзя воспроизводить последовательности;
используется специальное устройство;
необходимы меры по обеспечению стабильности.

Рис. Схема аппаратного метода генерации случайных чисел
Рис. Диаграмма получения случайных чисел аппаратным методом
АППАРАТНЫЙ СПОСОБ ГЕНЕРАЦИИ ЧИСЕЛ
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ТАБЛИЧНЫЙ СПОСОБ ГЕНЕРАЦИИ ЧИСЕЛ
Случайные числа, представленные в виде таблицы (содержащей проверенные некоррелированные, то есть никак не зависящие друг от друга, цифры), помещаются в память ЭВМ.
Этот способ получения случайных чисел обычно используют при сравнительно небольшом объеме таблицы и файла чисел.
Пример: Обходя таблицу слева направо сверху вниз, можно получать равномерно распределенные от 0 до 1 случайные числа с нужным числом знаков после запятой (в примере используется для каждого числа по три знака). Так как цифры в таблице не зависят друг от друга, то таблицу можно обходить разными способами, например, сверху вниз, или справа налево, или, скажем, можно выбирать цифры, находящиеся на четных позициях.
Достоинства:
дает действительно случайные числа;
требуется однократная проверка;
можно воспроизводить последовательности.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6
Недостатки:
запас чисел ограничен;
много места в ОЗУ;
необходимо время для обращения к памяти
большие трудности порождения и проверки такого рода таблиц

АЛГОРИТМИЧЕСКИЙ СПОСОБ ГЕНЕРАЦИИ ЧИСЕЛ
Способ получения последовательности случайных чисел основанный на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ.
Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделирова­нии системы на ЭВМ.
Числа, генерируемые с помощью этих ГСЧ, всегда являются псевдослучайными (или квазислучайными), то есть каждое последующее сгенерированное число зависит от предыдущего:
ri + 1 = f(ri).
Последовательности, составленные из таких чисел, образуют петли, то есть обязательно существует цикл, повторяющийся бесконечное число раз. Повторяющиеся циклы называются периодами.
Достоинства:
высокое быстродействие;
требуется однократная проверка;
многократная воспроизводимость последовательности чисел;
мало места в памяти и нет внешних устройств.
Недостатки:
запас чисел ограничен периодом последовательности;
числа нельзя в полной мере назвать случайными;
затраты машинного времени.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6
Методы получения ГСЧ:
метод серединных квадратов;
метод серединных произведений;
метод перемешивания;
линейный конгруэнтный метод.

МЕТОД СЕРЕДИН­НЫХ КВАДРАТОВ
Имеется некоторое четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее из R1 берется середина (четыре средних цифры) — новое случайное число — и записывается в R0. Затем процедура повторяется (см. рис.).
Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij, а 0.ghij — с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис., так и на последующих подобных рисунках.
Пример: если начальное число х0=0,2152, то (х0)2=0,04631104, т. е. x1=0,6311, затем (х1)2=0,39828721, т. е. х2=0,8287, и т. д.
Недостатки метода:
если на некоторой итерации число R0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R0;
генератор будет повторять последовательность через Mn шагов (в лучшем случае), где n — разрядность числа R0, M — основание системы счисления;
повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно;
Описанный выше способ был предложен Джоном фон Нейманом и относится к 1946 году. Поскольку этот способ оказался ненадежным, от него очень быстро отказались.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

МЕТОД СЕРЕДИН­НЫХ ПРОИЗВЕДЕНИЙ
Число R0 умножается на R1, из полученного результата R2 извлекается середина R2* (это очередное случайное число) и умножается на R1. По этой схеме вычисляются все последующие случайные числа
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

МЕТОД ПЕРЕМЕШИВАНИЯ
В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R0. Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R0*. Точно так же, циклически сдвигая содержимое ячейки R0 вправо на 1/4 длины ячейки, получаем второе число R0**.
Сумма чисел R0* и R0** дает новое случайное число R1.
Далее R1 заносится в R0, и вся последовательность операций повторяется
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ЛИНЕЙНЫЙ КОНГРУЭНТНЫЙ МЕТОД
Линейный конгруэнтный метод является одной из простейших и наиболее употребительных в настоящее время процедур, имитирующих случайные числа.
В этом методе используется операция mod(x, y), возвращающая остаток от деления первого аргумента на второй. Каждое последующее случайное число рассчитывается на основе предыдущего случайного числа по следующей формуле:
ri + 1 = mod(k · ri + b, M)
где M — модуль (0 < M), k — множитель (0 ≤ k < M), b — приращение (0 ≤ b < M),
r0 — начальное значение (0 ≤ r0 < M)
Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью.
Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом, а при b ≠ 0 — смешанным конгруэнтным методом
Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2N, поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M, меньшего, чем 2N: в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа ri + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна, равное 231 – 1, и таким образом, M = 231 – 1.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ЛИНЕЙНЫЙ КОНГРУЭНТНЫЙ МЕТОД
Одним из требований к линейным конгруэнтным последовательностям является как можно большая длина периода. Длина периода зависит от значений M, k и b. Теорема, которая приводится ниже, позволяет определить, возможно ли достижение периода максимальной длины для конкретных значений M, k и b.
Теорема. Линейная конгруэнтная последовательность, определенная числами M, k, b и r0, имеет период длиной M тогда и только тогда, когда:
числа b и M взаимно простые;
k – 1 кратно p для каждого простого p, являющегося делителем M;
k – 1 кратно 4, если M кратно 4.
Примеры использования линейного конгруэнтного метода для генерации случайных чисел:
Пример 1:
M = 2N, k = 3 + 8· q (или k = 5 + 8 · q), b = 0, r0 — нечетно .
Было установлено, что ряд псевдослучайных чисел, генерируемых на основе данных из примера 1, будет повторяться через каждые M/4 чисел. Число q задается произвольно перед началом вычислений, однако при этом следует иметь в виду, что ряд производит впечатление случайного при больших k (а значит, и q). Результат можно несколько улучшить, если b нечетно и k = 1 + 4 · q — в этом случае ряд будет повторяться через каждые M чисел. После долгих поисков k исследователи остановились на значениях 69069 и 71365.
Пример 2:
M = 231 – 1, k = 1 220 703 125, b = 7, r0 = 7
Генератор случайных чисел, использующий данные из примера 2, будет выдавать случайные неповторяющиеся числа с периодом, равным 7 миллионам.
Мультипликативный метод генерации псевдослучайных чисел был предложен Д. Г. Лехмером (D. H. Lehmer) в 1949 году.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ПРИБЛИЖЕННЫЕ СПОСОБЫ ПРЕОБРАЗОВАНИЯ
В практике моделирования систем приближенные способы преобразования случайных чисел классифицируются следующим образом:
универсаль­ные способы, с помощью которых можно получать случайные числа с законом распределения любого вида;
не универсальные способы, пригодные для получения случайных чисел с конкретным законом распределения.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

УНИВЕРСАЛЬНЫЙ СПОСОБ ПРЕОБРАЗОВАНИЯ
Универсальный способ получения случайных чисел, базируется на кусочной аппроксимации функции плотности.
Пусть требуется получить последовательность случай­ных чисел {уi} с функцией плотности fn(y), возможные значения которой лежат в интервале (а, b). Представим fn(y) в виде кусочно-постоянной функции, т. е. разобьем интервал (а, b) на m интервалов.
Будем считать, что функция плотности на каждом интервале постоянна. Тогда случайную величину η можно пред­ставить в виде η=ak+ ηk
где ak— абсцисса левой границы k-ro интервала;
ηk — случайная величина, возможные значения которой располагаются равномерно внутри k-го интервала.
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

УНИВЕРСАЛЬНЫЙ СПОСОБ ПРЕОБРАЗОВАНИЯ
На участке случайная величина ηk распределена равномерно. Целесообразно разбить (а, b) на интервалы так, чтобы вероятность попадания случайной величины ηk в любой ин­тервал была постоянной и не зависела от номера интервала .
Для вычисления ak воспользуемся следующим соотношением:
Алгоритм машинной реа­лизации этого способа полу­чения случайных чисел сво­дится к выполнению следующих дей­ствий:
генерируется случай­ное равномерно распределен­ное число xi из интервала (0, 1);
с помощью этого числа случайным образом выбирается интервал ;
генерируется число xi+1 и масштабируется с целью приведения его к интервалу ,
т. е. домножается на коэффициент
вычис­ляется случайное число с требуемым законом распределения.
В пункте 2 целесообразно для этой цели построить таблицу (сформировать массив), в которую предварительно поместить номера интервалов k и значения коэффициента масштабирования, для приведения числа к интервалу (а, b). Получив из генератора случайное число xi , с помощью таблицы можно сразу определять абсциссу левой границы ak и коэффициент масштабирования
Достоинства способа:
При реализации на ЭВМ требуется небольшое количество операций для получения каждого случайного числа, так как операция масштабирования выполняется только один раз перед моделированием
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6

ПРОВЕРКА КАЧЕСТВА РАБОТЫ ГЕНЕРАТОРА
От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайная последовательность, порождаемая ГСЧ, должна удовлетворять целому ряду критериев.
Осуществляемые проверки бывают двух типов:
проверки на равномерность распределения;
проверки на статистическую независимость.
Требуется выполнить лабораторную работу…
При выполнении работы следует использовать:
Материалы к лабораторной работе (одноименный файл прилагается).
Задание к лабораторной работе (одноименный файл прилагается).
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ. Лекция 6