Теорема Маркова о предельных (финальных) вероятностях

Пусть есть некоторая эргодическая ЦМ. Тогда для нее справедлива такая теорема Маркова.

С увеличением количества шагов n вероятность перехода из состояния в состояние стремится к определенному пределу , который называется финальной вероятностью, то есть

для всех i, j. (6.12)

В матричной форме это записывается так:

. (6.13)

Из (6.12) и (6.13) вытекает, что предел вероятности перехода между любыми двумя состояниями эргодической цепи существует и не зависит от состояния . Иначе говоря,

по прошествии длительного времени вероятность того, что процесс будет находиться в состоянии , не зависит от того, из какого состояния этот процесс начал развиваться. Поэтому говорят, что ЦМ "забывают" свое прошлое.

Кроме того, в эргодических цепях Маркова безусловные вероятности при увеличении n также стремятся к финальным вероятностям .

Режим работы эргодической ЦМ (системы) при достаточно большом значении n называют стационарным режимом ЦМ.

Вычисление финальных вероятностей при известных начальных вероятностях и заданной матрице перехода – важнейшая задача при изучении эргодических ЦМ. Для решения этой задачи можно использовать два алгоритма.

1) Воспользоваться теоремой Маркова, согласно которой возведение матрицы перехода в достаточно высокую степень n должно дать вектор-строку искомых вероятностей. Ясно, что этот алгоритм является чрезвычайно трудоемким.

2) Значительно проще найти эти вероятности решением системы алгебраических уравнений. Согласно формуле полной вероятности можно записать соотношение, справедливое при произвольном значении n

.

При больших значениях n безусловные вероятности равняются финальным вероятностям, поэтому

. (6.14)

Получили систему N алгебраических уравнений с N неизвестными. Чтобы решить эту систему, из (6.14) надо взять N– 1 уравнение и дополнить систему условием нормировки .

Рассмотрим еще два примера.

Первый пример.

В процессе эксплуатации ЭВМ можно рассматривать как некоторую физическую систему с 4-мя возможными состояниями: – ЭВМ полностью исправная; – ЭВМ имеет незначительные неисправности, но может решать задачи; – ЭВМ имеет существенные неисправности и может решать лишь ограниченный класс задач; – ЭВМ полностью вышла из строя. Очевидно, что вместо ЭВМ таким же образом можно рассматривать и другие технические системы (приемные устройства, передающие устройства, каналы связи и др.). В начальный момент времени система полностью исправна. В фиксированные моменты времени осуществляется проверка ЭВМ. Процесс, происходящий в системе, можно рассматривать как однородную цепь Маркова с тремя шагами, которые соответствуют трем проверкам. Матрица вероятностей перехода известна:

.

Нужно найти вероятности состояний ЭВМ после трех проверок.

Решение:

Начнем с построения графа состояний. Граф приведено на рис. 6.3.

Очевидно, что вектор-строка вероятностей начальных состояний имеет вид .

Находим вероятности состояний после первого шага:

; ;

; .

Вероятности состояний после второго шага:

;

;

;

Наконец, искомые вероятности после третьего шага равняются:

;

;

;

Проверим результат на выполнение условия нормировки:

.

Рассмотрим пример использования математического аппарата ЦМ для построения моделей речевых сигналов.

Второй пример.

Большинство звуков языка можно отнести или к вокализованным (гласным), или к невокализованным (согласным). Тогда речевой сигнал в системе связи можно представить как такой, что имеет три состояния: – пауза; – вокализованный и – невокализованный звуки. Необходимо построить модель языкового процесса с этими тремя состояниями на базе однородной ЦМ. Это значит, что надо найти финальные вероятности и .

Решение:

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

В случае, который рассматривается .

Запишем матрицу перехода однородной цепи Маркова для нашего случая.

.

Чтобы найти финальные вероятности, воспользуемся алгоритмом 2). Для этого составим систему трех алгебраических уравнений с тремя неизвестными. Первые два уравнения получим из (6.14) и третье – из условия нормировки.

Осталось решить систему. Воспользуемся ЭВМ и системой MATHEMATICA. Ниже приведен оператор, с помощью которого решена эта система уравнений, и формулы для вычисления финальных вероятностей и . Эти формулы полностью описывают модель исследуемого процесса с тремя состояниями.