Графическое представление цепи

Цепи Маркова

 

Пусть имеется система S, которая может находиться в состояниях a₁,a₂,…,a_k, и в процессе работы может переходить только в эти состояния.

Пример: выключатель, АТС с двумя телефонами.

В определенные моменты времени t₁,t₂,… система может переходить из одного состояния в другое с определенной вероятностью. Переход обозначим: , - вероятность соответствующего перехода.

Система, которая переходит в каждое свое состояние в определенные моменты времени, называется дискретной.

Если переходы осуществляются не в определенные моменты, а в определенном промежутке времени, то система называется непрерывной.

Определение. Цепью Маркова называется последовательность переходов системы из одного состояния в другое, для которых известны , т.е. вероятности переходов.

Все вероятности переходов обычно записывают в виде матрицы переходов в цепи за один шаг:

a₁ a₂ … a_k

 

Свойства матрицы:

1.

2. - сумма элементов любой строки равна 1.

Матрица, обладающая такими свойствами, называется вероятностной матрицей.

Переход цепи из одного состояния в другое будем называть шагами перехода.

 

Задание цепи

 

Для того чтобы задать цепь, нужно знать:

1. Распределение вероятностей состояний в начальный момент, т.е. - начальное распределение (начальный вектор).

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

1. Матрицу переходов цепи за один шаг - .

 

Графическое представление цепи

 

Любую цепь всегда можно представить в виде графа.

Пример: пусть Р имеет вид:

a₁ a₂ a₃

 

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

 

Зная граф переходов, можно получить матрицу переходов.

Графическое представление удобно, когда число

состояний небольшое: 3 или 4.

 

 

Распределение состояний цепи через n-шагов

 

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

 

Пример. a₁ a₂ a₃

Пусть в начальный момент цепь находится в состоянии a₁: . Требуется определить распределение состояний цепи через 3 шага.

 

 

 

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

 

Аналитическое решение распределения состояний цепи через n-шагов

 

Пусть имеем цепь - начальное распределение и матрицу переходов цепи за один шаг - . Требуется найти распределение вероятностей состояний через n- шагов, т.е. , - вероятность того, что через n- шагов цепь (система) будет находиться в состоянии a_j, j=1,2,…,k.

По формуле полной вероятности получим:

 

(1)

 

В случае k=3 (3 состояния) система (1) примет вид:

 

(1^’)

 

Систему (1) обычно называют системой уравнений Колмогорова.

Систему (1) удобно записать в матричном виде следующим способом:

 

(2)

p(n-1) P

Тогда равенство (2) в матричном виде кратко запишется так:

 

(3)

 

Систему (3), придавая последовательно значения 1,2,3,…,k, можно переписать так:

 

 

Тогда система (3) окончательно примет вид:

 

(4)

 

Система (4) – система уравнений Колмогорова для нахождения распределения цепи через n- шагов.

Пример. (продолжение) 1 способ

Для нахождения нужного распределения нужно матрицу переходов P возвести в третью степень. В результате получим:

.

 

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

2 способ

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

 

Существование предельного распределения

 

Потоки вероятностей

 

1. Пусть имеем цепь с состояниями a₁,a₂,…,a_k,, вероятности которых будут p₁,p₂,…,p_k, и матрицу переходов .

Потоком вероятностей называется число, определяемое равенством: , аналогично потоком вероятностей называется число .

 

Непрерывные цепи Маркова

 

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

Характеристики цепей.

Как и в дискретном случае переходы в другие состояния будут характеризоваться соответствующими вероятностями.

- вероятность того, что цепь сделает переход за время .

Цепи Маркова

 

Пусть имеется система S, которая может находиться в состояниях a₁,a₂,…,a_k, и в процессе работы может переходить только в эти состояния.

Пример: выключатель, АТС с двумя телефонами.

В определенные моменты времени t₁,t₂,… система может переходить из одного состояния в другое с определенной вероятностью. Переход обозначим: , - вероятность соответствующего перехода.

Система, которая переходит в каждое свое состояние в определенные моменты времени, называется дискретной.

Если переходы осуществляются не в определенные моменты, а в определенном промежутке времени, то система называется непрерывной.

Определение. Цепью Маркова называется последовательность переходов системы из одного состояния в другое, для которых известны , т.е. вероятности переходов.

Все вероятности переходов обычно записывают в виде матрицы переходов в цепи за один шаг:

a₁ a₂ … a_k

 

Свойства матрицы:

1.

2. - сумма элементов любой строки равна 1.

Матрица, обладающая такими свойствами, называется вероятностной матрицей.

Переход цепи из одного состояния в другое будем называть шагами перехода.

 

Задание цепи

 

Для того чтобы задать цепь, нужно знать:

1. Распределение вероятностей состояний в начальный момент, т.е. - начальное распределение (начальный вектор).

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

1. Матрицу переходов цепи за один шаг - .

 

Графическое представление цепи

 

Любую цепь всегда можно представить в виде графа.

Пример: пусть Р имеет вид:

a₁ a₂ a₃

 

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

 

Зная граф переходов, можно получить матрицу переходов.

Графическое представление удобно, когда число

состояний небольшое: 3 или 4.