Марковские цепи

Пусть система может находиться в состояниях , где . Обозначим через - вероятность нахождения системы в конкретном состоянии в момент времени . Введем в рассмотрение стохастический вектор

, где ;

; .

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

Марковский процесс - это такой процесс, будущее состояние которого определяется только настоящим состоянием и не зависит от предыдущего состояния.

Каждой паре состояний , можно поставить в соответствие условную вероятность того, что система находится в состоянии в момент при условии, что в момент она находится в состоянии _. Очевидно, для вероятности справедливо:

.

Эти уравнения являются частным случаем уравнений Чемпмена - Колмогоpова. Они означают, что система может оказаться в состоянии путем одного из несовместных переходов. Причем вероятность нахождения системы в состоянии при условии, что ранее система находилась в состоянии , определяется по формуле произведения вероятностей событий.

Уравнения Чемпмена - Колмогоpова могут быть записаны в векторной форме:

, где - квадратная матрица вероятностей переходов:

; ; , для всех .

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

Приведем некоторые свойства стохастических матриц.

- Если стохастическая матрица, то то же стохастическая матрица.

- Если все строки матрицы одинаковы, то ,

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

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

Маpковские процессы удобно изображать в виде графа состояний (рис.4.4), вершины которого соответствуют состояниям, а дуги - переходам. Около каждой вершины записываются соответствующее состояние , а около дуги - вероятность перехода . Сумма вероятностей для дуг, выходящих из любой вершины графа, должна равняться единице.