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

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

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

С вероятностью, равной 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}}|} \lt = \sum_{i}{\sum_{j}{D_{ij}|p_j - q_j|}} = r(p,q) * (1- md)[/math]

Где [math](1-md)\lt 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