Викиконспекты - Вклад участника [ru]

Регулярная марковская цепь

2011-01-15T22:31:31Z

Alina:

== Регулярная цепь Маркова ==
{{Определение
|definition=Марковская цепь называется регулярной (нормальной), если <tex>p_{ij} > 0, \forall i,j=1,2, \ldots</tex>.
}}
=== Пример: ===
[[File:Temp.gif|thumb|250px|Пример регулярной цепи]]
Рассмотрим эксперимент по бросанию честной монеты. Тогда соответствующая этому эксперименту марковская цепь будет иметь 2 состояния. Рассмотрим матрицу, следующего вида: <tex>p_{ij}=0.5, i,j=1,2</tex>.

Такая матрица является стохастической, а, значит, корректно определяет марковскую цепь. Такая цепь является регулярной по определению регулярной марковской цепи.

== Эргодическая теорема для регулярной марковской цепи ==
{{Теорема
|statement=Для регулярной марковской цепи существует такой вектор <tex>\omega = \lim\limits
_{n \to +\infty} cP^n, \forall c</tex> такой, что <tex>\omega = \omega P</tex>.
}}

== Литература ==
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"

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

2011-01-15T22:30:44Z

Alina:

== Эргодическая цепь Маркова ==
{{Определение
|definition=Марковская цепь называется эргодической, если существует дискретное распределение (называемое эргодическим) <tex>\pi = (\pi_1,\pi_2,\ldots )^{\top}</tex>, такое что <tex>\pi_i > 0,\; i \in \mathbb{N}</tex> и
:<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, \quad \forall i=1,2, \ldots</tex>.
}}
=== Пример: ===
[[File:Temp.gif|thumb|250px|Пример эргодической цепи]]
Рассмотрим эксперимент по бросанию честной монеты. Тогда соответствующая этому эксперименту марковская цепь будет иметь 2 состояния.
Рассмотрим матрицу, следующего вида: <tex>p_{ij}=0.5, i,j=1,2</tex>.

Такая матрица является стохастической, а, значит, корректно определяет марковскую цепь. Такая цепь является эргодической, так как существует эргодическое распределение <tex>\pi = (0.5,0.5)^{\top}</tex>, такое что <tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, i=1,2</tex>.
== См. также ==
[http://ru.wikipedia.org/wiki/%D0%AD%D1%80%D0%B3%D0%BE%D0%B4%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Википедия: эргодическое распределение]

[http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5#.D0.94.D0.B8.D1.81.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F Википедия: дискретное распределение]

== Литература ==
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"

Файл:Temp.gif

2011-01-15T22:28:10Z

Alina: загружена новая версия «Файл:Temp.gif»

Теорема о поглощении

2011-01-15T21:27:10Z

Alina:

== Формулировка теоремы ==

'''Формулировка'''

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.

== Доказательство теоремы ==

Пусть '''''P''''' - матрица переходов, где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где '''''Q''''' - несущественные состояния, а '''''R''''' и '''''I''''' - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное) '''''I''''' - единичная матрица.
[[Файл:Матрница_перехода.GIF‎]]

Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге ''t''.
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени ''t''.
<tex> c^{(t)} = c^{(0)} * P^t</tex>
Рассмотрим, что представляет из себя возведение матрицы '''''P''''' в степень:

для ''t=1'' :
[[Файл:Матрница перехода (перемножение).GIF]]

Отсюда видно, что <tex> P^n</tex> имеет такой вид, где '''''X''''' - некоторые значения.
[[Файл:Vfnhbwf d n-jq cntgtyb.GIF]]

Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>

Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага i не попадет в поглощающее состояние.
Пусть <tex>m = max(m_i)</tex>, а <tex>p = max(p_i)< 1</tex>

Тогда получаем: <tex>\sum_{j} {Q^m_{ij}}\leqslant p</tex> <tex>\Rightarrow</tex> <tex>\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex>

В итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.е. цепь приходит в поглощающее состояние.

Файл:Матрница перехода (перемножение).GIF

2011-01-15T21:26:44Z

Alina: загружена новая версия «Файл:Матрница перехода (перемножение).GIF»

Файл:Матрница перехода.GIF

2011-01-15T21:25:59Z

Alina: загружена новая версия «Файл:Матрница перехода.GIF»

Файл:Vfnhbwf d n-jq cntgtyb.GIF

2011-01-15T21:25:01Z

Alina: загружена новая версия «Файл:Vfnhbwf d n-jq cntgtyb.GIF»

Теорема о поглощении

2011-01-15T21:14:18Z

Alina:

== Формулировка теоремы ==

'''Формулировка'''

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.

== Доказательство теоремы ==

Пусть '''''P''''' - матрица переходов, где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где '''''Q''''' - несущественные состояния, а '''''R''''' и '''''I''''' - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное) '''''I''''' - единичная матрица.
[[Файл:Матрница_перехода.GIF‎]]

Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге ''t''.
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени ''t''.
<tex> c^{(t)} = c^{(0)} * P^t</tex>
Рассмотрим, что представляет из себя возведение матрицы '''''P''''' в степень:

для ''t=1'' :
[[Файл:Матрница перехода (перемножение).GIF]]
Отсюда видно, что <tex> P^n</tex> имеет такой вид, где '''''X''''' - некоторые значения.
[[Файл:Vfnhbwf d n-jq cntgtyb.GIF]]

Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>

Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага i не попадет в поглощающее состояние.
Пусть <tex>m = max(m_i)</tex>, а <tex>p = max(p_i)< 1</tex>

Тогда получаем: <tex>\sum_{j} {Q^m_{ij}}\leqslant p</tex> <tex>\Rightarrow</tex> <tex>\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex>

В итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.е. цепь приходит в поглощающее состояние.

Теорема о поглощении

2011-01-15T21:10:27Z

Alina:

== Формулировка теоремы ==

'''Формулировка'''

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.

== Доказательство теоремы ==

Пусть '''''P''''' - матрица переходов, где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где Q - несущественные состояния, а R и I - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное)
[[Файл:Матрница_перехода.GIF‎]]

Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге t.
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени t.
<tex> c^{(t)} = c^{(0)} * P^t</tex>
Рассмотрим, что представляет из себя возведение матрицы P в степень:

для t=1 :
[[Файл:Матрница перехода (перемножение).GIF]]
Отсюда видно, что <tex> P^n</tex> имеет такой вид, где X - некоторые значения.
[[Файл:Vfnhbwf d n-jq cntgtyb.GIF]]

Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>

Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага i не попадет в поглощающее состояние.
Пусть <tex>m = max(m_i)</tex>, а <tex>p = max(p_i)< 1</tex>

Тогда получаем: <tex>\sum_{j} {Q^m_{ij}}\leqslant p</tex> <tex>\Rightarrow</tex> <tex>\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex>

В итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.е. цепь приходит в поглощающее состояние.

Файл:Vfnhbwf d n-jq cntgtyb.GIF

2011-01-15T20:49:20Z

Alina:

Файл:Матрница перехода (перемножение).GIF

2011-01-15T20:47:00Z

Alina:

Файл:Матрница перехода.GIF

2011-01-15T20:35:04Z

Alina: