9 Вероятностный автомат Мили

Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, которые можно представить соответственно в виде:

Таблица 2

Элементы из Y	•••	y1	y2	•••	YJ-1	y J
	•••	q1	q2	•••	q J-1	q J
Элементы из Z	•••	z1	z2	•••	zK-1	zK
	•••	1	2	•••	 K-1	 K

При этом и (4) вероятности перехода Р-автомата в состояние z_k и выдачи выходного сигнала y_k при условии, что Р-автомат находился в состоянии z_S и на его вход поступил входной сигнал x_i. Если для всех k и j имеет место соотношение , (5) то такой автомат называется вероятностным автоматом Мили.

Представленное тре­бование означает выполнение условия независимости распределе­ний для нового состояния Р-автомата и его выходного сигнала.

10 Вероятностный автомат Мура

Пусть выходной сигнал Р-автомата зави­сит лишь от того состояния, в котором находится автомат в данном такте работы, и каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:

Таблица 3

Элементы из Y	•••	yl	у2	•••	yK-1	yK
zk	•••	s1	S2	•••	SI-1	SI

Здесь , (6) где S_i — вероятность появления сигнала на выходе y_i при условии, что Р-автомат находился в состоянии z_k. Если для всех k и j имеет место соотношение , (7) то такой автомат называется вероятностным автоматом Мура.

Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал будет детерминированным (определенным). Если состояние Р-автомата является детерминированным, то такой автомат называется Y-детерминированным вероятност­ным автоматом.

Аналогично, Z-детерминированным вероятност­ным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

Рассмотрим пример Y-детерминированного Р-автомата.

Пусть Y-детерминированный Р-автомат задан таблицей переходов:

где p_ij – вероятность перехода автомата из состояния z_i в состояние z_j . При этом _. (8)

Таблица выходов представлена следующим образом:

Таблица 5

Z . . . z1	z2 . . . zK-1	zK
Y . . . уi1	уi2 . . . yi K-1	yiK

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

. (9)

Для полного описания Y-детерминированного Р-автомата необходимо задать началь­ное распределение вероятностей вида

Таблица 6

Z . . . . z1	z2 . . . . zk-1	zk
D . . . . d1	d2 . . . . dK-1	dK

где d_K — вероятность того, что в начале работы P-автомат находится в состоянии z_k . При этом . (10)

Будем полагать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z₀, в нулевом такте времени меняет свое состояние в соот­ветствии с распределением D. Дальнейшая смена состояний Р-автомата определяет­ся матрицей переходов Р_Р. Информацию о начальном состоянии Р-автомата удобно внести в матрицу Р_Р, увеличив ее размерность до . При этом первая строка такой матрицы, сопоставляемая состоянию z₀, будет иметь вид (0, d₁, d₂, ... ..., d_K), а первый столбец будет нулевым:

(11)

Описанный Y-детерминированный Р-автомат можно задать в виде ориентиро­ванного графа, вершины которого сопоставляются состояниям автомата, а дуги — возможным переходам из одного состояния в другое. Дуги имеют веса, соответст­вующие вероятностям перехода р_ij, а около вершин графа пишутся значения выход­ных сигналов, индуцируемых этими состояниями.

Рассмотрим следующий пример.

Пусть Y-детерминированный Р-автомат задан матрицей:

(11)

Граф переходов имеет вид (рис.1):

Рис. 1

(откуда выходит – сверху-вниз, куда направлена – слева-направо по графу – это цифры на линиях, а стрелка ставится, если на пересечении двух z стоит число)

Требуется оценить суммар­ные финальные вероятности пребывания этого Р-автомата в состояниях z₂ и z₃.

При использовании аналитического подхода можно записать известные соот­ношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. Начальное состояние z₀ можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероят­ностей. Тогда имеем матрицу финальных состояний:

, (12)

, (13)

где c_k - финальная вероятность пребывания Р-автомата в состоянии z_k.

Получаем систему уравнений (14)

Добавим к этим уравнениям условие нормировки: с₁+с₂+с₃+с₄=1. (16)

Тогда, решая систему уравнений, получим с₁ = 5/23, с₂=8/23, c₃ = 5/23, с₄ = 5/23. (17)

Таким образом, с₂+с₃= 13/23 =0,5652. (18)

Другими словами, при бесконечной работе заданного в этом примере Y-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.

Подобные Р-автоматы могут испо­льзоваться как генераторы марковских последовательностей, которые необхо­димы при построении и реализации про­цессов функционирования систем или воздействий внешней среды.

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

Бехтин, вопрос 11,12,13.

Системы массового обслуживания (Q-схемы). (Непрерывно-стохастические модели).

Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели).

Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позиций полной определенности в настоящем и будущем.

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

Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности.