40827

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

Лекция

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

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

Русский

2013-10-22

259 KB

40 чел.

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


 

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

82480. Деньги: возникновение, сущность, функции. Измерение денежной массы. Денежные агрегаты 32.39 KB
  Вторая деньги появились в результате эволюционного процесса который независимо от воли людей привел к тому что некоторые предметы выделились из общей массы и заняли особое место посредника в акте обмена. Сущность денег Деньги являются самым активным элементом экономики важнейшей частью экономической деятельности связующим звеном между участниками рынка и производством. Деньги обладают свойством обмениваемости на товары включая недвижимость драгоценности и художественные произведения. Функции денег Если рассматривать функции денег...
82481. Инфляция: сущность, виды, последствия 34.04 KB
  Сопровождается скачкообразным повышением цен от 1020 до 200300 в месяц. Рост цен не регулируется инфляция охватывает все сферы хозяйственной жизни. Поледствия инфляции: страдают больше всего те кто имеет фиксированные доходы; обесцениваются сбережение населения; падение реальной заработной платы по сравнению с номинальной; влияние на народное хозяйство: усиливается диспропорциональность развития производства; капиталы из сферы производства отвлекаются в спекулятивную торговлю; искажается нормальная структура потребительского...
82482. Антиинфляционная политика государства. Кривая Филлипса 46.16 KB
  Антиинфляционная политика государства может проводиться методами активной и адаптивной политики. Активная политика проводится с целью ликвидации причин инфляции а адаптивная для приспособления к ней экономики и смягчения ее отрицательных последствий. Активная антиинфляционная политика предполагает использование метода шоковой терапии при которой за короткий период времени уничтожаются причины инфляции как на стороне спроса так и на стороне предложения Адаптивная политика предполагает использование метода постепенного сокращения инфляции...
82483. Социальная политика государства. Источники доходов населения. Система социальной защиты 30.8 KB
  Источники доходов населения. Доходы населения это совокупность средств и затрат в натуральном выражении для поддержания физического морального экономического и интеллектуального состояния человека. Формирования денежных доходов осуществляется за счет оплаты труда работников выплат из социальных фондов социальных трансфертов предпринимательских доходов Социальная защита населения это одно из важнейших направлений социальной политики государства заключающееся в установлении и поддержании общественно необходимого материального и...
82484. Государственное регулирование экономики: социальное неравенство, измерение распределения доходов. Черта бедности. Кривая Лоренца, коэффициент Джини 55.12 KB
  ГОСУДАРСТВЕННОЕ РЕГУЛИРОВАНИЕ ЭКОНОМИКИ одна из основных форм участия государства в экономике состоящая в его воздействии на распределение ресурсов и доходов на уровень и темпы экономического развития и благосостояние населения страны. К числу наиболее распространенных индикаторов дифференциации доходов населения относят коэффициент концентрации доходов индекс Джини и кривую Лоренца характеризующие степень удаления от состояния равенства в распределении доходов. Степень неравенства в распределении доходов в западной экономической...
82485. Теория сравнительных преимуществ и протекционизм. Международная торговля и распределение доходов 33.02 KB
  Она исходит из наличия двух стран и двух товаров; издержек производства только в виде заработной платы которая к тому же одинакова для всех профессий; игнорирования различий в уровне заработной платы между странами; отсутствия транспортных издержек и наличия свободной торговли. увеличению производства в отраслях ориентированных на экспорт и сокращению производства в отраслях конкурирующих с импортом. Теория ХекшераОлинадает возможность оценить последствия развития внешней торговли для владельцев различных факторов производства рабочих...
82486. Теории международной торговли (А. Смита, Д. Риккардо, Э. Хекшера, Б. Олина) 34.21 KB
  В своем труде Исследование о природе и причинах богатства народов в полемике с меркантилистами Смит сформулировал идею о том что страны заинтересованы в свободном развитии международной торговли поскольку могут выиграть от нее независимо от того являются они экспортерами или импортерами. Каждая страна должна специализироваться на производстве того товара где она обладает абсолютным преимуществом – выгодой основанной на разной величине затрат на производство в отдельных странах – участницах внешней торговли. При анализе направлений...
82487. Мировое хозяйство, понятие и эволюция. Интеграция в мировой экономике 32.42 KB
  Интеграция в мировой экономике Мировое хозяйство – совокупность национальногосударственных и негосударственных структур а также их взаимодействий на основе международного разделения труда и политических контактов. В данной трактовке мировое хозяйство представляет собой единое экономическое пространство мегаэкономику в котором субъектами хозяйственных отношений выступают: национальные экономики стран мира; субъекты мирового бизнеса – транснациональные корпорации и их альянсы; институты мирового хозяйства – международные экономические...
82488. Международная торговля: свобода торговли и протекционизм 33.52 KB
  Сторонники свободной торговли считают что международная торговля должна развиваться на основе рыночных сил спроса и предложения т. Экономические аргументы в защиту протекционистских мер: с помощью импортных пошлин страна может достичь улучшения условий торговли и увеличения экономического выигрыша; поддержка национальной промышленности на этапе ее зарождения и становления; повышение уровня занятости национальных ресурсов; смягчение кризиса в отраслях испытывающих экономические трудности; ограждение национальной экономики от мировых...