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

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

Рассмотрим задачу об осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 10.5).

Осел стоит между двумя копнами: "Рожь" и "Пшеница" (рис. 10.5). Каждую минуту он либо передвигается на десять метров в сторону первой копны (с вероятностью ), либо в сторону второй копны (с вероятностью ), либо остается там, где стоял (с вероятностью ); такое поведение называется одномерным случайным блужданием. Будем предполагать, что обе копны являются "поглощающими" в том смысле, что если осел подойдет к одной из копен, то он там и останется. Зная расстояние между двумя копнами и начальное положение осла, можно поставить несколько вопросов, например: у какой копны он очутится с большей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попасть туда?

Рис. 10.5.

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

Пусть - вероятность того, что он переместится из в за одну минуту. Например, и . Эти вероятности называются вероятностями перехода , а -матрицу называют матрицей перехода . Заметим, что каждый элемент матрицы неотрицателен и что сумма элементов любой из строк равна единице. Из всего этого следует, что - начальный вектор -строка, определенный выше, местоположение осла по прошествии одной минуты описывается вектором-строкой , а после минут - вектором . Другими словами, -я компонента вектора определяет вероятность того, что по истечении минут осел оказался в .

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

Нас будет интересовать следующее: можно ли попасть из одного данного состояния в другое, и если да, то за какое наименьшее время. Например, в задаче об осле из в можно попасть за три минуты и вообще нельзя попасть из в . Следовательно, в основном мы будем интересоваться не самими вероятностями , а тем, положительны они или нет. Тогда появляется надежда, что все эти данные удастся представить в виде орграфа , вершины которого соответствуют состояниям, а дуги указывают на то, можно ли перейти из одного состояния в другое за одну минуту. Более точно, если каждое состояние представлено соответствующей ему вершиной).

Однородной называют цепь Маркова, для которой условная вероятностьперехода из состоянияв состояниене зависит от номера испытания. Для однородных цепей вместо
используют обозначение
.

Примером однородной цепи Маркова могут служить случайные блуждания. Пусть на прямой Oxв точке с целочисленной координатойx=nнаходится материальная частица. В определенные моменты времени
частица скачкообразно меняет свое положение (например, с вероятностьюpможет сместиться вправо и с вероятностью 1 –p– влево). Очевидно, координата частицы после скачка зависит от того, где находилась частица после непосредственно предшествующего скачка, и не зависит от того, как она двигалась в предшествующие моменты времени.

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

Переходные вероятности. Матрица перехода.

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

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

, где представляют вероятности перехода за один шаг.

Отметим некоторые особенности матрицы перехода.

Равенство Маркова

Обозначим через
вероятность того, что в результатеnшагов (испытаний) система перейдет из состоянияв состояние. Например,
- вероятность перехода за 10 шагов из третьего состояния в шестое. Отметим, что приn= 1 эта вероятность сводится просто к переходной вероятности
.

Возникает вопрос, как, зная переходные вероятности
, найти вероятности перехода состоянияв состояниезаnшагов. С этой целью вводится в рассмотрение промежуточное (междуи) состояниеr. Другими словами, полагают, что из первоначального состояниязаmшагов система перейдет в промежуточное состояниеrс вероятностью
, после чего за оставшиесяn–mшагов из промежуточного состоянияrона перейдет в конечное состояниес вероятностью
. Используя формулу полной вероятности, можно показать, что справедлива формула

Эту формулу называют равенством Маркова .

Зная все переходные вероятности
, т.е. зная матрицу переходаиз состояния в состояние за один шаг, можно найти вероятности
перехода из состояние в состояние за два шага, а значит, и саму матрицу перехода, далее – по известной матрице- найтии т.д.

Действительно, полагая в равенстве Маркова n= 2,m= 1 получим

или
. В матричном виде это можно записать как
.

Полагая n=3,m=2, получим
. В общем случае справедливо соотношение
.

Пример . Пусть матрица переходаравна

Требуется найти матрицу перехода
.

Умножая матрицу саму на себя, получим
.

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

Здесь через
обозначена вероятность нахождения системы в состояниив начальный момент времени. В частном случае, если начальное состояние системы в точности известно (например
), то начальная вероятность
, а все остальные равны нулю.

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

.

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

где - вероятность того, что прибор останется в исправном состоянии;

- вероятность перехода прибора из исправного в неисправное состояние;

- вероятность перехода прибора из неисправного в исправное состояние;

- вероятность того, что прибор останется в состоянии "неисправен".

Пусть вектор начальных вероятностей состояний прибора задан соотношением

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

Решение : Используя матрицу перехода, определим вероятности состояний после первого шага (после первых суток):

Вероятности состояний после второго шага (вторых суток) равны

Наконец, вероятности состояний после третьего шага (третьих суток) равны

Таким образом, вероятность того, что прибор будет находиться в исправном состоянии равна 0,819, и того, что в неисправном – соответственно 0,181.

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

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

В процессе функционирования система сервиса принимает на я-м шаге то или иное состояние с безусловной вероятностью

В некоторых случаях эти вероятности не изменяются для каждого состояния от шага к шагу, т.е.

Однородная цепь Маркова, для которой вероятности состояния одинаковы, т.е. не зависят от п, называется стационарной. В противном случае цепь называется нестационарной. Вероятность состояний называется стационарной вероятностью состояний.

Отметим, что обратная цепь...,5 ,S„,S n l ,... стационарной марковской цепи...,5 j ,S n ,S х ,... также является стационарной цепью Маркова . Стационарная цепь Маркова обратима, если и только если существует набор положительных чисел p(j), сумма которых равна 1, удовлетворяющих условиям баланса

для всех состояний.

Для однородной стационарной цепи справедлива формула

которая показывает, что на каждом шаге вероятности состояний стационарной цепи Маркова не изменяются и перемножение на матрицу переходных вероятностей не дает никакого эффекта. Как видно, вектор в (12.32) является собственным (неподвижным) вектором матрицы П 5 , принадлежащим характеристическому числу А,=1. Матрица П 5 будет положительной.

Часто на первых шагах система ведет себя как нестационарная, а после некоторого числа шагов приобретает свойства стационарности. Стационарный режим работы системы называют установившимся режимом, а нестационарный - переходным режимом.

Для цепи Маркова с конечным числом состояний при выполнении условия n rk {п) > 0, г, к = 1, К, начиная с некоторого п существуют предельные (финальные или стационарные) вероятности состояний

Следовательно,

Условие: , означает, что П является матрицей

вероятностей перехода регулярной цепи. В таком случае матрицы П" сходятся к некоторой матрице П,:

где величины , называются предельными, или финаль

ными, переходными вероятностями. Отсюда

В то же время

Объединяя два последних уравнения, получаем (12.32).

Если в качестве вектора начальных вероятностей Р т (О)для однородной цепи Маркова выбрать собственный вектор Р/ стохастической матрицы, то цепь Маркова стационарная начиная с момента t 0 .

Строки П у образуют одинаковый вероятностный вектор Р/, компоненты которого положительны. Матрица П у также является стохастической:

Так как строки П у одинаковы, то при умножении слева на любой вероятностный вектор получается, согласно (12.7), строка матрицы. Следовательно, финальные вероятности не зависят от начального состояния.

Стохастическую матрицу П и соответствующую ей однородную цепь Маркова называют правильной, если у матрицы нет характеристических чисел, отличных от единицы и равных по модулю единице, и регулярной, если дополнительно единица является простым корнем характеристического уравнения матрицы П .

Предельные переходные вероятности существуют только у правильных однородных цепей Маркова.

Характеристическое число стохастической матрицы всегда лежит в круге | А|

Если матрица П 5 существует, то желательно вычислить ее без нахождения степени матрицы П" и ее предела lim П" = П°°.

п -*? оо

Для правильной матрицы существует матрица П, которую можно вычислить по формуле :

где С(А) = (А1- л) -1 ср(А) - приведенная присоединенная матрица; ср(А) - минимальный многочлен правильной матрицы; ср"(Х) - производная многочлена.

Для регулярной матрицы ф(А) = Д(А) и С(Х) = В(А). Следовательно,

где - присоединенная матрица; А(Х) - характеристический многочлен регулярной матрицы.

Рассмотрим регулярную цепь Маркова с двумя состояниями с матрицей переходных вероятностей (12.28). Вычисленные характеристические числа матрицы (12.29) различны. Существует только одно характеристическое число, равное 1, и оно является простым (не кратным) корнем характеристического уравнения (12.29). Для вычисления финальных вероятностей используем ранее найденную присоединенную матрицу (12.30). Для характеристического корня Xj = 1

Производная по X уравнения (12.29) откуда

Согласно (12.34),

Строки полученной матрицы одинаковы и должны быть равны финальным вероятностям состояний. При умножении слева этой матрицы на любой вероятностный вектор (сумма элементов вероятностного вектора равна 1) получим строку матрицы.

Для рассмотренного ранее численного примера нахождения вероятности заказа клиентом в каждом месяце

Матрица финальных вероятностей вычисляется по (12.35) как

Подставляя численные значения а = 0,3, a (3 = 0,4, получаем Следовательно, финальная вероятность заказа Финальная вероятность незаказа

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

Эргодические цепи Маркова. Марковские цепи, для которых существуют финальные вероятности, называются эргодическими. Если марковская цепь эргодическая, то из каждого ее состояния можно попасть в любое другое. Регулярная цепь всегда эргодическая, т.е. она не содержит невозвратных состояний и имеет единственное эргодическое множество состояний. Система, описываемая эрго- дической цепью Маркова, называется статистически устойчивой.

Если цепь Маркова эргодическая и стационарные вероятности состояний существуют, то необходимо их вычислить. Перед этим были приведены способы определения стационарных вероятностей путем вычисления Игл П" = П°° и П°°.

п-> ОС

Однако можно вычислить эти вероятности и без нахождения стационарной матрицы переходных вероятностей.

Финальные вероятности р к, к = 1,К, являются решением системы уравнений

В матричной записи (12.36) имеет вид

Так как уравнения (12.36) и (12.37) вероятностные, они должны удовлетворять условию нормировки

или в матричной записи

Система (12.38) - линейно зависимая матрица П размером пх п является сингулярной и имеет ранг (п - 1). Поэтому для нахождения К неизвестных финальных вероятностей необходимо заменить одно из уравнений системы (12.36) на уравнение (12.38) .

Уравнение (12.37) может быть представлено в виде

Следовательно, для нахождения решения необходимо решить систему линейных уравнений типа

При решении необходимо использовать условие нормировки (12.39), поэтому один из столбцов матрицы В надо заменить на единичный вектор 1, в результате чего получится матрица С. Если заменяется последний столбец матрицы, система (12.40) преобразуется в систему

где

Рассмотрим систему с двумя состояниями. Согласно (12.36), Заменим последнее уравнение системы на условие нормировки:

В матричной записи (12.41) элементы уравнения будут равны:

Если существует обратная матрица С -1 , то решение можно найти в виде

Для рассматриваемого примера обратная матрица существует: поэтому

Так как п п = 1-7т 12 , п 21 = 1-тг 22 , найденное решение можно также записать как

что соответствует полученным ранее решениям.

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

Способы математических описаний марковских случайных процессов в системе с дискретными состояниями (ДС) зависят от того, в какие моменты времени (заранее известные или случайные) могут происходить переходы системы из состояния в состояние.
Если переход системы из состояния в состояние возможен в заранее фиксированные моменты времени, имеем дело со случайным марковским процессом с дискретным временем. Если переход возможен в любой случайный момент времени, то имеем дело со случайным марковским процессом с непрерывным временем.
Пусть имеется физическая система S , которая может находиться в n состояниях S 1 , S 2 , …, S n . Переходы из состояния в состояние возможны только в моменты времени t 1 , t 2 , …, t k , назовём эти моменты времени шагами. Будем рассматривать СП в системе S как функцию целочисленного аргумента 1, 2, …, k , где аргументом является номер шага.
Пример: S 1 → S 2 → S 3 → S 2 .
Условимся обозначать S i ( k ) – событие, состоящее в том, что после k шагов система находится в состоянии S i .
При любом k события S 1 ( k ) , S 2 ( k ) ,…, S n ( k ) образуют полную группу событий и являются несовместными.

Процесс в системе можно представить как цепочку событий.
Пример:S 1 (0) , S 2 (1) , S 3 (2) , S 5 (3) ,….
Такая последовательность называется марковской цепью , если для каждого шага вероятность перехода из любого состояния S i в любое состояние S j не зависит от того, когда и как система пришла в состояние S i .
Пусть в любой момент времени после любого k -го шага система S может находиться в одном из состояний S 1 , S 2 , …, S n , т. е. может произойти одно событие из полной группы событий: S 1 ( k ) , S 2 ( k ) , …, S n ( k ) . Обозначим вероятности этих событий:
P 1 (1) = P (S 1 (1)); P 2 (1) = P (S 2 (1)); …; P n (1) = P (S n ( k ));
P 1 (2) = P (S 1 (2)); P 2 (2) = P (S 2 (2)); …; P n (2) = P (S n (2));
P 1 (k ) = P (S 1 (k )); P 2 (k ) = P (S 2 (k )); …; P n (k ) = P (S n (k )).
Легко заметить, что для каждого номера шага выполняется условие
P 1 (k ) + P 2 (k ) +…+ P n (k ) = 1.
Назовём эти вероятности вероятностями состояний .следовательно, задача будет звучать следующим образом: найти вероятности состояний системы для любого k .
Пример. Пусть имеется какая-то система, которая может находиться в любом из шести состояний. тогда процессы, происходящие в ней, можно изобразить либо в виде графика изменения состояния системы (рис. 7.9, а ), либо в виде графа состояний системы (рис. 7.9, б ).

а)

Рис. 7.9
Также процессы в системе можно изобразить в виде последовательности состояний: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Вероятность состояния на (k + 1)-м шаге зависит только от состояния на k- м шаге.
Для любого шага k существуют какие-то вероятности перехода системы из любого состояния в любое другое состояние, назовем эти вероятности переходными вероятностями марковской цепи.
Некоторые из этих вероятностей будут равны 0, если переход из одного состояния в другое невозможен за один шаг.
Марковская цепь называется однородной , если переходные состояния не зависят от номера шага, в противном случае она называется неоднородной .
Пусть имеется однородная марковская цепь и пусть система S имеет n возможных состояний: S 1 , …, S n . Пусть для каждого состояния известна вероятность перехода в другое состояние за один шаг, т.е. P ij (из S i в S j за один шаг), тогда мы можем записать переходные вероятности в виде матрицы.

. (7.1)
По диагонали этой матрицы расположены вероятности того, что система переходит из состояния S i в то же состояние S i .
Пользуясь введенными ранее событиями S 1 (k) , S 2 (k) ,..., S n (k) можно переходные вероятности записать как условные вероятности:
P ij =P(S j (k) /S i k-1)
Очевидно, что сумма членов P ij k =P(S j (k) /S i k-1) в каждой строке матрицы (1) равна единице, поскольку события S 1 (k) , S 2 (k) ,..., S n (k) образуют полную группу несовместных событий.

При рассмотрении марковских цепей, так же как и при анализе марковского случайного процесса, используются различные графы состояний (рис. 7.10).

Рис. 7.10

Данная система может находиться в любом из шести состояний, при этом P ij – вероятность перехода системы из состояния S i в состояние S j . Для данной системы запишем уравнения, что система находилась в каком-либо состоянии и из него за время t не вышла:

В общем случае марковская цепь является неоднородной, т. е. вероятность P ij меняется от шага к шагу. Предположим, что задана матрица вероятностей перехода на каждом шаге, тогда вероятность того, что система S на k -м шаге будет находиться в состоянии S i , можно найти по формуле

Зная матрицу переходных вероятностей и начальное состояние системы, можно найти вероятности состояний P 1 (k) , P 2 (k) , ..., P n (k) после любого k -го шага. Пусть в начальный момент времени система находится в состоянии S m . Тогда для t = 0
P 1 (0)=0 , P 2 (0)=0 ,..., P m (0)=1 ,..., P n (0)=0
Найдем вероятности после первого шага. Из состояния S m система перейдет в состояния S 1 , S 2 и т.д. с вероятностями P m 1 , P m 2 , …, P mm , … , P mn . Тогда после первого шага вероятности будут равны

P 1 (1) = P m1 ; P 2 (1) = P m2 , ..., P n (1) = P mn (7.2)
Найдем вероятности состояния после второго шага: P 1 (2) , P 2 (2) , ..., P n (2) . Будем вычислять эти вероятности по формуле полной вероятности с гипотезами:
.
Гипотезами будут следующие утверждения:

• после первого шага система была в состоянии S 1 -H 1 ;
• после второго шага система была в состоянии S 2 -H 2 ;
• после n -го шага система была в состоянии S n -H n .

Вероятности гипотез известны из выражения (7.2). Условные вероятности перехода в состояние А при каждой гипотезе тоже известны и записаны в матрицы переходных состояний. Тогда по формуле полной вероятности получим:

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

(7.3)
В формуле (7.3) суммируются все переходные вероятности P ij , но учитываются только отличные от нуля. Вероятность любого состояния после k -го шага:

(7.4)
Таким образом, вероятность состояния после k -го шага определяется по рекуррентной формуле (7.4) через вероятности (k – 1)-го шага.

Задача 6. Задана матрица вероятностей перехода для цепи Маркова за один шаг. Найти матрицу перехода данной цепи за три шага.
Решение. Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

В каждой строке матрицы помещены вероятности событий (перехода из состояния i в состояние j ), которые образуют полную группу, поэтому сумма вероятностей этих событий равна единице:

Обозначим через p ij (n) вероятность того, что в результате n шагов (испытаний) система перейдет из состояния i в состояние j . Например p 25 (10) - вероятность перехода из второго состояния в пятое за десять шагов. Отметим, что при n=1 получаем переходные вероятности p ij (1)=p ij .
Перед нами поставлена задача: зная переходные вероятности p ij , найти вероятности p ij (n) перехода системы из состояния i в состояние j заn шагов. Для этого введем промежуточное (между i и j ) состояние r . Другими словами, будем считать, что из первоначального состояния i за m шагов система перейдет в промежуточное состояние r с вероятностью p ij (n-m) , после чего, за оставшиеся n-m шагов из промежуточного состояния r она перейдет в конечное состояние j с вероятностью p ij (n-m) . По формуле полной вероятности получаем:
.
Эту формулу называют равенством Маркова. С помощью этой формулы можно найти все вероятности p ij (n) , а, следовательно, и саму матрицу P n . Так как матричное исчисление ведет к цели быстрее, запишем вытекающее из полученной формулы матричное соотношение в общем виде P n = P 1 n .
Вычислим матрицу перехода цепи Маркова за три шага, используя полученную формулу:

Ответ: .

Задача №1 . Матрица вероятностей перехода цепи Маркова имеет вид:
.
Распределение по состояниям в момент времени t=0 определяется вектором:
π 0 =(0.5; 0.2; 0.3)
Найти: а) распределение по состояниям в моменты t=1,2,3,4 .
в) стационарное распределение.