-
Дискретные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
Если число состояний системы конечно (или счетно), а переходы из одного состояния в другое осуществляются скачком (то есть время перехода из состояния в состояние мало, а время пребывания в одном состоянии продолжительно), то данная система является системой с дискретными состояниями.
Система может работать в дискретном или в реальном времени. При дискретном времени есть тактируемые сигналы, переход возможен только в определенные моменты времени. При реальном времени переход возможен в любой момент времени.
Если переходы в системе возможны только в определенные, заранее фиксированные моменты времени – значит, данная система является системой с дискретным временем.
Дискретная марковская цепь – это марковский случайный процесс с дискретными состояниями и временем.
ДМЦ часто представляется в виде графа, вершины обозначаются, как Si, дуги – возможные переходы из Si в Sj.
Каждой дуге соответствует переходная вероятность Pi,j(K) – это условная вероятность того, что система находится в состоянии Sj на К-том шаге при условии, что она находилась в состоянии Si на К-1 шаге.
Марковская цепь – однородная, если переходные вероятности не зависят от номера шага, иначе – неоднородная.
Полным описанием однородной марковской цепи является матрица переходных вероятностей и вектор начального распределения вероятностей для всех состояний в момент t = 0.
Для неоднородной – такая же матрица для каждого шага K и вектор начального распределения вероятностей.
В неоднородной ДМЦ одна вероятность на нулевом шаге равна 1, все остальные равны 0. Общая формула вероятности:
Цепи бывают эргодическими и разложимыми.
Эргодическая
цепь описывается сильносвязанным
графом, в такой системе возможен переход
из любого Si
в любое Sj
за конечное число шагов. При достаточно
большом
наступает установившийся режим (то есть
вероятности состояний системы Pi
не зависят от времени и от распределения
начальных вероятностей системы, Pi
= const). Pi
харакетризует среднюю долю времени,
которое система находится в состоянии
Si.
Разложимые цепи содержат невозвратные состояния (поглощающие), из поглощающего состояния нельзя перейти ни в какие другие состояния.
Для определения вероятностей стационарных состояний эргодического процесса необходимо составить n линейных алгебраических уравнений с n неизвестными:
Систему уравнений удобно составлять по размеченному графу состояний. Тогда в данной системе уравнений слева стоят вероятности нахождения в i-той вершине, справа – сумма, число слагаемых – число входящих в i-тую вершину дуг.
В таком графе представлены начальная вершина, операторные вершины и конечная вершина.
Теория ДМЦ применяется для анализа и синтеза вычислительных систем. Наиболее типичная задача – оценка трудоемкости алгоритмов. Алгоритмы задаются графом, вершины являются операторами алгоритма, дуги – связи между операторами. [??????? обоснование]
[В С П О М Н И М]
Математическое ожидание для непрерывной случайной величины:
Дисперсия:
