Матрица переходов и граф состояний

Матрица переходов и граф состояний

Допустим, число состояний конечно и равно k. Тогда матрица, составленная из условных вероятностей перехода будет иметь вид:
Эта матрица называется матрицей перехода системы.
Т.к. в каждой строке содержаться вероятности событий, которые образуют полную группу, то, очевидно, что сумма элементов каждой строки матрицы равна единице.
На основе матрицы перехода системы можно построить так называемый граф состояний системы, его еще называют размеченный граф состояний. Это удобно для наглядного представления цепи. Порядок построения граф рассмотрим на примере.
Пример. По заданной матрице перехода построить граф состояний.
Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.
На графе не отмечаются вероятности перехода системы из одного состояния в то же самое. При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы.
Пусть Pij(n) - вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r - некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое pij(1) = pij. Тогда вероятность Pij(n) может быть найдена по формуле, называемой равенством Маркова:
равенство Маркова
Здесь n - число шагов (испытаний), за которое система перешла из состояния i в состояние r.
В принципе, равенство Маркова есть ни что иное как несколько видоизменная формула полной вероятности.
Зная переходные вероятности (т.е. зная матрицу перехода Р1), можно найти вероятности перехода из состояния в состояние за два шага Pij(2), т.е. матрицу Р2, зная ее - найти матрицу Р3, и т.д.
Непосредственное применений полученной выше формулы не очень удобно, поэтому, можно воспользоваться приемами матричного исчисления (ведь эта формула по сути - не что иное как формула перемножения двух матриц).
Тогда в общем виде можно записать:
Вообще то этот факт обычно формулируется в виде теоремы, однако, ее доказательство достаточно простое, поэтому приводить его не буду.
Пример. Задана матрица переходов Р1. Найти матрицу Р3.
Определение. Матрицы, суммы элементов всех строк которых равны единице, называются стохастическими. Если при некотором n все элементы матрицы Рn не равны нулю, то такая матрица переходов называется регулярной.
Другими словами, регулярные матрицы переходов задают цепь Маркова, в которой каждое состояние может быть достигнуто через n шагов из любого состояния. Такие цепи Маркова также называются регулярными.
Теорема. (теорема о предельных вероятностях) Пусть дана регулярная цепь Маркова с n состояниями и Р - ее матрица вероятностей перехода. Тогда существует предел предел и матрица Р(¥) имеет вид:
Т.е. матрица состоит из одинаковых строк.