40827

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

Лекция

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

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

Русский

2013-10-22

259 KB

46 чел.

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


 

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

14413. Экономическое отношение современной молодёжи в России 33.5 KB
  Экономическое отношение современной молодёжи в России Молодёжь в значительной части обладает тем уровнем мобильности интеллектуальной активности и здоровья который выгодно отличает её от других групп населения. В то же время перед любым обществом стоит вопрос о...
14414. Хочешь жить - умей вертеться 18.22 KB
  Хочешь жить умей вертеться. В современном мире все вращается вокруг денег. Каждый пытается гдето сэкономить а ктото старается увеличить свою прибыль. Что касаемо студентов... То не буду лукавить даже порой садясь в автобус или маршрутное такси нас давит жаба плат
14415. Экономические отношения современной молодёжи России 30 KB
  Экономические отношения современной молодёжи России сочинение Современная молодежь России в последнее время всё чаще идёт на поводу брендов о которых не умолкают СМИ стремится быть в первых рядах и подражать иностранным известным личностям в каких либо их приобре...
14416. Сочинение на тему: «Экономические отношения молодежи в стране» 20.49 KB
  Сочинение на тему: Экономические отношения молодежи в стране. В условиях социальноэкономического реформирования российского общества особую актуальность приобретают исследования проблем молодежи проживающей в малых городах. Проблемная ситуация заключается в то
14417. Экономические отношения современной молодёжи в моей группе 7.39 KB
  Экономические отношения современной молодёжи в моей группе. Экономические отношения это отношения между людьми по поводу распределения обмена и потребления благ. В экономические отношения люди обычно вступают исходя из мотивов выгоды. Дай то что нужно мне и ...
14418. Есть такая профессия - защищать Родину 482.72 KB
  Сочинение на тему: Есть такая профессия защищать Родину Я счастливый человек Я живу со своими родителями хожу в любимую школу слышу смех бабули и дедушки. Мне интересно читать книги рассматривать картинки в энциклопедиях изучать географические карты. Как мног
14419. Важный выбор 13.85 KB
  Важный выбор Мой важный выбор состоял в том что я решил сильно поменять свою жизнь поступив в суворовское военное училище. Одним летним утром я как обычно проснулся поздно но по новостям увидел передачу об Уссурийском суворовском военном училище.
14420. Важный выбор профессии 17.36 KB
  Я учусь в 8 классе мне 14 лет. Через несколько лет меня ждет расставание со школой. Но самое главное мне предстоит сделать очень важный выбор от которого впоследствии будет зависеть моя будущая жизнь. Кто поможет мне ответить на вопрос: Кем быть Куда пойти учиться ...
14421. Моя мечта 32 KB
  Среди десятков, сотен, тысяч принимаемых человеком решений ни одно не может сравниться по своему значению, по роли и влиянию на судьбу с решением выбора профессии.