Генераторы случайных чисел. Псевдослучайные числа icon

Генераторы случайных чисел. Псевдослучайные числа



НазваниеГенераторы случайных чисел. Псевдослучайные числа
Дата конвертации05.09.2012
Размер127.11 Kb.
ТипПрограмма
1. /RANDOMIZ.DOC
2. /М.М.4,1.doc
3. /МЕТ1_M.doc
4. /МЕТ2_M.doc
5. /МЕТ3_M.doc
6. /МЕТ4_M.doc
7. /МЕТ5_M.doc
8. /МЕТ6_M.doc
9. /МЕТ7_2_M.doc
10. /МЕТ8_2_M.doc
11. /МЕТ9_2_M.doc
12. /Мет10_2_M.doc
13. /Мет11_2_M.doc
14. /Мет12_2_M.doc
15. /Мет13_2_M.doc
16. /Мет14_2_M.doc
Генераторы случайных чисел. Псевдослучайные числа
Дифференциальные уравнения первого порядка
Введение
Точечные оценки параметров распределений
Методы получения точечных оценок
Интервальное оценивание параметров нормально распределенной случайной величины
Проверка статистических гипотез о параметрах нормально распределенной случайной величины
Лабораторная работа №6
Введение
Моделирование случайных сигналов и процессов
Аппроксимация эмпирических данных методом наименьших квадратов
Лабораторная работа №10
Линейные статистические модели. Пассивный и активный эксперименты
Синтез D–оптимальных тестирующих сигналов для идентификации динамических объектов
Функции одной переменной в экономических задачах
Лабораторная работа №14

— —

Генераторы случайных чисел. Псевдослучайные числа.


При построении стохастических иммитационных моделей необходимо обеспечить возможность учета стохастических воздействий. Результаты статистического моделирования существенно зависят от качества выбранных исходных последовательностей случайных чисел.
На практике используется три основных способа генерации случайных чисел: аппаратный (физический), табличный (файловый) и алгоритмический (программный).

Определим основные требования, которым должен удовлетворять идеальный генератор. То есть псевдослучайные последовательности чисел должны:

  1. Состоять из квазиравномерно распределенных чисел.

  2. Содержать статистически независимые числа.

  3. Быть воспроизводимыми.

  4. Программа генерации должна иметь наименьшие затраты машинного времени и занимать минимальный объем памяти.

Метод средних квадратов


Одной из первых алгоритмических процедур получения псевдослучайных чисел был метод средних квадратов, который заключается в следующем. Например, для восьмиразрядного числа (половина равна 4 разрядам) берется начальное значение:

х0 = 0.2152, возводится в квадрат:

( х0 )2 = 0.04631104, берется “среднее” число:

х1 = 0.6311 и снова возводится в квадрат:

( х1 )2 = 0.39828721,

х2 = 0.8287 и т. д.

К сожалению этот метод работает неудовлетворительно: существует наличие корреляции между числами, а иногда и отсутствие характера случайности.


Самое широкое применение при моделировании на ЭВМ получили конгруэнтные методы генерации псевдослучайных последовательностей, в основе которых лежит фундаментальное понятие конгруэнтности.

Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m — целое число, тогда и только тогда, когда существует такое целое число k, что

a - b = km ,

то есть разность a - b делится на m, и если числа a и b дают одинаковые остатки деления на абсолютную величину числа m.

Например 1984 º 4 ( mod 10 ),

5008 º 8 ( mod 103 ) и т.д.

Величина m берется равной длине машинного слова m = 2b, где b — число бит в машинном слове.

Конгруэнтный метод представляет собой арифметическую процедуру для генерирования конечной последовательности равномерно распределенных чисел. С использованием нескольких рекурентных формул было построено множество конгруэнтных алгоритмов. Среди них наиболее известным являются мультипликативный, смешанный и аддитивный.

Мультипликативный конгруэнтный метод


Основная формула этого метода имеет вид:

xi+1 = axi (mod m),

где a и m — неотрицательные целые числа.

Согласно этому выражению, мы должны взять последнее случайное число xi, умножить его на постоянный коэффициент a и взять модуль полученного числа по m, то есть разделить на axi, и остаток считать как xi+1. Поэтому для генерирования последовательности чисел xi необходимо начальное значение х0, множитель а и модуль т.

Любой генератор псевдослучайных чисел может дать лишь конечное множество чисел, после которого последовательность будет повторяться. Период, или длина последовательности L, зависит от ЭВМ и от выбранного модуля, а статистические свойства зависят от выбранного начального значения и множителя. Таким образом, выбирать а, х0 и т следует так, чтобы обеспечить максимальный период и минимальную корреляцию между генерируемыми числами. Правильный выбор модуля не зависит от системы счисления. Обычно берут т равным длине машинного слова.

Выбор а и х0.

Для двоичной системы а = 8Т ± 3, где Т может быть любым целым положительным числом. х0 — любое положительное, но нечетное число.

Для десятичной системы а = 200Т ± Q, где Т любое целое положительное число, Q может принимать одно из следующих значений ± (3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61), х0 — любое положительное число, которое не делится на 2 и на 5.

Процедура вычисления случайных чисел между 0 и 1:

  1. Выбрать в качестве х0 произвольное нечетное число.

  2. Вычислить коэффициент а = 8Т ± 3.

  3. Найти произведение ах0, содержащее не более 2b значащих разрядов.

  4. Взять b младших разрядов в качестве первого члена последовательности х1, а остальные отбросить.

  5. Определить дробь х1 = х1 / 2b из интервала (0, 1).

  6. Присвоить х0 := х1.

  7. Вернуться к пункту 3.


Таким образом, генерируемая последовательность чисел xi, i = 0, 1, ..., N, представляет собой равномерно распределенные на интервале (0, 1) случайные числа. Следует иметь в виду, что на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2п случайных чисел того же интервала. Поэтому закон распределения такой дискретной последовательности называют квазиравномерным распределением. При этом случайная величина принимает значения:

с вероятностью , где i = 0, 1, ..., 2n -1.

,

.

Для равномерной случайной последовательности этого же интервала (0, 1) имеем:

,

.

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

Смешанный метод


Работа этих генераторов основана на использовании формулы

xi+1 = axi + C (mod m)

С вычислительной точки зрения смешанный метод генерации последовательности неотрицательных целых чисел сложнее мультипликативного на одну операцию сложения, но при этом возможность выбора дополнительного параметра позволяет уменьшить возможную корреляцию получаемых чисел. Однако экспериментальная проверка качества генерируемой последовательности чисел на основе этой формулы является сложнее.

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


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

Проверка равномерности


Выполняется по гистограмме. Для проверки выдвигается гипотеза о равномерности распределения чисел в интервале (0, 1). Затем этот интервал разбивается на т равных частей. Это означает, что при генерации последовательности { xi } каждое из чисел xi с вероятностью



попадет в один из интервалов. Всего в каждый j-ый подинтервал попадет Nj чисел, причем

.

Относительная частота попадания случайных чисел в каждый из подинтервалов равна NN. На следующем рисунке показан пример гистограммы.




Пунктирная линия соответствует теоретическому значению Рj, а сплошная — экспериментальному NN. Очевидно, что при большом N экспериментальная гистограмма приблизится к теоретической. Оценка степени приближения может быть проведена с использованием критериев согласия. На практике обычно принимается т = 20 ¸ 50, N = (102 ¸ 103т.

Проверка стохастичности


Среди наиболее часто используемых тестов являются интервальный тест и автокорреляционные тесты. Интервальный тест проводится методами комбинаций и серий. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в п-разрядном двоичном числе хi. На практике длину последовательности N берут достаточно большой и проверяют все п разрядов или только l старших разрядов числа хi.

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

P ( j,l ) = Cl j P l (1),

где P ( j,l ) — вероятность появления j единиц в l разрядах числа хi, Р (1) = Р (0) = 0.5 — вероятность появления единицы (нуля) в любом разряде числа хi.

.

Тогда, если выбрать длину выборки N фиксированной, то теоретически ожидаемое число появления случайных чисел хi с j единицами в проверяемых разрядах будет равна

hj = N Cl j P l (1) .

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

Проверка независимости


Проверка независимости элементов последовательности проводится на основе вычисления корреляционного момента. Случайные числа x и h называются независимыми, если закон распределения каждого из них не зависит от того, какое значение приняло другое. Для независимых величин корреляционный момент и коэффициент корреляции равен нулю:





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







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

, , , , ,

где t — величина сдвига последовательностей.

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

.

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


Моделирование случайных сигналов и процессов

Формирование возможных значений случайных величин с заданным законом распределения


Исходным материалом служат случайные величины с равномерным распределением в интервале (0, 1):



Есть простой метод преобразования равномерного распределения в требуемое. Его называют прямым методом. Он заключается в преобразовании случайных величин. Пусть переменная у является функцией от х:

у = j ( х ).

Тогда для каждого значения х однозначно определяется у.

Пусть х — случайная величина, тогда у будет так же случайной величиной. И если х имеет функцию распределения f1 (x), то у будет иметь так же функцию распределения f2 (у), но зависящую уже от f1 (x) и j (х).

Известно, что для взаимно однозначного соответствия между х и у имеет место следующее равенство:

f1 (x) dx = f2 (y) dy, (1)

то есть вероятность того, что случайная величина х находится в интервале между х1 и х1+, равна вероятности того, что преобразованная случайная величина у будет находиться в интервале у1 и у1+.

Последнее выражение можно изобразить графически:




Согласно выражению (1) находится требуемое распределение случайной величины х:

.

Требуемое распределение f2 (y) является функцией от распределения случайной величины х и производной от функции j (х). Абсолютное значение производной принято потому, что функция распределения не может принимать отрицательных значений. Функцию у = j (х) можно найти из (1):

или (2)

Пусть f2 (y) = const. Тогда имеем равномерное распределение, и выражение (2) принимает вид:

или .

Функция j (х) для данного случая совпадает с интегральной функцией распределения F1 (x). Это выражение можно использовать для преобразования случайных чисел, то есть для реализации некоторой операции над числом уi, имеющим равномерный закон распределения, и преобразование его в число xi, имеющее заданный закон распределения:

.

Эта формула является рабочей. Она может быть использована для практических целей. Например, необходимо получить случайные числа xi с показательным законом распределения:

(х > 0). (3)

Согласно этому выражению имеем:

.

Здесь уi — случайная величина с равномерным законом распределения в интервале (0, 1). После вычисления интеграла получим:

или

.

И далее, учитывая, что случайная величина уi = 1 - y имеет так же случайное распределение в интервале (0, 1), запишем

. (4)

Однако для многих практических случаев, например для нормального распределения, уравнение (3) не имеет точного решения. Кроме того, даже простое на первый взгляд выражение (4) оказывается неудобным для решения его на ЭВМ. Поэтому на практике обычно пользуются приближенными приемами преобразования случайных чисел, основанными на кусочной аппроксимации функции плотности.

Пусть требуется получить последовательность случайных чисел { уi } с функцией плотности fh (y), возможные значения которой лежат в интервале (а, в). Представим fh (y) в виде кусочно-постоянной функции. Для этого разобъем имнтервал (а, в) на т интервалов и будем считать, что fh (y) на каждом интервале постоянна. Чтобы аппроксимировать fh (y) наиболее удобным способом для практических целей, целесообразно разбить (а, в) на интервалы так, чтобы вероятность попадания случайной величины h в любой интервал (ak, ak+1) была постоянной, то есть не зависела от номера интервала k. Тогда для вычисления ak можно использовать выражение

(5)



Случайную величину h можно представить в виде h = ak + hk, где ak — абсцисса левой границы k-го интервала; hk — случайная величина, возможные значения которой располагаются равномерно внутри k-го интервала.

Алгоритм этого способа получения случайных чисел сводится к следующим действиям.

  1. Генерируется случайное равномерно распределенное число xi из интервала (0, 1).

  2. С помощью этого числа случайным образом выбирается интервал (ak, ak+1).

  3. Генерируется число xi+1 и масштабируется с целью приведения его к интервалу (ak, ak+1), то есть домножается на коэффициент (ak+1 - ak) хk+1.

  4. Вычисляется случайное число yj = ak + (ak+1 - ak) хk+1 с требуемым законом распределения.

Для выбора интервала (ak, ak+1) с помощью случайного числа xi строят таблицу (формируют массив), в которую предварительно помещают номера интервалов k и значения коэффициента масштабирования, определенные из соотношения (5) для приведения числа к интервалу (а, в). Получив случайное число xi, с помощью этой таблицы определяют абсциссу левой границы ak и коэффициент масштабирования (ak+1 - ak).

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

Можно привести еще способы преобразования равномерно распределенных случайных чисел { хi } в последовательность с заданным законом распределения { уj } на основе предельной теоремы теории вероятностей.

Центральная предельная теорема


Если x1, x1, ..., xN — независимые одинаково распределенные случайные величины, имеющие математическое ожидание а и дисперсию s2, то при ® ¥ закон распределения суммы неограниченно приближается к нормальному.

Рассмотрим применение предельной теоремы на примере.

Пусть требуется получить последовательность случайных чисел { уj }, имеющих нормальное распределение с математическим ожиданием а и средним квадратическим отклонением s.



Случайные числа yi формируются в виде сумм последовательностей случайных чисел { хi }, имеющих равномерное распределение на интервале (0, 1). Тогда можно использовать центральную теорему:

Если независимые одинаково распределенные случайные величины х1, х1, ..., хN имеют каждая математическое ожидание а1 и среднее квадратичное отклонение s1, то сумма асимптотически нормальна с математическим ожиданием а = Na1 и .

Расчеты показывают, что сумма имеет распределение, близкое к нормальному, уже при N = 8 ¸ 12.




Похожие:

Генераторы случайных чисел. Псевдослучайные числа iconОсновные конструкции, используемые при получении случайных чисел
Получить 10 случайных целых чисел в интервале от 0 до 100. (Повторить запуск программы несколько раз – числа будут разные)
Генераторы случайных чисел. Псевдослучайные числа iconКонтрольная работа по теме «Повтор материала курса алгебры 7 класса»
Из данных чисел -8; 2,1; 7; 0,2020020002…;; 3,(6);; 0; 201;; -1 выпишите: а) натуральные числа; б) целые отрицательные числа; в)...
Генераторы случайных чисел. Псевдослучайные числа iconСамостоятельная работа по теме «Положительные и отрицательные числа» Вариант Пусть положительное число. Сравните с нулем значение выражения: а, б, в
Из данных чисел -8; 2,1; 7; 0,2020020002…;; 3,(6);; 0; 201;; -1 выпишите: а) натуральные числа; б) целые отрицательные числа; в)...
Генераторы случайных чисел. Псевдослучайные числа iconТема : Проверка закономерностей методом рассуждений
Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам. Вычисляются три числа...
Генераторы случайных чисел. Псевдослучайные числа iconТема : Проверка закономерностей методом рассуждений
Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам. Вычисляются три числа...
Генераторы случайных чисел. Псевдослучайные числа iconSheet 1: Комбинаторика – Глоссарий
Факториалом натурального числа n называется произведение натуральных чисел от единицы вплоть до этого числа: n! = 1·2·…·n
Генераторы случайных чисел. Псевдослучайные числа iconРешение : Уравнение не имеет решений Заметим, что числа: [х 2
В таблице 2Х2 стоят четыре натуральных числа. При этом соседние по вертикали числа отличаются на 6, а соседние по горизонтали в два...
Генераторы случайных чисел. Псевдослучайные числа iconЗадачи первого тура для 10 класса
Квадрат каждого из трёх чисел равен произведению двух оставшихся чисел. Докажите, что все данные числа равны
Генераторы случайных чисел. Псевдослучайные числа iconТема исследовательского проекта
«Натуральные числа». Первый пункт называется «Обозначение натуральных чисел», и он начинается со слов: «Для счёта предметов применяются...
Генераторы случайных чисел. Псевдослучайные числа iconМатериал из Википедии — свободной энциклопедии
Числа Бернулли — последовательность рациональных чисел B0,B1, найденная Я. Бернулли в связи с вычислением суммы одинаковых степеней...
Генераторы случайных чисел. Псевдослучайные числа iconВ пределах миллиона
Цели урока: Познакомить с понятиями «многозначные числа», «позиционная система записи чисел», формировать умения читать и записывать...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов