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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Состояния: вроде нормальная классификация)
Строка 23: Строка 23:
 
== Состояния ==
 
== Состояния ==
  
Состояния марковской цепи делятся на два класса: ''поглощающие'' (''существенные'') и ''непоглощающие'' (''несущественные'').
+
{{Определение
{{Определение | definition =
+
|definition=
Состояние <tex> i </tex> называют '''поглощающим (существенным)''', если <tex> p_{ii} = 1 </tex>.
+
<tex> p_{ij}^{(n)} </tex> {{---}} вероятность попасть из состояния <tex> i </tex> в состояние <tex> j </tex> за <tex> n </tex> переходов.
Все остальные состояния называют '''непоглощающими (несущественными)'''.
 
 
}}
 
}}
 +
 +
{{Определение
 +
|definition=
 +
Состояние <tex> j </tex> '''достижимо''' из состояния <tex> i </tex>, если существует такое <tex> n </tex>, что <tex> p_{ij}^{(n)} > 0 </tex>. Достижимость <tex> j </tex> из <tex> i </tex> обозначается <tex> i \rightarrow j </tex>. <br>
 +
Состояния '''сообщаются''', если они достижимы друг из друга.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
'''Неразложимый класс''' {{---}} класс эквивалентности множества состояний по отношению сообщаемости. Если представить Марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности. <br>
 +
'''Неразложимая цепь''' {{---}} цепь Маркова, в которой все состояния образуют один неразложимый класс.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''. Состояния в эргодических классах называются '''эргодическими''', '''возвратными''', или '''существенными'''. Если эргодический класс состоит из одного состояния, такое состояние называется '''поглощающим'''.<br>
 +
Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс. <br>
 +
Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными'''.
 +
}}
 +
  
 
В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими {{---}} 1 и 2.
 
В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими {{---}} 1 и 2.
 
Вероятность того, что через <tex> r </tex> шагов марковская цепь будет находиться в состоянии <tex> j </tex> равна <tex dpi = 150> c_{rj} = (c_0 P^r) [j] </tex>
 
  
 
== Смотри также ==
 
== Смотри также ==

Версия 05:19, 17 января 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] p_{ij}^{(n)} [/math] — вероятность попасть из состояния [math] i [/math] в состояние [math] j [/math] за [math] n [/math] переходов.


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


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


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

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

Все остальные неразложимые классы называются невозвратными классами. Состояния, входящие в них, называются невозвратными или несущественными.


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

Смотри также

Литература

  • И.В. Романовский. «Дискретный анализ»