Моделирование процессов с целочисленными значениями

1. Моделирование процессов с целочисленными значениями

ГРЫЗЛОВА Т. П.
РГАТА, 2 0 1 0
Моделирование.
Компьютерное моделирование.

2. Процессы с целочисленными значениями

пуассоновский процесс
процесс размножения и гибели
процесс чистого размножения
распределение Пуассона
марковская цепь
случайные потоки
очереди
дисциплины обслуживания
ПРОЦЕССЫ С
ЦЕЛОЧИСЛЕННЫМИ
ЗНАЧЕНИЯМИ

3. Методика описания характеристик процессов с целочисленными значениями

Вводятся постулаты процесса
Строится автоматная модель (стохастический автомат Мура)
Составляется выражение для вероятности произвольного состояния процесса
Составляется выражение для приращения вероятности состояния процесса
Выполняется предельный переход к дифференциальному уравнению
Задаются начальные условия и решаются системы дифференциальных
уравнений

4. Пуассоновский процесс

Постулаты:
(1) Процесс начинается в момент времени 0 в состоянии 0 .
(2) Непосредственный переход из состояния i возможен только в состояние i+1
(3) Вероятность перехода за время t равна
t o t
o( t ) – вероятность более чем одного скачка.
n
t
n+1
1 - t – o( t)

5. Вероятности (находятся аналитически)

Pn t t
Вероятность того, что система в момент времени (t + t)
будет находиться в состоянии n
Pn t P0 t Pn t 1 t o t
Pn 1 t t o t
Pn t t Pn t 1 t Pn 1 t t o t
Pn t t Pn t
Pn t Pn 1 t o t / t
t
Pn t Pn t Pn 1 t
n 0
P0 t P0 t
n 1
P1 0 0 P1 t te t
P0 t e t
P0 0 1
Pn t
t n
n!
e t

6. Процесс размножения и гибели

Постулаты:
(1) Непосредственный переход из состояния i , i 1 возможен в
состояния i+1 и i -1. Из состояния 0 переход возможен
только в состояние 1
(2) Вероятность перехода в течении интервала
из состояния i в состояние i+1 составляет
а в i -1 –
i t
(3) Вероятность более чем одного скачка -
n-1
i t
o t
n+1 t
n t
n-1 t
t, t t
n
n t
n+1
1 - n t - n t– o( t)

7. Вероятности переходов

Состояние
n
в момент времени
t t
возможно, если:
(1) в момент времени t система находилась в состоянии n 1
и на рассматриваемом интервале произошел переход в n
(2) в момент времени t
система находилась в состоянии
и на рассматриваемом интервале времени не
произошло никаких событий
(3) система находилась в состоянии
и на рассматриваемом интервале
произошел переход в
n
n 1
n
(4) на интервале t , t t
происходит несколько переходов.
Поскольку возможности взаимно исключают друг друга, их
складывают:

8. Вероятности состояний

Pn t t Pn t 1 n t n t
n 1 tPn 1 t n 1 tPn 1 t o t
n 1
Pn t n n Pn t n 1Pn 1 t n 1Pn 1 t
n 0 P0 t 0P0 t 1P1 t
Pi 0 1, Pn 0 0, n i
n n 1
n n 1
Условие стационарности
Начальные условия
Вероятности
переходов в марковской сети
lim Pn t p n
t
n
n
n ,n 1
; n ,n 1
n n
n n

9. Процесс линейного роста

могут делиться с вероятностью
t
t o t
погибнуть с вероятностью
t o t
Элементы совокупности на интервале
n n
n n
Pn t nPn t n 1 Pn 1 t n 1 Pn 1 t ,
P0 t P1 t
E n 0 n 0
E n t n 0e t

10. Распределение Пуассона

Распределение Пуассона – распределение вероятностей случайной
величины X с целочисленными неотрицательными значениями,
k 0,1, 2, ... ,
заданное формулой
k
p k e
k!
Математическое ожидание и дисперсия такой случайной величины равна
параметру
X x1 ... x n / n
Процесс радиоактивного распада: если в n независимых испытаниях события
A1,..., A n
происходят с одной и той же малой вероятностью p,
то вероятность того, что k событий произойдут
одновременно приблизительно выражается
распределением Пуассона с параметром = pn:
Pk np

11. Пуассоновский процесс

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

12. Марковская цепь

Марковская цепь – важный пример последовательности зависимых
случайных испытаний с конечным или счетным числом исходов. Более
точно – последовательность случайных величин
x 0 , x1,..., x n
со значениями из множества натуральных чисел, при этом условное
распределение случайной величины xn при любом n зависит только от значения
xn-1 и не зависит от всех предыдущих значений:
P x n i n | x 0 i0 ,..., x n 1 i n 1
P x n i n | x n 1 i n 1

13. Моделирование случайных потоков

Рассматривается упорядоченная последовательность случайных
моментов времени, в которые происходит или не происходит какое-либо
событие. Такая модель называется случайным потоком
Случайный поток событий используется при моделировании:
систем массового обслуживания
приема импульсных сигналов
в теории надежности
Многомерные плотности интервалов между моментами наступления
событий:
w t1, t 2 ,... t k ,...
t1 1 t1 t 0 , t 2 2 t 2 t1,....
Моменты времени наступления события
t k t k 1 k
(***)

14. Типы потоков событий

Потоки с ограниченным последействием, у которых интервалы
1, 2 ,..., n
статистически независимы, следовательно, многомерное распределение
раскладывается на произведение одномерных распределений:
w t1, t 2 ,... t k ,... t n
w t1 w t 2 ...w t k ...w t n
Потоки с ограниченным последействием задаются последовательностью
одномерных законов распределения
w t k pk
Рекуррентные стационарные потоки, у которых
p 2 p3 ... p n p
задаются двумя одномерными плотностями p , p
0
Потоки, у которых
p 0 p
это просто рекуррентные потоки.
Пример: простейший пуассоновский поток при k 1 с распределением

15. Методика моделирования случайных потоков

p e , 0
Методика моделирования
случайных потоков
(1) Формируются реализации случайных величин
с заданным законом распределения
t k
(2) По формулам (***) вычисляются моменты времени наступления событий
Последовательность моделирования пуассоновского потока –
генерация равномерно распределенных случайных величин
определение интервала времени
1
t k ln rk
вычисление моментов времени наступления событий
rk 0,1

16. ОЧЕРЕДИ

Очередь в случае одного канала
Предположение о показательном времени
обслуживания
Очереди с бесконечным числом каналов
Очереди с фиксированным числом каналов
Очередь с дисциплиной FIFO
Очередь с дисциплиной LIFO
Очередь со случайной дисциплиной обслуживания
ОЧЕРЕДИ

17. Предположение о показательном времени обслуживания

Простейший случай постоянных коэффициентов в процессе
размножения и гибели
n
n
Процесс размножения и гибели сводится к задаче об очередях при
a 1
Аналогия основана на предположении о показательных временах
обслуживания
Телефонный разговор длится X секунд, причем X – целочисленная случайная
величина с известным законом распределения
pn P X n
Очередь – это физическая система с двумя состояниями – занято и свободно
0
1
Если линия занята, то вероятность изменения состояния в следующую
секунду зависит от того, сколько идет разговор. Иначе, прошлое влияет на
будущее и процесс не является марковским.

18. Предположение о показательном времени обслуживания

Представим, что решение продолжать или не продолжать разговор
принимается каждую секунду подбрасыванием несимметричной монеты,
иначе, раз в секунду производится испытание Бернулли, последовательность
испытаний продолжается до первого успеха. Когда произойдет успех, разговор
кончится.
В этом случае время обслуживания имеет геометрическое распределение
pn q n 1p
Когда линия занята, вероятность того, что она останется занятой более
одной секунды, равна q
Вероятность перехода в свободное состояние равна
p
Теперь эти вероятности не зависят от того, как долго была занята линия.
Если же время нельзя считать дискретным, то вместо геометрического
распределения берут показательное. Это единственное распределение,
имеющее марковский характер

19. Показательное время обслуживания

.
Показательное время обслуживания
Вероятность того, что разговор, происходящий в момент времени s,
продлится до (s + t), не зависит от предыдущего разговора тогда,
когда вероятность того, что разговор продлится более t единиц
времени, равна
e t
Показательное время обслуживания – нулевой член распределения Пуассона,
т.е. времени ожидания первого изменения
Входной поток (поток требований) имеет пуассоновский тип с параметром