Имитация случайных величин и процессов Базовый датчик

Моделирование случайных элементов в системах является одной из самых главных, базовых задач математического моделирования.

Любая случайная величина или процесс X может моделироваться следующим образом:

Базовый датчик выдает независимые равномерно распределенные случайные величины:

1. непрерывные в [0,1);

2. дискретные в

Типы базовых датчиков:

1. физические (любой физический шум) – не используются, т.к. характеристики нестабильны и реализацию повторить нельзя;

2. псевдослучайные – строятся на основе детерминированного алгоритма, но полученные результаты неотличимы от случайных.

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

Требования к базовым датчикам и их проверка

1. Отрезок апериодичности

Периодом T и длиной отрезка апериодичности датчика называются наименьшие из величин, удовлетворяющие

Чем больше T и L, тем лучше датчик (особенно L).

Как определить их:

1. Берем V – достаточно большое число (обычно

2. Генерируем и проверяем ,запоминая.

3. Генерируем и проверяем . Если нет для , то и . Иначе запоминаем , для которого , и находим следующий , для которого (если нужно, генерируются дополнительные величины). Тогда

4. Генерируем и и ищем первое совпадение . Тогда

2. Равномерность

Должно быть для

Проверка:

1. Берем и генерируем

2. Находим и разбиваем отрезок [0,1) на k равных частей (длиной )

3. Для каждого числа определяем, в какой интервал оно попало:

и заполняем массив :

4. По значениям этого массива строим гистограмму (для наглядности).

5. Используем критерий

.

Выбираем уровень значимости (обычно 5%), а число степеней свободы . В таблицах находим значение и проверяем: если ,то «данные эксперимента не противоречат гипотезе о равномерности случайных чисел», иначе – «противоречат».

3. Некоррелированность

1. Генерируем

2. Вычисляем , (можно и больше).

3. Вычисляем

4. Проверяем для всех k

Если да, то «данные эксперимента не противоречат гипотезе о равномерности случайных чисел», иначе – «противоречат». Здесь – уровень значимости, а берется из таблиц

4. Простейшие проверки

Подходят для любой непрерывной случайной величины.

1. Математическое ожидание:

2. Дисперсия:

Модели базовых датчиков Мультипликативный конгруэнтный метод (метод вычетов)

В основе лежит следующее рекуррентное соотношение:

– множитель, M – модуль, – стартовое значение. Рекомендуемые значения для 64-разрядной сетки:

Тогда период

Для 32-разрядной:

Тогда период

Линейные смешанные формулы.

p – порядок, стартовые значения: . Период

Частный случай. Датчик Терпугова.

function Rand (var y: Integer): Double;

const b=843314861;

         c=453816693;

         m2=1073741824; {M/2}

begin

{$O-,$R-} {Optimization- & Range Check-}

    y:=y*b+c;

    if y<0 then y:=(y+m2)+m2;

    Result:=Double(y)*0.4656613E-09;

end;

Причем тогда и только тогда, когда

Существуют и другие методы моделирования базовых датчиков.

Генерация случайных событий

1. Пусть имеется некоторое случайное событие А, наступающее с вероятностью р(А). Тогда ( – числа, генерируемые базовым датчиком). Следовательно, генератор 1 случайного события:

,где

2. Полная группа попарно несовместимых событий . Пусть Идея:

ГЕНЕРАЦИЯ ДИСКРЕТНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН

Пусть имеется дискретная случайная величина с рядом распределения.

x			...
p			...

,

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

Программная реализация

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

1. Равномерное распределение

x	0	1	...	n
p			...

Тогда

Док-во.

x удовлетворяет равномерному распределению.

2. Геометрическое распределение

x = 0,1,2,... до

Док-во.

3. Отрицательное биномиальное распределение.

х=0,1,2,... до Параметры: , и Для это распределение совпадает с геометрическим, поэтому можно представить , где - независимые случайные величины, распределенные по геометрическому закону. Т.о.

(базовый датчик должен выдать r чисел для генерации одного х).

4. Биномиальное распределение

(теорема об опытах – вероятность наступления m событий A в n опытах). Введем (функция Хэвисайда). Тогда

наступило 1 события сумма дает кол-во событий наступивших в n опытах биномиальное распределение).

5. Пуассоновское распределение

ГЕНЕРАЦИЯ НЕПРЕРЫВНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН

Непрерывная случайная величина характеризуется плотностью или функцией распределения

1. Метод обратной функции

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

Т.к. равномерно распределена в [0,1), то и равномерно распределена там же, следовательно, можно записать и так

Метод обратной функции применяется редко, т.к. обычно найти очень трудно.

Примеры.

1. Экспоненциальное распределение:

2. Непрерывные случайные величины с заданной гистограммой:

Общая площадь Функция распределения: или Чтобы найти формулу, решим уравнение

1. .Отнимаем от него , затем и т.д. до тех пор, пока не получим отрицательное значение:

2. Ясно, что . Следовательно,