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

↑

▷ Содержание

Стр 1 из 3Следующая ⇒

Цепи Маркова

Пусть имеется система 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.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии