Лекция 8. Дискретно – стохастические модели

(Р-схемы)

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

Применение схем вероятностных автоматов имеет важное значение для проектирования дискретных систем, в которых проявляется статистически закономерное случайное поведение.

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

Функция переходов вероятностного автомата определяет не одно конкретное состояние, а распределение вероятностей на множестве состояний (автомат со случайными переходами). Функция выходов также есть распределение вероятностей на множестве выходных сигналов (автомат со случайными выходами).

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

элементы из Ф ...

... ... ,

где – вероятности перехода автомата в состояние z_k и появления на выходе сигнала y_j , если он был в состоянии z_s и на его вход в этот момент времени поступал сигнал x_i.

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

.

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

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

Марковские последовательности, согласно теореме Маркова, – это последовательность случайных величин, для которой справедливо выражение

,

где N – количество независимых испытаний; D – дисперсия.

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

Y-детерминированный Р-автомат можно задать двумя таблицами: переходов (табл. 1) и выходов (табл.2).

Таблица 1

Таблица 2

где P_ij – вероятность перехода Р-автомата из состояния z_i в состояние z_j, при этом

.

Таблицу 1 можно представить в виде квадратной матрицы размерности . Такую таблицу будем называть матрицей переходных вероятностей или просто матрицей переходов Р-автомата, которую можно представить в компактной форме:

.

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

где d_k – вероятность того, что в начале работы Р-автомат находится в состоянии z_k, при этом

.

Итак, до начала работы Р-автомат находится в состоянии z₀ и в начальный (нулевой) такт времени меняет состояние в соответствии с распределением D. После этого смена состояний автомата определяется матрицей переходов Р. С учетом z₀ размерность матрицы Р_р следует увеличить до , при этом первая строка матрицы будет (d₀,d₁,d₂,...,d_k), а первый столбец будет нулевым.

Пример.Y-детерминированный Р-автомат задан таблицей переходов:

Таблица 3

и таблицей выходов

Таблица 4

Z
Y

С учетом таблицы 4 граф переходов вероятностного автомата представлен на рис. 1.

Рис. 1. Граф переходов

Требуется оценить суммарные финальные вероятности пребывания этого автомата в состоянии z₂ и z₃, т.е. когда на выходе автомата появляются единицы.

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

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

В результате получаем систему уравнений:

(3.7)

К данной системе следует добавить условие нормировки:

(3.8)

Теперь решая систему уравнений (3.7) совместно с (3.8), получаем:

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

.

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