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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
  
В регулярной Марковской цепи из любого состояния можно попасть в другое за некоторое число ходов.
+
В регулярной Марковской цепи из любого состояния можно попасть в любое другое за некоторое число ходов.
  
 
== Лемма ==
 
== Лемма ==
Строка 19: Строка 19:
 
<tex>am_0 + (1 - a)M_0 = M_0 - a(M_0 - m_0)</tex>, где а - элемент P, который домножается на <tex>m_0</tex>, причем <tex>a \geqslant \varepsilon</tex>. Поэтому наше выражение не превосходит <tex>M_0 - \varepsilon(M_0 - m_0)</tex>. Отсюда и из неравенства <tex>x \leqslant x'</tex> получается: <tex>M_1 \leqslant M_0 - \varepsilon (M_0 - m_0)</tex>.
 
<tex>am_0 + (1 - a)M_0 = M_0 - a(M_0 - m_0)</tex>, где а - элемент P, который домножается на <tex>m_0</tex>, причем <tex>a \geqslant \varepsilon</tex>. Поэтому наше выражение не превосходит <tex>M_0 - \varepsilon(M_0 - m_0)</tex>. Отсюда и из неравенства <tex>x \leqslant x'</tex> получается: <tex>M_1 \leqslant M_0 - \varepsilon (M_0 - m_0)</tex>.
  
Применяя те же рассуждения для вектора х, получим: <tex>-m_1 \leqslant -m_0 - \varepsilon (-m_0 + M_0)</tex>.
+
Применяя те же рассуждения для вектора -х, получим: <tex>-m_1 \leqslant -m_0 - \varepsilon (-m_0 + M_0)</tex>.
 +
 
 +
Складывая эти два неравенства, получаем <tex>M_1 - m_1 \leqslant M_0 - m_0 - 2\varepsilon (M_0 - m_0) = (1 - 2\varepsilon )(M_0 - m_0)</tex>, ч.т.д.
 +
 
 +
== Основная теорема регулярных цепей ==
 +
 
 +
{{Теорема
 +
|statement=Пусть Р - регулярная переходная матрица. Тогда:<br>
 +
<tex>\exists A: \displaystyle \lim_{n \to \infty}P^n = A</tex><br>;
 +
каждая строка А представляет собой один и тот же вероятностный вектор <tex>\alpha = \{a_1, a_2, \ldots, a_n \}</tex>
 +
}}
 +
 
 +
Доказательство:
 +
 
 +
Рассмотрим вектор-столбец <tex>\rho _j</tex>, у которого j-й элемент равен 1, а все остальные равны 0. Пусть <tex>M_n</tex> и <tex>m_n</tex> - минимальный и максимальный элементы столбца <tex>P^n \rho _j</tex>.
 +
Так как <tex>P^n \rho _j = P \cdot P^{n-1} \rho _j</tex>, то из леммы следует, что <tex>M_1 \geqslant M_2 \geqslant \ldots</tex> и <tex>m_1 \leqslant m_2 \leqslant \ldots</tex> и
 +
 
 +
<tex>M_n - m_n \leqslant (1 - 2\varepsilon )(M_{n-1} - m_{n-1})</tex>. Пусть <tex>d_n = M_n - m_n</tex>, тогда
 +
 
 +
<tex>d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0</tex>.
 +
 
 +
Значит <tex>P^n \rho _j</tex> сходится к вектору, все элементы которого равны между собой. Пусть <tex>a_j</tex> - их общее значение. Тогда <tex>0 \leqslant a_j \leqslant 1</tex>. Заметим, что <tex>P^n \rho _j</tex> - j-тый столбец матрицы <tex>P^n</tex>. Рассмотрим все <tex>\rho _j</tex> для <tex>j = 1, 2, \ldots</tex>. Тогда <tex>P^n</tex> сходится к матрице А, у которой по строкам стоит один и тот же вектор <tex>\alpha = \{a_1, a_2, \ldots, a_n \}</tex>.
 +
Так как в каждой матрице <tex>P^n</tex> сумма элементов в строке равна 1, то то же самое справедливо и для предельной матрицы А. Теорема доказана.
  
 
== Литература ==
 
== Литература ==
 
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова", стр 93
 
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова", стр 93

Версия 07:09, 13 января 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]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]\exists A: \displaystyle \lim_{n \to \infty}P^n = A[/math]
;

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

Доказательство:

Рассмотрим вектор-столбец [math]\rho _j[/math], у которого j-й элемент равен 1, а все остальные равны 0. Пусть [math]M_n[/math] и [math]m_n[/math] - минимальный и максимальный элементы столбца [math]P^n \rho _j[/math]. Так как [math]P^n \rho _j = P \cdot P^{n-1} \rho _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 \rho _j[/math] сходится к вектору, все элементы которого равны между собой. Пусть [math]a_j[/math] - их общее значение. Тогда [math]0 \leqslant a_j \leqslant 1[/math]. Заметим, что [math]P^n \rho _j[/math] - j-тый столбец матрицы [math]P^n[/math]. Рассмотрим все [math]\rho _j[/math] для [math]j = 1, 2, \ldots[/math]. Тогда [math]P^n[/math] сходится к матрице А, у которой по строкам стоит один и тот же вектор [math]\alpha = \{a_1, a_2, \ldots, a_n \}[/math]. Так как в каждой матрице [math]P^n[/math] сумма элементов в строке равна 1, то то же самое справедливо и для предельной матрицы А. Теорема доказана.

Литература

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