Дискретно-стохастические модели

Особенности подхода

Рассмотрим на примере испытания в качестве мат. аппарата теории конечных автоматов (КА) в части её применения к вероятностным (стохастическим) автоматам (probabilistic automat). Вероятностный автомат (P-схемы) – это КА, в которой закономерности смены состояний и формирования выходного сигнала имеют статический характер. Автомат, находящийся в определенном состоянии, при получении определенного входного сигнала может перейти в одно из конечного множества возможных состояний с выдачей одного из конечного множества возможных выходных сигналов. При этом переход в конкретное состояние с выдачей конкретного выходного сигнала трактуется как случайное событие и определяется конкретным значением вероятности наступления этого события.

Введём мат. понятие P-автомата по аналогии с F-автоматом.

Пусть заданы:

• множество входных сигналов X размерностью M с элементами x₁, x₂, …x_m, m=1,M
• множество выходных сигналов Y размерностью L с элементами y₁, y₂,…y_l, l=1,L
• множество состояний Z размерностью I с элементами z₁, z₂, …x_i, i=1,I

Введём в рассмотрение: новое множество G размерностью K=I*M (k=1,K), элементами которого являются пары (x_m, z_i)

– новое множество Ф размерностью S=I*L (s=1,S), элементами которого являются пары (z_i,y_l).

Для F-автомата характерно, что каждая пара элементов (x_m, z_i) однозначно отображается с помощью функций переходов Y(z,x) и выходов Y(z,x) в подмножество Z и Y

В случае P-автомата каждая пара (x_m, z_i) индуцирует на множестве Ф пар элементов (z_i,y_l) некоторый закон распределения следующего вида:

Элементы из Ф={z_j,y_l}, j=1,I

При этом

где b_jl – векторы перехода автомата в состояние z_j и выдачей y_l на выходе, если он был в состоянии z_i и на его вход поступил сигнал x_m.

Число распределений, представленных в виде таблиц, равно числу К элементов множества G. Обозначим множество таких распределений размерностью К через B. Тогда четвертка элементов P=<Z,Y,X,B> называется вероятностным автоматом (P-автоматом)

Если для Р-автомата элементы множества {(x_m, z_i)} индуцируют независимые законы распределения на подмножествах Y и Z, что можно представить в виде:

Элементы из Y: y1, y2,…yl => C1, C2, …; (x_m, z_i) – k-й элемент множества G

Элементы из Z: z1,z2,…zj => d1, d2,…; (x_m, z_i)

где ,

b_jl, C_l, d_j – условные вероятности, то такой Р-автомат называется вероятностным автоматом Мили.

Если выходной сигнал Р-автомата зависит лишь от его состояния, что можно представить в виде:

Элементы из Y: y1, y2,…yl => C1, C2, …; z_i – i-й элемент множества G

Элементы из Z: z1,z2,…zj => d1, d2,…; (x_m, z_i)

где ,

b_jl, C_l, d_j – условные вероятности, то такой Р-автомат называется вероятностным автоматом Мура.

Частные случае Р-автоматов соответствуют рассмотренным выше видам F-автоматов. При этом частными случаями всех видов вероятностных автоматов являются:

Z-детерминированные и Y-детерминированные Р-автоматы

Z-детерм. У-детерм. Y-статист.

Y-детерм. У-стат., Y- детерм.

Рассмотрим нетабличные способы задания Y-детерминированного автономного Р-автомата.

При матричном способе такой Р-автомат задается матрицей переходных вероятностей.

||p_ij||, который содержит информацию о вероятностях перехода автомата за один шаг из каждого i-состояния в каждое последующее j-ое, а также вариантом выходов ||y_i||

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

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

Зададим графически Y-детерм. автономный Р-автомат, у которого множество Z={z1,z2,z3,z4,z5}, Y={y1,y2,y3}, а

Если модель процесса функционирования объекта модели представима в форме Y-детерминированного автономного Р-автомата, то такая модель называется также дискретной Марковской моделью.