Изменения
Новая страница: «== Формулировка теоремы == '''Формулировка''' С вероятностью, равной 1, марковская цепь перей…»
== Формулировка теоремы ==
'''Формулировка'''
С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние.
'''Альтернативная формулировка'''
Пусть '''''P''''' - матрица переходов, где элемент <math>p_{ij}</math> равен вероятности перехода из i-го состояния в j-ое, а <math>p^{(t)}</math> вектор вероятностей нахождения в определенном состоянии на шаге ''t'', тогда, если все элементы матрицы переходных состояний '''''P''''' положительны, то при ''t'' , стремящимся к бесконечности, вектор <math>p^{(t)}</math> стремится к вектору <math>\bar p</math>, являющемуся единственному решению системы <math>p \times P</math> <math>=</math> <math> p </math>
== Доказательство теоремы ==
Обозначим через ''d'' минимальный элемент матрицы '''''P''''' (''d''>0). Введем функцию ''f'', переводящую вероятностный вектор в другой: <math>f=p \times P</math>. Отображение ''f'' сжимающиеся, т.е. отношение "расстояния" между ''f(p)'' и ''f(q)'' к расстоянию между векторами p и q не превосходит, некоторого ''R'' (''R''<1).
Пусть расстояние между ''p'' и ''q'' равно: <math>r(p,r) = \sum_{i} {|p_i - q_i|}</math>
Введем матрицу '''''D''''', элементы которой на ''d'' меньше, чем у '''''P'''''. Тогда <math>f(p) = p \times 1 + p \times D</math>. Таким образом <math>f(p) - f(q) = {(p- q)} \times D</math>.
Подставляем это выражение в определение расстояния и получаем выражение:
<math>r(f(p), f(q)) = \sum_{i} {|\sum_{j}{p_j D_{ji}} - \sum_{j}{q_i D_{ji}}|} <= \sum_{i}{\sum_{j}{D_{ij}|p_j - q_j|}} = r(p,q) * (1- md)</math>
Где <math>(1-md)< 1</math>, следовательно оно равно ''R''.
В итоге получаем <math>r(pP,qP)\leqslant R \times r(p,q)</math>, из которого следует для любого ''n'' <math>r(pP^n,qP^n)\leqslant R^n \times r(p,q)</math>. Отсюда получаем сходимость <math>p^{(0)}P^n</math>. И переходя в исходном уравнении к пределу в итоге получаем уравнение для предельного вектора <math>\bar p</math> <math>\bar p = \bar p P</math>.
Единственность решения для уравнения следует из этого же неравенства. Если <math>p_1</math> и <math>p_2</math> решения системы, то получаем <math>r(p_1,p_2)=(r(p_1P,p_2P)\leqslant R \times r(p_1,p_2)</math>, что возможно только при совпадении этих решений.
== Используемая литература ==
И.В. Романовский "Дискретный анализ", 2003
'''Формулировка'''
С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние.
'''Альтернативная формулировка'''
Пусть '''''P''''' - матрица переходов, где элемент <math>p_{ij}</math> равен вероятности перехода из i-го состояния в j-ое, а <math>p^{(t)}</math> вектор вероятностей нахождения в определенном состоянии на шаге ''t'', тогда, если все элементы матрицы переходных состояний '''''P''''' положительны, то при ''t'' , стремящимся к бесконечности, вектор <math>p^{(t)}</math> стремится к вектору <math>\bar p</math>, являющемуся единственному решению системы <math>p \times P</math> <math>=</math> <math> p </math>
== Доказательство теоремы ==
Обозначим через ''d'' минимальный элемент матрицы '''''P''''' (''d''>0). Введем функцию ''f'', переводящую вероятностный вектор в другой: <math>f=p \times P</math>. Отображение ''f'' сжимающиеся, т.е. отношение "расстояния" между ''f(p)'' и ''f(q)'' к расстоянию между векторами p и q не превосходит, некоторого ''R'' (''R''<1).
Пусть расстояние между ''p'' и ''q'' равно: <math>r(p,r) = \sum_{i} {|p_i - q_i|}</math>
Введем матрицу '''''D''''', элементы которой на ''d'' меньше, чем у '''''P'''''. Тогда <math>f(p) = p \times 1 + p \times D</math>. Таким образом <math>f(p) - f(q) = {(p- q)} \times D</math>.
Подставляем это выражение в определение расстояния и получаем выражение:
<math>r(f(p), f(q)) = \sum_{i} {|\sum_{j}{p_j D_{ji}} - \sum_{j}{q_i D_{ji}}|} <= \sum_{i}{\sum_{j}{D_{ij}|p_j - q_j|}} = r(p,q) * (1- md)</math>
Где <math>(1-md)< 1</math>, следовательно оно равно ''R''.
В итоге получаем <math>r(pP,qP)\leqslant R \times r(p,q)</math>, из которого следует для любого ''n'' <math>r(pP^n,qP^n)\leqslant R^n \times r(p,q)</math>. Отсюда получаем сходимость <math>p^{(0)}P^n</math>. И переходя в исходном уравнении к пределу в итоге получаем уравнение для предельного вектора <math>\bar p</math> <math>\bar p = \bar p P</math>.
Единственность решения для уравнения следует из этого же неравенства. Если <math>p_1</math> и <math>p_2</math> решения системы, то получаем <math>r(p_1,p_2)=(r(p_1P,p_2P)\leqslant R \times r(p_1,p_2)</math>, что возможно только при совпадении этих решений.
== Используемая литература ==
И.В. Романовский "Дискретный анализ", 2003
