40827

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

Лекция

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

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

Русский

2013-10-22

259 KB

44 чел.

Лекция 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


 

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

7787. Антон Семенович Макаренко 32 KB
  Макаренко Антон Семенович Макаренко родился в г. Белополье, бывш. Харьковской губернии, в семье мастера малярного цеха железнодорожных мастерских. Макаренко подверг острой критике буржуазную и мелкобуржуазную педагогику. Он писал, ч...
7788. Педагогически взгляды представителей демократического движения в России в сер 19 века 43.5 KB
  Педагогически взгляды представителей демократического движения в России в сер 19 века Герцен. Педагогические взгляды Герцена определились философскими (атеизм и материализм), этическими (гуманизм) и политическими (революционный демократизм) убеждени...
7789. Педагогическая деятельность и взгляды Толстого Л.Н. 32 KB
  Педагогическая деятельность и взгляды Толстого Л.Н. Горячий протестант и страстный обличитель, как назвал его В.И. Ленин, подверг разрушительной критике постановку воспитания и образования в России и в Западной Европе, современные ему школы, утверж...
7790. Педагогическая система Ушинского 28 KB
  Педагогическая система Ушинского В основе педагогической системы Ушинского лежит идея народности. Под народностью Ушинский понимал своеобразие каждого народа, обусловленное его историческим развитием, географическими, природными условиями. В статье ...
7791. Педагогические Взгляды французских материалистов XVIII века 33 KB
  Педагогические Взгляды французских материалистов XVIII века Педагогические идеи Клода Адриана Гельвеция Гельвеций прославился как автор книги Об уме, которая вышла в 1758 г. и вызвала яростные нападки со стороны всех сил реакции, правя...
7792. Педагогическая технология Руссо 31.5 KB
  Педагогическая технология Руссо Основу педагогических взглядов Руссо составляет теория естественного воспитания, которая тесно связана с его социальными взглядами, с его учением о естественном праве Руссо утверждал, что человек родится совершенным, ...
7793. Педагогическая деятельность и теория Яна Амоса Коменского 36 KB
  Педагогическая деятельность и теория Яна Амоса Коменского О роли воспитания, его целях и задачах Взгляды Коменского на ребенка, его развитие и воспитание коренным образом отличались от средневековых представлений. Вслед за гуманистами эпохи Возрожде...
7794. Педагогическая мысль и школа в период Французской буржуазной революции XVIII века 43 KB
  Педагогическая мысль и школа в период Французской буржуазной революции XVIII века В 70-х годах XVIII века во Франции создалась революционная ситуация. В недрах феодального общества выросли и созрели формы нового, капиталистического уклада. О...
7795. Педагогическая мысль эпохи Возрождения 37.5 KB
  Педагогическая мысль эпохи Возрождения Наиболее ярко педагогическая мысль эпохи Возрождения представлена трудами итальянских, немецких и французских ученых-гуманистов. Среди итальянских гуманистов эпохи Возрождения особенно выделяется Витторино да Ф...