Теорема о поглощении — различия между версиями
Hazzus (обсуждение | вклад) (Источники) |
Hazzus (обсуждение | вклад) (Чуть подробнее расписал рассуждения в конце) |
||
Строка 69: | Строка 69: | ||
− | Рассмотрим путь из <tex>i</tex>-го состояния в поглощающее, равное <tex>j</tex>. Пусть <tex> | + | Рассмотрим путь из <tex>i</tex>-го состояния в поглощающее, равное <tex>j</tex>. Пусть <tex>p_{i}<1</tex> — вероятность того, что через <tex>m_i</tex> шагов из шага <tex>i</tex> не попадет в поглощающее состояние. |
Пусть <tex>m = \max(m_i)</tex>, а <tex>p = \max(p_i)< 1</tex> | Пусть <tex>m = \max(m_i)</tex>, а <tex>p = \max(p_i)< 1</tex> | ||
− | Тогда | + | Тогда вероятность перехода в состояние <tex>j</tex> на шаге <tex>m</tex> равна <tex>\sum_{j} {q^{m}_{ij}}</tex>, где <tex>q_{ij}^{m}</tex> — элемент матрицы <tex>Q^{m}</tex>. |
+ | |||
+ | В то же время, <tex>\sum_{j} {q^m_{ij}}\leqslant p</tex>. Возведем обе части в степень <tex>k \rightarrow \infty</tex>, получим: <tex>\sum_{j} {q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex> | ||
В итоге получаем, что непоглощающие состояния стремятся к <tex>0</tex>, а значит поглощающие в итоге приходят к <tex>1</tex>, т.е. цепь приходит в поглощающее состояние. | В итоге получаем, что непоглощающие состояния стремятся к <tex>0</tex>, а значит поглощающие в итоге приходят к <tex>1</tex>, т.е. цепь приходит в поглощающее состояние. |
Версия 16:58, 12 марта 2018
Определение: |
Матрицу | называют непоглощающей, если она не содержит поглощающих состояний. То есть
Определение: |
Стохастическую матрицу с поглощающими состояниями и непоглощающими, можно перевести в каноническую форму:
где , — единичная матрица ( ), — нулевая матрица ( ), — ненулевая поглощающая матрица ( ) и — непоглощающая ( ). Первые состояний переходные и последние состояний поглощающие. |
Теорема (о поглощении): |
Если цепь поглощающая, то с вероятностью, равной 1, она перейдет в поглощающее состояние. |
Доказательство: |
Пусть матрица переходов, где элемент равен вероятности перехода из -го состояния в -ое. Приведем ее в каноническую форму: —
. Произведение единичной матрицы на саму себя есть единичная матрица ( ); — некоторые значения (не важны для доказательства теоремы, т.к. чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0).Продолжив вычисления, получим, что имеет следующий вид: .Докажем, что , при .
Тогда вероятность перехода в состояние на шаге равна , где — элемент матрицы .В то же время, В итоге получаем, что непоглощающие состояния стремятся к . Возведем обе части в степень , получим: , а значит поглощающие в итоге приходят к , т.е. цепь приходит в поглощающее состояние. |
Литература
- Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"