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

 

Основные соотношения

В общем виде вероятностный автомат (англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически. Применение схем вероятностных автоматов ( -схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.

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

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

 

Элементы из Ф  

         

При этом , где   - вероятности перехода автомата в состояние   и появления на выходе сигнала   если он был всостоянии   и на его вход в этот момент времени поступил сигнал . Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов   называется вероятностным автоматом (Р - автоматом).

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

 

Элементы из Y

Элементы из Z

 

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

Если для всех   и  имеет место соотношение , то такой Р - автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р - автоматаи его выходного сигнала.

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

Элементы из

 

 

Здесь , где   - вероятность появления выходного сигнала   при условии, что Р - автоматнаходился в состоянии .