Марковская цепь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
Матрицу <tex>P = ||p_{ij}||</tex> называют '''матрицей переходов'''.
 
Матрицу <tex>P = ||p_{ij}||</tex> называют '''матрицей переходов'''.
 
}}
 
}}
 
[[File:Markov_chain_example.png|thumb|273px|Пример марковской цепи]]
 
  
 
На матрицу переходов накладываются следующие условия:
 
На матрицу переходов накладываются следующие условия:
Строка 80: Строка 78:
  
 
В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими — 1 и 2.
 
В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими — 1 и 2.
 +
 +
=== Пример ===
 +
[[File:Markov-chain-example-complete.png|thumb|500px|Пример марковской цепи]]
 +
 +
На рисунке:
 +
* достижимыми состояниями являются: <tex> 2 </tex> из <tex> 1 </tex>, <tex> 1 </tex> из <tex> 2 </tex>, <tex> 3 </tex> из <tex> 1 </tex> и т.д., сообщаются <tex> 1 </tex> и <tex> 2 </tex>, а также <tex> 6 </tex> и <tex> 7 </tex>;
 +
* неразложимыми классами являются множества вершин <tex> \left \{ 1, 2, 3 \right \} </tex>, <tex> \left \{ 4 \right \} </tex>, <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>;
 +
* эргодическими классами являются множества вершин <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>;
 +
* поглощающим состоянием является состояние <tex> 5 </tex>.
  
 
== Литература ==
 
== Литература ==

Версия 22:58, 9 марта 2012

Определение:
Цепь Маркова — процесс, находящийся в одном из [math]n[/math] состояний.

При этом, если он находится в состоянии с номером [math]i[/math], то он перейдет в состояние [math]j[/math] с вероятностью [math]p_{ij}[/math].

Матрицу [math]P = ||p_{ij}||[/math] называют матрицей переходов.


На матрицу переходов накладываются следующие условия:

  1. [math] p_{ij} \geqslant 0 [/math]
  2. [math] \forall i\ \ \sum\limits_{j} p_{ij} = 1 [/math]

Такая матрица называется стохастической.

В общем случае для марковской цепи задают вектор [math] c_0[/math]. [math]\ c_{0i} [/math] — вероятность того, что в начале процесса марковская цепь находится в состоянии [math] i [/math].

Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из [math] i [/math] в [math] j [/math] написана вероятность перехода из [math] i [/math] в [math] j [/math], то есть [math] p_{ij} [/math].

Вероятность того, что через [math] r [/math] шагов марковская цепь будет находиться в состоянии [math] j [/math] равна [math] c_{rj} = (c_0 P^r) [j] [/math]

Достижимость и сообщаемость

Обозначим вероятность попасть из состояния [math] i [/math] в состояние [math] j [/math] за [math] n [/math] переходов как [math] p_{ij}^{(n)} [/math].


Определение:
Состояние [math] j [/math] достижимо (accesible) из состояния [math] i [/math], если существует такое [math] n [/math], что [math] p_{ij}^{(n)} \gt 0 [/math]. Достижимость [math] j [/math] из [math] i [/math] обозначается [math] i \rightarrow j [/math].


Определение:
Состояния [math] i [/math] и [math] j [/math] сообщаются (communicate), если они достижимы друг из друга.


Классификация цепей и состояний

Неразложимая цепь

Определение:
Неразложимый класс (communicating class) — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности.


Определение:
Неразложимая цепь (ireducible chain) — цепь Маркова, в которой все состояния образуют один неразложимый класс.


Эргодическая цепь

Определение:
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются эргодическими классами. Состояния в эргодических классах называются эргодическими (ergodic), возвратными, или существенными. Все остальные неразложимые классы называются невозвратными классами. Состояния, входящие в них, называются невозвратными или несущественными.


Определение:
Если эргодический класс состоит из одного состояния, такое состояние называется поглощающим (absorbing).


Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс.


Определение:
Эргодическая марковская цепь — марковская цепь, целиком состоящая из одного эргодического класса.


Определение:
В эргодической цепи можно выделить циклические классы. Количество циклических классов [math] d [/math] называют периодом цепи, если цепь состоит целиком из одного циклического класса, её называют регулярной. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые d шагов она оказывается в одном и том же циклическом классе.


Таким образом, эргодические цепи делятся на регулярные и циклические.

Поглощающая цепь

Определение:
Поглощающей (absorbing chain) называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее.


В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими — 1 и 2.

Пример

Пример марковской цепи

На рисунке:

  • достижимыми состояниями являются: [math] 2 [/math] из [math] 1 [/math], [math] 1 [/math] из [math] 2 [/math], [math] 3 [/math] из [math] 1 [/math] и т.д., сообщаются [math] 1 [/math] и [math] 2 [/math], а также [math] 6 [/math] и [math] 7 [/math];
  • неразложимыми классами являются множества вершин [math] \left \{ 1, 2, 3 \right \} [/math], [math] \left \{ 4 \right \} [/math], [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
  • эргодическими классами являются множества вершин [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
  • поглощающим состоянием является состояние [math] 5 [/math].

Литература

  • И.В. Романовский «Дискретный анализ». 3-е изд., 2003. стр. 270—279
  • Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"
  • Цепь Маркова