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

ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (Р-СХЕМЫ)

Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы Я. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным в § 2.3 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.

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

В общем виде вероятностный автомат (англ, probabilistic automat) можно определить, как дискретный по-тактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически.
Применение схем вероятностных автоматов (P-схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворящих заданным ограничениям.
Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (х_ь z,)_t где х_{ и z_s — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции q> и ф, то с их помощью осуществляются отображения G-+Z и G-* У, то говорят, что F= Х_у У, <р, i/r) определяет автомат детерминированного типа.
Введем в рассмотрение более общую математическую схему. Пусть Ф — множество всевозможных пар вида (z_ki yj), где y_t — элемент выходного подмножества У. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:

При этом

где bkj — вероятности перехода автомата в состояние г_к и появления на выходе сигнала у_)у если он был в состоянии г₃ и на его вход в этот момент времени поступил сигнал Хь Число таких распределений, представленных в виде таблиц, равно числу элементов множества <7. Обозначим множество этих таблиц через В. Тогда четверка элементов Р=^_у Х_у У, В) называется вероятностным автоматом (Р-автоматом).
Пусть элементы множества (У индуцируют некоторые законы распределения на подмножествах У и Z, что можно представить соответственно в виде:

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

Здесь

где 5, — вероятность появления выходного сиг
нала у₍ при условии, что г-автомат находился в состоянии г*.