1.4. ОСНОВНЫЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧ СРЫВА СЛЕЖЕНИЯ КОНЕЧНОГО АВТОМАТА

Срыв слежения конечного автомата со случайными переходами происходит при выходе точки, описывающей состояние этого автомата, из некоторого подмножества состояний . В общей задаче срыва слежения предполагается, что случайная траектория точки после выхода из может снова пройти через это подмножество. В частной задаче событие возврата точки в считается невозможным.. При анализе частной задачи рассматриваются вопросы первого выхода из

Частная задача [70, 76]. Вероятность характеризует возможность срыва за заданное число шагов, равное n. Она равна сумме вероятностей попадания точки на шаге в подмножества поглощения

Вероятность задается так:

Чтобы было распределением вероятностей, необходимо выполнение краевых условий

При этом

На основании спектрального представления (1.3.8) для матрицы вероятностей поглощающе цепи Маркова, описывающей поведение конечного автомата со случайными переходами, получаем суммарный и разностный законы распределения вероятностей моментов времени срыва слежения:

где первая компонента вектора .

Рекуррентное соотношение (1.3.9) задает вероятность срыва слежения за шагов следующим образом:

Для цепи с одним поглощающим состоянием получим

где — коэффициенты характеристического полинома матрицы вероятностей переводов, взятые с обратным знаком. Коэффициенты f (с обратным знаком) получаются при исключении корня из исходного характеристического полинома.

Так как рекуррентное соотношение (1.3.9) сохраняет свой вид и для векторных разностей, то

и для цепи с одним поглощающим состоянием

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

где

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

то

где

Общая задача [71, 76]. В данном случае полагается, что срыв слежения происходит, если точка покидает подмножество на время, большее . В общей задаче о срыве за пределами подмножества эргодические классы отсутствуют. В этом случае все состояния марковской цепи будут сообщающимися, а сама цепь — регулярной. Если при решении частной задачи необходимо было найти характеристики первого достижения границы, то в общей задаче основное внимание уделяется событию возвращения в заданное подмножество состояний за время, не превышающее заранее определенного.

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

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

Краевые условия в общей задаче имеют вид

где вероятность срыва за шагов.

Если коэффициенты характеристического полинома матрицы то суммарное распределение вероятностей срыва запишется в виде

Аналогично разностное распределение вероятностей будет иметь вид