Математические схемы вероятностных автоматов.

Введение

Понятие вероятностного автомата (ВА) впервые было сформулировано в 1963 г. в основополагающей работе М. Рабина. Данное понятие возникло как синтез понятий конечного детерминированного автомата и цепи Маркова и было предназначено для построения математических моделей динамических систем, в которых присутствует неопределённость, описываемая статистическими закономерностями.
Вероятностный автомат является примером дискретно-стохастической функциональной модели исследуемой системы. Сущность дискретизации времени при этом подходе остается аналогичной рассмотренным ранее конечным автоматам, но появляется возможность учета влияния случайных факторов на развитие моделируемых процессов.
Актуальность работы объясняется тем, что применение схем вероятностных автоматов имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.
Целью работы является описание математической схемы вероятностных автоматов.
Задачи работы: разбор понятия и характеристики математической схемы вероятностного автомата, анализ примеров математических схем вероятностных автоматов.

Понятие и характеристика математической схемы вероятностного автомата

В общем виде вероятностный автомат (англ. probabilistic automat) можно определить, как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически.
Cуществуют и другие модели динамических систем со случайным поведением, например скрытые марковские модели (hidden Markov models), байесовские сети (Bayesian networks), вероятностные графические модели, марковские решающие процессы (Markov decision processes), вероятностные I/O автоматы (probabilistic I/O automata). Все эти модели являются частными случаями исходного понятия ВА общего вида. Наряду с перечисленными выше моделями в последние годы изучаются модели динамических систем со случайным поведением, переходы в которых могут быть ассоциированы не только с вероятностями их выполнения, но и с модальностями must и may, которые позволяют существенно усилить выразительные возможности этих моделей по сравнению с другими упомянутыми выше моделями.
Основные концепции и методы, относящиеся к таким моделям, содержатся в статье. Также изучаются и другие обобщения понятия ВА, в частности вероятностные сети Петри, ВА с непрерывным временем, вероятностные процессные алгебры. изучается средняя длина кода Хафмана как случайная величина, зависящая от случайного набора вероятностей кодируемого алфавита и устанавливается асимптотика математического ожидания средней длины при увеличении мощности алфавита.
Также предложена математическая модель случайного блуждания по целочисленной решетке в прямоугольной области на плоскости для представления двух-приоритетной очереди в виде двух последовательных FIFO-очередей, на основе этой модели предложен алгоритм, который позволяет для заданных вероятностей выполнения основных операций с приоритетной очередью находить оптимальный способ перераспределения памяти после переполнения одной из FIFO-очередей. В
Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары , где  и -элементы входного подмножества X и подмножества состояний Z соответственно

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

Элементы из F …
…

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

При этом и, где  и - вероятности перехода Р-автомата в состояние и появления выходного сигнала при условии, что Р-автомат находился в состоянии  и на его вход поступил входной сигнал .
Если для всех k и j имеет место соотношение , то такой Р-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.
Пусть теперь определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы. Другими словами, пусть каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:
Элементы из Y …
…
Здесь , где  - вероятность появления выходного сигнала при условии, что Р-автомат находился в состоянии .
Если для всех k и i имеет место соотношение , то такой Р-автомат называется вероятностным автоматом Мура.
Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым .Частным случаем Р-автомата, задаваемого как , являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминировано. Если выходной сигнал Р-автомата определяется детерминировано, то такой автомат называется Y-детерминированным вероятностным автоматом. [1]
Аналогично, Z детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.
Матрицы, соответствующие конечным случайным функциям.
СФ называется конечной (КСФ), если её область определения и область значений являются конечными множествами.
Пусть задана КСФ f : X →r Y , и на X и Y заданы упорядочения их элементов, которые имеют вид (x1, . . . .xm) и (y1, . . . , yn) соответственно. Тогда f можно представить в виде матрицы (обозначаемой тем же символом f)

Будем отождествлять каждую КСФ f с соответствующей ей матрицей. Будем предполагать, что для каждого множества X, являющегося областью определения или областью значений какой-либо из рассматриваемых КСФ, на X задано фиксированное упорядочение его элементов. Таким образом, для каждой рассматриваемой КСФ соответствующая ей матрица определена однозначно. Согласно определению произведения матриц, из (2) следует, что матрица fg является произведением матриц f и g.
Вероятностным распределением (или просто распределением) на множестве X называется произвольная СФ ξ вида
ξ : 1 → X
где 1 – множество, состоящее из одного элемента, который мы будем обозначать символом e