Вероятностные автоматы

Вероятностные (стохастические) автоматы представляют собой конечные автоматы со случайными управлениями, у которых, как правило, учитываются только состояния.

Пример:

модель системы, которая случайным образом может оказаться в одном из технических состояний:

исправное, неисправное, поиск неисправности, ремонт и т.д.

Марковские цепи с дискретным временем

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

t + ∆t зависит только от текущего состояния в момент времени t.

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

множество состояний

S s1 ,..., sk

матрица вероятностей переходов

вектор начальных вероятностей

p0 p1(0) ,...pk(0)

Марковские цепи с дискретным временем

Марковская цепь изображается в виде графа, вершины которого соответствуют состояниям цепи и дуги – переходам между состояниями

Пример. Дана матрица вероятностей переходов

Граф:

вектор начальных вероятностей

p0 1,0,0,0,0

Анализ марковских цепей

Результат анализа марковской цепи:

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

каковы установившиеся значения этих вероятностей.
pn p1(n) ,...pk(n)	p0 1,0,...,0

Для расчета вероятностейpиспользуетсяp P уравнение

Колмогорова-Чепмена

n 1 n

			p2	p1 P p0 P2					3
	вероятности состояний вычисляются рекуррентно:
p1 p0		P			p3	p2	P p0	P

pn pn 1 P p0 Pn

pp P

При n→∞ определяютn установившиесяn (финальные)

вероятности

Анализ марковских цепей. Пример.

Вероятностный автомат представлен в виде графа

		1		1	0
	2			2
P		1		1		1
	4			2	4
	0			1	1
				2		2

p p		P (1,0,0) P (	1	,	1	, 0)
1	0	2		2

p	2	p P (					1		,		1	, 0) P (				3	,	1	,	1	)
																		2		8
			1			2				2					8
p1( )				1	p1( )			1		p2( )										p p p 1
				2				4
p( )																				1				2	3
				1	p( )			1		p( )				1	p( )				( )			1		( )	1		( )	1
	2		2		1			2		2			2		3			p2						p1			p3
																							2			4			4
	( )			1	( )			1				( )
p3					p2					p3
				4				2

Марковские процессы

Главное свойство непрерывного марковского процесса – экспоненциальность распределения времени пребывания процесса в каждом из состояний.

Марковский процесс с непрерывным временем переходов можно задать в виде графа или описать системой дифференциальных уравнений.

Расчет характеристик марковских процессов

P1 (t) ( 12 13 ) P1 (t) 21 P2 (t) 31 P3 (t)

P2 (t) 12 P1 (t) ( 21 23 ) P2 (t) 32 P3 (t)

P3 (t) 13 P1 (t) 23 P2 (t) ( 31 32 ) P3 (t)

Pi (t) ij Pj (t) Pi (t) ij
j	j

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

Модель "гибели и размножения"

01P0 10 P1

( 12 10 )P1 01P0 21P2 12 P1 21P2

n 1, n Pn 1 n, m 1Pn
P		01			P															1
1		10				0						P0
						P 01 12															01 12... n 1, n
P 12																01
											P		1						01 12	..
															10			21 10			n, n 1	... 21 10
2			21			1		21 10			0
P n 1, n							P	01 12... n 1, n P
n	n, n 1						n 1		n, n 1			0
											... 21 10

Модели массового обслуживания

Объекты заняты обслуживанием поступающих в общем случае случайных потоков заявок или требований.

Поток событий – последовательность однородных событий, следующих одно за другим в какой-то случайный момент времени

Характеристика потока событий

Характеристика потока событий – интенсивность

—среднее число событий, приходящееся на единицу времени.

может быть постоянной ( = const),

переменной, зависящей от времени t.

•поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик — интенсивнее, чем в другие часы