40827

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

Лекция

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

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

Русский

2013-10-22

259 KB

39 чел.

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


 

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

70348. МЕТОДИКА ФОРМИРОВАНИЯ КОММУНИКАТИВНОЙ КОМПЕТЕНТНОСТИ СТУДЕНТОВ ТЕХНИЧЕСКОГО ВУЗА В ПРОЦЕССЕ ИЗУЧЕНИЯ СОЦИАЛЬНО-ГУМАНИТАРНЫХ ДИСЦИПЛИН 95.5 KB
  Проблема формирования коммуникативной компетентности студентов не является совершенно новой. Представляется целесообразным целостно на междисциплинарном уровне исследовать проблему формирования коммуникативной компетентности студентов посредством выявления дидактического...
70349. СОСТАВ И СОДЕРЖАНИЕ ДОКУМЕНТАЛЬНЫХ МАТЕРИАЛОВ КАК ИСТОЧНИКОВ ПРИ ИЗУЧЕНИИ РАЗВИТИЯ СИСТЕМЫ ВЫСШЕГО ОБРАЗОВАНИЯ В РЕСПУБЛИКЕ БЕЛАРУСЬ 67 KB
  Статья посвящена актуальной проблеме - системному анализу документальной источниковедческой базы материалов учет которых чрезвычайно важен при изучении процесса развития системы высшего образования в нашей стране.
70350. МАРКЕТИНГ ДОПОЛНИТЕЛЬНЫХ ОБРАЗОВАТЕЛЬНЫХ УСЛУГ В ФИЛИАЛЕ РГСУ В Г. МИНСКЕ 144.5 KB
  Базируясь на учете специфики образовательных услуг, анализе внешнего, внутреннего и интерактивного маркетинга, автор исследует сущность образовательных услуг, их качество, предлагает модель маркетинга на рынке образовательных услуг, ориентированную на потенциал, процесс, результат.
70351. МАТРИЦА КОНСТРУИРОВАНИЯ УЧЕБНОГО ДИАЛОГА: ЕДИНСТВО ПРОЦЕССА И РЕЗУЛЬТАТА 79.5 KB
  В статье рассматривается вопрос конструирования учебного диалога с позиций матричного анализа. Данные параметры закладываются в матрицу конструирования учебного диалога как основные факторы по горизонтали и вертикали.
70352. ТВОРЧЕСКОЕ РАЗВИТИЕ СТУДЕНТА В КОНТЕКСТЕ СОВРЕМЕННЫХ ПРЕДСТАВЛЕНИЙ 82.5 KB
  В статье с позиций философского психологического педагогического знания проанализирована сущность творчества; обоснована новизна социальная ценность и оригинальность продукта творчества; структура творческой личности рассмотрена как совокупность творческой направленности творческих...
70353. ОРГАНИЗАЦИЯ СОЗДАНИЯ КРЕАТИВНЫХ ПРОДУКТОВ В ОБРАЗОВАТЕЛЬНОЙ ПРАКТИКЕ СТАРШЕКЛАССНИКОВ 64.5 KB
  В статье представлен экспериментально подтвержденный опыт подготовки старшеклассников к созданию креативных продуктов посредством взаимосвязи соответствующих ситуаций и педагогических технологий. Предлагаемый опыт педагогического руководства созданием...
70354. ЦЕННОСТНЫЙ КОМПОНЕНТ УЧЕБНОГО ИСТОРИЧЕСКОГО ЗНАНИЯ 92 KB
  В статье рассматривается проблема содержания образования определяется сущность ценностного компонента содержания исторического образования в школе и предлагаются пути его реализации в практике обучения учащихся на уроках истории. Изменения происходящие в обществе определяют...
70355. МОДЕЛЬ ЭСТЕТИЧЕСКОГО ВОСПИТАНИЯ СТУДЕНТОВ ПЕДАГОГИЧЕСКИХ СПЕЦИАЛЬНОСТЕЙ СРЕДСТВАМИ ИСКУССТВА НА ОСНОВЕ ГЕРМЕНЕВТИЧЕСКОГО ПОДХОДА 64 KB
  В статье рассматривается проблема эстетического воспитания будущих специалистов в области мировой и отечественной культуры средствами искусства на основе герменевтического подхода. Модель эстетического воспитания студентов педагогических специальностей средствами искусства на основе...
70356. КОНСТРУИРОВАНИЕ И ИЗУЧЕНИЕ УЧЕБНОГО МАТЕРИАЛА В СОДЕРЖАТЕЛЬНОЙ ЛИНИИ «ИСТОРИЯ И ПАМЯТЬ» 65.5 KB
  Автором рассматриваются дидактические возможности формирования исторической памяти у учащихся через конструирование и изучение содержания учебно-исторического материала. Значение исторической памяти как феномена который способствует формированию национальной и гражданской идентичности общеизвестно.