40827

Генерация базовой последовательности. Требования к генератору случайных чисел

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Требования к генератору случайных чисел. Проверка и улучшение качества последовательностей псевдослучайных чисел. При дискретном моделировании базовым процессом является последовательность чисел {xi} = x0 x1 xN представляющих собой реализации независимых равномерно распределенных на интервале 0 1 случайных величин {i} = 0 1 N или в статистических терминах – повторную выборку из равномерно распределенной на 0 1 генеральной совокупности значений величины . Поэтому на ЭВМ вместо непрерывной совокупности равномерных...

Русский

2013-10-22

259 KB

38 чел.

Лекция 16. Генерация базовой последовательности. Требования к генератору случайных чисел. Проверка и улучшение качества последовательностей псевдослучайных чисел. Проверка качества последовательностей. Характеристики качества генераторов

Генерация базовой последовательности

При моделировании систем на ЭВМ программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. При дискретном моделировании базовым процессом является последовательность чисел {xi} = x0, x1, …, xN, представляющих собой реализации независимых, равномерно распределенных на интервале (0, 1) случайных величин {ξi} = ξ0, ξ1, …, ξN или в статистических терминах – повторную выборку из равномерно распределенной на (0, 1) генеральной совокупности значений величины .

Непрерывная случайная величина имеет равномерное распределение в интервале (a, b), если ее функции распределения (рис. 4.9, a) и плотности (рис. 4.9, б) соответственно примут вид

а      б

Рис.4.9. Равномерное распределение случайной величины

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

M[] = xf(x) dx = xdx/(b a) = (a + b)/2;  (4.7)

D[] =  (x M[])2f(x) dx = (b a)2/12;

= + = (b a)/(2 ).

При моделировании систем на ЭВМ применяется частный случай равномерного распределения, когда случайные числа находятся на интервале (0, 1), т.е. границы интервала a = 0 и b = 1. Функции плотности и распределения соответственно имеют вид:

  (4.8)

Такое распределение имеет математическое ожидание M[] = 1/2 и дисперсию D[] = 1/12.

Получить такое распределение на цифровой ЭВМ невозможно, так как машина оперирует с n-разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2n случайных чисел того же интервала. Закон распределения такой дискретной последовательности называют квазиравномерным распределением.

Случайная величина , имеющая квазиравномерное распределение в интервале (0, 1), принимает значения xi = i/(2n  l) с вероятностями рi = 1/2n, i=.

Математическое ожидание и дисперсия квазиравномерной случайной величины соответственно имеют вид:

.

Таким образом, математическое ожидание квазиравномерной случайной величины совпадает с математическим ожиданием равномерной случайной последовательности интервала (0, 1), а дисперсия отличается только множителем (2n + 1)/(2n – 1), который при достаточно больших n близок к единице.

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

Требования к генератору случайных чисел

Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны:

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

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

х i 1 = Ф(хi),     (4.9)

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

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

Первой процедурой получения псевдослучайных чисел была процедура – метод серединных квадратов, заключающаяся в следующем. Пусть имеется 2n-разрядное число, меньше 1: хi = 0,а1а2а2n. Возведем его в квадрат: хi2 = 0,b1b2b4n, затем отберем средние 2n разрядов хi+1 = 0,bn+1bn+2b3n, которые будут являться очередным числом псевдослучайной последовательности. Например, если начальное число х0 = 0,2152, то (х0)2 = 0,04631104, т.е. х1 = 0,6311, затем (х1)2 =  0,39828721, т.е. х2 = 0,8287, и т.д. Недостаток этого методаналичие корреляции между периодами последовательности, а в ряде случаев случайность вообще может отсутствовать. Например, если х0 = 0,4500, то (х0)2 = 0,20250000, х1 = 0,2500, (х1)2 = 0,06250000, х2 = 0,2500, (х2)2 = 0,06250000, х3 = 0,2500 и т.д. 

Вторая конгруэнтная процедура генерации псевдослучайных последовательностей представляет собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности. Два целых числа α и β конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что α – β = km, т.е. если разность α – β делится на m и если числа α и β дают одинаковые остатки от деления на абсолютную величину числа m. Например, 1984 ≡ 4 (mod 10),
5008 ≡ 8 (
mod 103) и т.д.

Конгруэнтные процедуры являются чисто детерминированными, так как описываются в виде рекуррентного соотношения, когда функция (4.9) имеет вид:

Xi+1 = λХi + μ(mod M),   (4.10)

где Xi+1, λ, μ, М – неотрицательные целые числа.

Раскроем рекуррентное соотношение (4.10):

Х1 = λХ0 + μ(mod M);

Х2 = λХ1 + μ = λ2Х0 + (λ + 1)μ(mod M);

Х3 = λХ2 + μ = λ3Х0 + (λ2 + λ + 1)μ = λ3Х0 + (λ3 – 1)μ/(λ – 1)(mod M);

…………….

Хi = λiХ0 + (λi – 1)μ/(λ – 1)(mod M).         (4.11)

Если заданы начальное значение Х0, множитель λ и аддитивная константа μ, то (4.11) однозначно определяет последовательность целых чисел {Хi}, составленную из остатков от деления на М членов последовательности
iХ0 + (λi – 1)/(λ – 1)}. Таким образом, для любого i  1 справедливо неравенство Хi<M. По целым числам последовательности {Хi} можно построить последовательность {xi} = {Хi/M} рациональных чисел из единичного интервала (0, 1). В настоящее время почти все пакеты прикладных программ универсальных ЭВМ для вычисления последовательностей равномерно распределённых случайных чисел основаны на конгруэнтной процедуре.

4.3. Проверка и улучшение качества последовательностей псевдослучайных чисел

Проверка качества последовательностей

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

Проверка равномерности последовательностей псевдослучайных квазиравномерно распределённых чисел {xi} может быть выполнена по гистограмме с присваиванием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi c вероятностью pj = 1/m, j = , попадет в один из подынтервалов. Всего в каждый j-й подынтервал попадает Ni чисел последовательности {xi}, i = , причём N = . Относительная частота попадания случайных чисел из последовательности {xi} в каждый из подынтервалов будет равна Nj/N. Очевидно, что если числа xi принадлежат псевдослучайной квазиравномерно распределённой последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис. 4.10, а) приближается к теоретической прямой 1/m.

 

Рис. 4.10. Проверка равномерности последовательности

Оценка степени приближения, т.е. равномерности последовательности {xi}, может быть проведена с использованием критериев согласия. На практике принимается m = 20 50, N = (102103)m.

Суть проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность {xi} разбивается на две последовательности:

х1, х3, х5, x2i-1;

х2, х4, х6, x2i, i = .

Затем проводится следующий эксперимент. Если выполняется условие:

, i = ,    (4.12)

то фиксируется наступление некоторого события и в счётчик событий добавляется единица. После N/2 опытов, когда генерировано N число, в счётчике будет некоторое число k  N/2.

Геометрически условие (4.12) означает, что точка (x2i-1, x2i), i = , находится внутри круга радиусом r = 1, что иллюстрирует рис. 4.10, б. В общем случае точка (x2i-1, x2i) всегда попадает внутрь квадрата. Тогда теоретическая возможность попадания этой точки в четверть круга:

pk = S 1/4круга/Sквадрата = (r2/4)/(11) = /4.

Если числа последовательности {xi} равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота 2k/N  /4.

Проверка стохастичности последовательности псевдослучайных чисел {xi} наиболее часто проводится методами комбинаций и серий. Сущность метода сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе Хi.

Теоретически закон появления j единиц в l разрядах двоичного числа Хi описывается, исходя из независимости отдельных разрядов, биномиальным законом распределения:

P(j, l) = Cljpj(1)[1 – p(1)]l-j = Cljpl(1),

где P(j, l) – вероятность появления j единиц в l разрядах числа Xi;
p(1) = p(0) = 0,5 – вероятность появления единицы и нуля в любом разряде числа Xi; Clj = l! / [j! / (lj)!].

Тогда при фиксированной точке выборки N теоретически ожидаемое число появления случайных чисел Xi с j единицами в проверяемых l разрядах будет равно nj = NCljpl(1).

После нахождения теоретических и экспериментальных вероятностей P(j, l) или чисел nj при различных значениях l  n гипотеза о стохастичности проверяется с использованием критериев согласия [4, 1].

При анализе стохастичности последовательности чисел {xi} методом серий последовательность разбивается на элементы первого и второго рода (a и b), т.е.

где 0 < p < 1.

Серией называется отрезок последовательности {xi}, состоящий из идущих друг за другом элементов одного и того же рода. Причём число элементов в отрезке (a или b) называется длиной серии.

После разбиения последовательности {xi} на серии первого и второго рода будем иметь, например, серию вида

.....aabbbbaaabbbaabbab.... .

Так как случайные числа a и b в данной последовательности независимы и принадлежат последовательности {xi}, равномерно распределённой на интервале (0, 1), то теоретическая вероятность появления серии длиной j в N опытах (под опытом здесь понимается генерация числа xi  и проверка условия xi < p) определится формулой Бернулли:

P(j, l) = Cljp(1 – p)l-j , j = , l = .

В случае экспериментальной проверки оцениваются частоты появления серий длиной j. В результате получаются экспериментальная и теоретическая зависимости P(j, l), сходимость которых проверяется по известным критериям, причём проверку целесообразно проводить при разных значениях р, 0 < р < 1 и l.

Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределённых чисел {xi} производится на основе корреляционного момента.

Случайные величины и называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая. Таким образом, независимость элементов последовательности {xi} может быть проверена путём введения в рассмотрение последовательности
{
yj} = {xi+}, где – величина сдвига последовательностей.

В общем случае корреляционный момент дискретных случайных величин и с возможными значениями yj и xi определяется по формуле

где pij – вероятность того, что (, ) примет значение (xi, yj).

Корреляционный момент характеризует рассеивание случайных величин и и их зависимость. Если случайные числа независимы, то
K = 0. Коэффициент корреляции:

,

где x и y – среднеквадратические отклонения величин и .

При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:

,

где

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

При любом   0 для достаточно больших N с доверительной вероятностью справедливо соотношение

.

Если найденное эмпирическое значение () находится в указанных пределах, то с вероятностью  можно утверждать, что полученная последовательность чисел {хi} удовлетворяет гипотезе корреляционной независимости.

Характеристики качества генераторов

При статистическом моделировании системы S с использованием программных генераторов псевдослучайных квазиравномерных последовательностей важными характеристиками качества генератора является длина периода Р и длина отрезка апериодичности L. Длина отрезка апериодичности L псевдослучайной последовательности {xi}, заданной уравнением

Xi+1 = λХi + μ(mod M), xi = Xi/M,

есть наибольшее целое число, такое, что при 0<j<i<L событие Р{xi=xj} не имеет места, т.е. все числа х в пределах отрезка апериодичности не повторяются.

Если длина последовательности чисел {xi} больше отрезка апериодичности L, то повторение испытаний происходит в тех же условиях, что и раньше, т.е. увеличение числа реализации не дает новых статистических результатов.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. М. : Высш. шк., 2001. 343 с.

2. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. 2-е изд. М.: Высшая школа, 1998. 319 с.

3. Тарасик В.П. Математическое моделирование технических систем: учеб. для вузов / В.П. Тарасик. М.: Наука, 1997. 600 с.

4. Введение в математическое моделирование: учеб. пособие для вузов/ под ред. П.В.Тарасова. М.: Интермет Инжиниринг, 2000. 200 с.

5. Ивченко Г.И. Математическая статистика: учебное пособие для втузов / Г.И. Ивченко, Ю.И. Медведев. М.: Высш. шк., 1984. 248 с.

6. Альянах И.Н. Моделирование вычислительных систем / И.Н. Альянах. Л.: Машиностроение, 1988. 233 с.

7. Шеннон Р. Имитационное моделирование систем – искусство и наука / Р. Шеннон. М.: Мир, 1978. 308 с.

7

f(x)     F(x)

1

1/(ba) -----

0 a                 b x 0      a        b   x


 

А также другие работы, которые могут Вас заинтересовать

80027. Сравнение регуляторов LQR и MPC с наблюдателем высокого порядка 1.24 MB
  Чтобы понять как все происходит внутри колонны требуется рассмотреть некоторые тонкости. Первый элемент который необходим для работы колонны это сырьевой насос перекачивающий сырую нефть из складского резервуара в систему. Внутри ректификационной колонны находится набор тарелок в которых проделаны...
80029. Оценка доходности и ликвидности в ВТБ 24 1.21 MB
  Основная цель деятельности коммерческого банка -– получение максимальной прибыли при обеспечении устойчивого длительного функционирования и прочной позиции на рынке. Поэтому прибыли и факторы влияющие на ее динамику занимает одно из центральных мест в анализе деятельности коммерческого банка.
80031. Исследование уровня жизни граждан и его реализации в сфере социального обеспечения 300 KB
  Однако не исключено, что при неразумной государственной политике грядущим поколениям России достанется дряхлеющее в борьбе с центробежными тенденциями и переворотами государство, расколотое и разлагающееся под бременем бедности и нищеты общество, больное и полуграмотное по стандартам...
80032. Створення об’єктивної картини проблем сучасної телерадіожурналістики на прикладі конкретних публікацій збірника «Теле- та радіожурналістика» 275.09 KB
  На сучасному етапі розвитку електронних засобів масової інформації журналіст радіо і телебачення виступає одночасно в кількох іпостасях здобувача укладача редактора аналітика оформлювача тлумача коментатора оглядача інформації та безпосереднього виконавця ролі її дикторського озвучування.
80035. Океанология. Физические явления и процессы в океане 14.3 MB
  Показан исторический опыт и современный уровень представлений о районировании и классификации подразделений Мирового океана. Приводятся основные сведения о физических явлениях и процессах в океане: рассматриваются вопросы перемешивания и устойчивости вод термики оптики акустики океана...