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

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

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

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

Введем математическое понятие Р-автомата, используя понятия для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi, zs), где xi и zs — элементы входного подмножества X и подмножества состояний Z соответственно.

Определение 3.1. Если существуют две такие функции φ и ψ, что с их помощью осуществляются отображения  G→Z  и  G→Y,  то говорят, что F = <Z, X, Y, φ, ψ> определяет автомат детерминированного типа.

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

При этом  , где bkj — вероятности перехода автомата в состояние zk и появления на выходе сигнала  yi,  если он был в состоянии zs, и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P = <Z, X, Y, B> называется вероятностным автоматом (Р-автоматом).

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

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

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

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

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

Возможные приложения. Если для всех  k  и  i  имеет место соотношение  zksi = bki, то такой Р-автомат называется вероятностным автоматом Мура. Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым F = <Z, X, Y, φ, ψ>.  Частным случаем Р-автомата, задаваемого как P = <Z, X, У, B>, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно.


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

Пример 3.4. Рассмотрим Y-детерминированный Р-автомат, который задан таблицей переходов (см. табл. 3.6) и таблицей выходов:

В этих таблицах  pij — вероятность перехода Р-автомата из состояния zi в состояние zj. При этом, как и ранее,.

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

Таблица 3.6

Для описания Y-детерминированного Р-автомата необходимо задать начальное распределение вероятностей вида

Здесь dK — вероятность того, что в начале работы Р-автомат находится в состоянии k. При этом  .

Будем считать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z0 и в нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний Р-автомата определяется матрицей переходов РР. Информацию о начальном состоянии Р-автомата удобно внести в матрицу Рр, увеличив ее размерность до (K+1) х (К+ 1). При этом первая строка такой матрицы, сопоставляемая состоянию z0, будет иметь вид (0, dl, d2, …, dk), а первый столбец будет нулевым.

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

Пример 3.4. Пусть задан Y-детерминированный Р-автомат

 

;          .

На рис. 3.4 показан граф переходов этого вероятностного автомата. Требуется оценить суммарные финальные вероятности пребывания этого Р-автомата в состояниях z2 и z3.

При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние z0 можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеем

; ,

где  сk – финальная вероятность пребывания Р-автомата в состоянии zk.

Получаем систему уравнений

Добавим к этим уравнениям условие нормировки  c1 + с2 + с3 + с4 = 1. Тогда, решая систему уравнений, получим с1 = 5/23, с2 = 8/23, с3 = 5/23, с4 = 5/23. Таким образом, с2 + с3 = 13/23 =0,5652. Другими словами, при бесконечной работе заданного в этом примере Y-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.

Подобные Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е.

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