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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 62: Строка 62:
 
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии <tex>s_i</tex>, и эта вероятность не зависит от начального распределения, а зависит только от матрицы P.
 
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии <tex>s_i</tex>, и эта вероятность не зависит от начального распределения, а зависит только от матрицы P.
  
== Пример ==
+
== Примеры ==
 
[[File:Temp.gif|thumb|250px|Пример регулярной цепи]]
 
[[File:Temp.gif|thumb|250px|Пример регулярной цепи]]
Самый очевидный пример регулярной цепи - честная монета. Матрица переходов будет выглядеть так:
+
Самый очевидный и тривиальный пример регулярной цепи:
 +
 
 +
Пусть у нас есть два состояния - "1" и "2". Каждый ход мы кидаем честную монету - если выпал "0", то цепь остается в предыдущем состоянии, если "1" - цепь меняет свое состояние.
 +
 
 +
Матрица переходов будет выглядеть так:
  
 
<tex>
 
<tex>
Строка 74: Строка 78:
  
 
Тогда <tex>\forall n \ \ P^n = P = A,\  \alpha = \{ 0.5, 0.5 \}</tex>
 
Тогда <tex>\forall n \ \ P^n = P = A,\  \alpha = \{ 0.5, 0.5 \}</tex>
То есть через достаточно большое количество ходов наша система будет ''равновероятно'' находится как в состоянии "1", так и в состоянии "0", независимо от начального распределения.
+
То есть через достаточно большое количество ходов наша система будет ''равновероятно'' находится как в состоянии "1", так и в состоянии "2", независимо от начального распределения.
 +
 
 +
Более интересный пример - если мы будем управлять переходом состояний с помощью нечестной монеты.
 +
Пусть а - вероятность выпадения "0" на монете.
 +
 
 +
Матрица переходов будет выглядеть так:
 +
 
 +
<tex>
 +
P = \begin{bmatrix}
 +
a & 1 - a \\
 +
1 - a & a
 +
\end{bmatrix}
 +
</tex>
 +
 
 +
Тогда при возведении Р в степень n элементы будут стремится к <tex>\frac{1}{2}</tex> с разных сторон.
 +
То есть вектор <tex>\alpha = \{ 0.5, 0.5 \}</tex>, т.е от честности монеты ничего не зависит.
  
 
== Литература ==
 
== Литература ==

Версия 03:09, 14 января 2012

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

Определение:
Марковская цепь называется регулярной (нормальной), если в матрице перехода P [math]\forall i,j \ \ p_{ij} \neq 0[/math].


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

Лемма

Лемма:
Пусть [math]P_{[r\times r]}[/math] — матрица перехода регулярной цепи, [math]\varepsilon[/math] — минимальный элемент этой матрицы. Пусть х — произвольный r-мерный вектор-столбец, имеющий максимальный элемент [math]M_0[/math] и минимальный [math]m_0[/math]. Пусть [math]M_1[/math] и [math]m_1[/math] - максимальный и минимальный элементы [math]Px[/math].
Тогда [math]M_1 \leqslant M_0[/math], [math]m_1 \geqslant m_0[/math] и [math]M_1 - m_1 \leqslant (1 - 2\varepsilon)(M_0 - m_0)[/math]
Доказательство:
[math]\triangleright[/math]

Пусть х' - вектор, полученный из х заменой всех элементов, кроме [math]m_0[/math] на [math]M_0[/math]. Тогда [math]x \leqslant x'[/math]. Каждый элемент [math]Px'[/math] имеет вид

[math]am_0 + (1 - a)M_0 = M_0 - a(M_0 - m_0)[/math], где а - элемент P, который домножается на [math]m_0[/math], причем [math]a \geqslant \varepsilon[/math]. Поэтому наше выражение не превосходит [math]M_0 - \varepsilon(M_0 - m_0)[/math]. Отсюда и из неравенства [math]x \leqslant x'[/math] получается: [math]M_1 \leqslant M_0 - \varepsilon (M_0 - m_0)[/math].

Применяя те же рассуждения для вектора -х, получим: [math]-m_1 \leqslant -m_0 - \varepsilon (-m_0 + M_0)[/math].

Складывая эти два неравенства, получаем [math]M_1 - m_1 \leqslant M_0 - m_0 - 2\varepsilon (M_0 - m_0) = (1 - 2\varepsilon )(M_0 - m_0)[/math], ч.т.д.
[math]\triangleleft[/math]

Основная теорема регулярных цепей (Эргодическая теорема)

Теорема:
Регулярная марковская цепь эргодична. Другими словами:

Пусть Р - регулярная переходная матрица. Тогда:
[math]\exists A: \displaystyle \lim_{n \to \infty}P^n = A[/math];

каждая строка А представляет собой один и тот же вероятностный вектор [math]\alpha = \{a_1, a_2, \ldots, a_r \}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим вектор-столбец [math]e_j[/math], у которого j-й элемент равен 1, а все остальные равны 0. Пусть [math]M_n[/math] и [math]m_n[/math] - минимальный и максимальный элементы столбца [math]P^n e_j[/math]. Так как [math]P^n e_j = P \cdot P^{n-1} e_j[/math], то из леммы следует, что [math]M_1 \geqslant M_2 \geqslant \ldots[/math] и [math]m_1 \leqslant m_2 \leqslant \ldots[/math] и

[math]M_n - m_n \leqslant (1 - 2\varepsilon )(M_{n-1} - m_{n-1})[/math]. Пусть [math]d_n = M_n - m_n[/math], тогда

[math]d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0[/math].

Значит [math]P^n e_j[/math] сходится к вектору, все элементы которого равны между собой. Пусть [math]a_j[/math] - их общее значение. Тогда [math]0 \leqslant a_j \leqslant 1[/math]. Заметим, что [math]P^n e_j[/math] - j-тый столбец матрицы [math]P^n[/math]. Рассмотрим все [math]e_j[/math] для [math]j = 1, 2, \ldots[/math]. Тогда [math]P^n[/math] сходится к матрице А, у которой по строкам стоит один и тот же вектор [math]\alpha = \{a_1, a_2, \ldots, a_r \}[/math].

Так как в каждой матрице [math]P^n[/math] сумма элементов в строке равна 1, то то же самое справедливо и для предельной матрицы А. Теорема доказана.
[math]\triangleleft[/math]


Определение:
Матрица А называется предельной матрицей, вектор [math]\alpha[/math] - предельным распределением.


Следствия

Теорема:
Пусть [math]P, A, \alpha[/math] - объекты из предыдущей теоремы.

Тогда справедливы факты:

  • для любого вероятностного вектора [math]\pi \ \ \ \displaystyle \lim_{n \to \infty} \pi P^n = \alpha[/math]
  • [math]\alpha[/math] - единственный вектор, для которого [math]\alpha P = \alpha[/math]
  • [math]AP = PA = A[/math]
Доказательство:
[math]\triangleright[/math]

Пусть [math]\xi[/math] - вектор-столбец, состоящий из единиц.

  • [math]\pi[/math] - вероятностный вектор, значит [math]\pi \xi = 1 [/math] ( сумма его элементов равна 1 ), значит [math]\pi A = \pi \xi \alpha = \alpha[/math]. Но [math]\displaystyle \lim_{n \to \infty} \pi P^n = \pi A = \alpha[/math] - первый пункт доказан.
  • Пусть [math]\beta : \ \ \beta P = \beta[/math]. Тогда [math]\forall n \ \beta P^n = \beta \Rightarrow \beta = \beta A = \alpha[/math]. Второй пункт доказан.
  • [math]\displaystyle \lim_{n \to \infty} P^n = A \Leftrightarrow P \cdot \lim_{n \to \infty} P^n = A \Leftrightarrow \lim_{n \to \infty} P^n \cdot P = A[/math]. Третий пункт доказан.
[math]\triangleleft[/math]

Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии [math]s_i[/math], и эта вероятность не зависит от начального распределения, а зависит только от матрицы P.

Примеры

Пример регулярной цепи

Самый очевидный и тривиальный пример регулярной цепи:

Пусть у нас есть два состояния - "1" и "2". Каждый ход мы кидаем честную монету - если выпал "0", то цепь остается в предыдущем состоянии, если "1" - цепь меняет свое состояние.

Матрица переходов будет выглядеть так:

[math] P = \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix} [/math]

Тогда [math]\forall n \ \ P^n = P = A,\ \alpha = \{ 0.5, 0.5 \}[/math] То есть через достаточно большое количество ходов наша система будет равновероятно находится как в состоянии "1", так и в состоянии "2", независимо от начального распределения.

Более интересный пример - если мы будем управлять переходом состояний с помощью нечестной монеты. Пусть а - вероятность выпадения "0" на монете.

Матрица переходов будет выглядеть так:

[math] P = \begin{bmatrix} a & 1 - a \\ 1 - a & a \end{bmatrix} [/math]

Тогда при возведении Р в степень n элементы будут стремится к [math]\frac{1}{2}[/math] с разных сторон. То есть вектор [math]\alpha = \{ 0.5, 0.5 \}[/math], т.е от честности монеты ничего не зависит.

Литература

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