Аналитическое определение вероятностных автоматов
6.1.1. Формальное задание и классификация. Вероятностные автоматы (ВА) относятся к дискретно-стохастическому классу моделей. Данный тип моделей служит инструментом изучения динамических систем, имеющих стохастическую природу функционирования с дискретным временем. ВА является типичным представителем таких систем (probabilistic automat) и носит название P-схемы или P-автомата. В общем виде такой автомат является потактным преобразователем информации с памятью, функционирование которого может быть описано статистически.
Математический аппарат ВА применим для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения возможностей таких систем и обоснования границ целесообразности их использования, а также при решении различных задач синтеза. Аппарат ВА применяется также для моделирования дискретно-стохастических объектов, у которых подача входных параметров, изменение состояния и формирование выходных параметров осуществляется в дискретные моменты времени ti (t0,t1,...,ti…). Состояние объекта определяется через предшествующие состояния и входной параметр. Выходной параметр определяется через состояние в данном такте времени, состояние в предшествующем такте, а также через входной параметр.
Для формального описания ВА следует задать распределение начальных состояний, множество входных параметров Х={х1,х2,...,хm}, множество состояний Z={z1,z2,...,zn}, множество выходных параметровY={y1,y2,...,yr}. Элементы множества Х,Z,Y называют входным, внутренним и выходным алфавитом.
Определение. Вероятностным автоматом называется математическая схема, которая задается следующим набором [7,14]:
ВА=<Z,Y,Р0,{Р(zt,yt/zt-1,хt)}>,
где Р0 - распределение начальных состояний, Р0=||
||,- вероятность того, что в такте времени t0 автомат будет находиться в состоянии zi; Р=||Р(zt,yt/zt-1,хt)||- стохастическая матрица, в которой Р(zt,yt/zt-1,хt)=Р{z(t)=zt, y(t)=yt/z(t-1)=zt-1, х(t)=хt} -условная вероятность того, что в такте времени t автомат будет в состоянии zt, на выходе будет иметь параметр ytпри условии, что в такте t-1автомат был в состоянии zt-1, а на вход был подан параметр хt. При моделировании следует определить функции переходов и выходов. Функцию переходов задают в виде стохастической матрицы ||Р{zt(t)=z(t)/zt-1,хt}||.
Функция выходов определяет выходные параметры и задается в виде стохастической матрицы ||Р(yt/zt-1,хt,zt)||, в которой Р(yt/zt-1,хt,zt)=Р{y(t)=yt/z(t-1)=zt-1,х(t)=хt, z(t)=zt}.
Определим условную вероятность Р(yt/zt-1,хtzt):
Р(zt,yt/zt-1,хt)=Р(zt/zt-1,хt)Р(yt/zt-1,хt,zt).
Просуммируем правую и левую части по всем значениям yiи получим
Сумма в правой части равна единице, так как это сумма вероятностей полной группы событий. Тогда вероятность Р(yt/zt-1,хt,zt) определится формулой
.
6.1.2. Классификация ВА.Классификация ВА зависит от способов определения вероятности Р(yt/zt-1,хt,zt)функции выходов и вероятности Р(yt/zt-1,хt)функции переходов.
Вероятностный автомат называется автоматом первого рода, если функция выходов зависит только от предшествующего состояния и входного параметра в данном такте времени:
Р(yt/zt-1,хt,zt)=Р(yt/zt-1,хt),(автомат Мили).
Вероятностный автомат называется автоматом второго рода, если функция выходов зависит только от состояния и входного параметра в данном такте времени:
Р(yt/zt-1,хt,zt)=Р(yt/хt,zt).
Вероятностный автомат называется правильным, если функция выходов зависит только от состояния в предшествующем такте и состояния в текущем такте времени:
Р(yt/zt-1,хt,zt)=Р(yt/zt-1,zt).
Существует правильный ВА первого рода, у которого
Р(yt/zt-1,хt,zt)=Р(yt/zt-1),
и правильный вероятностный автомат второго рода, у которого
Р(yt,zt-1,хt,zt)=Р(yt/zt), (автомат Мура).
Вероятностный автомат называется автоматом с детерминированной функцией перехода, если состояние в каждый такт времени однозначно определяется через предшествующее состояние и входной параметр:
Вероятностный автомат будет называться автоматом с детерминированной функцией выходов, если выходной параметр однозначно задается через предшествующее и текущее состояние и входной параметр:
Вероятностный автомат первого рода с детерминированной функцией переходов называется автоматом со случайными реакциями.
Вероятностный автомат первого рода с детерминированной функцией выходов называется марковским.
Правильный ВА второго рода с детерминированной функцией выходов называется автоматом с отмеченными состояниями. Каждому состоянию соответствует свой входной параметр. Причем, если у этого ВА стохастическое отображение элементов множества Z в элементы множества Y задается взаимно однозначно, то ВА называется абстрактным и для него достаточно рассматривать алфавит внутренних состояний. Абстрактный ВА задается в виде набора
ВА=<Х,Z,Р0{Р(zt/zt-1,хt}>.
Если мощность множества Z равна единице, то такой автомат называется автоматом без памяти.
Если мощность множества Х равна единице, то такой автомат называется автономным.
Автономный абстрактный ВА называется дискретной цепью Маркова и задается в следующем виде:
ВА=<Z,Р0{Р(zt/zt-1)}>.