На главную   ::   Содержание



Дискретные цепи Маркова: классификация состояний, основная предельная теорема

Пусть неограниченно повторяется одно и то же испытание, имеющее не более, чем счетное число исходов.

Определение 1.   Будем называть последовательность с.в. $ X_i, i\geqslant 0$, принимающих значения из целых неотрицательных чисел, цепью Маркова, если условная вероятность (вероятность перехода между состояниями) зависит только от текущего состояния,

$\displaystyle P(X_n=j\vert X_0=k_0,\dots,X_{n-1}=i)=P(X_n=j\vert X_{n-1}=i)=p_{ij}^{(n)}.$

Определение 2.   Цепь маркова называется однородной, если $ p_{ij}^{(n)}=p_{ij}$ (не зависят от номера шага).

Вероятности перехода образуют стохастическую матрицу $ \vert\vert p_{ij}\vert\vert$ (где $ \sum_{j}p_{ij}=1, p_{ij}\geqslant 0$). Будем обозначать ее $ P$. Легко проверить, что матрица вероятностей переходов за $ k$ шагов будет $ P^k$. Это доказывается по индукции. Будем считать, что $ p_{ij}(n)$--вероятность перехода $ i\to j$ за $ n$ шагов. Кроме того, задается начальное распределение цепи -- $ P_0$ -- вектор, показывающий вероятность нахождения цепи в начальный момент времени в данном состоянии. Тогда распределение за $ n$ шагов записывается как $ P_0P^n$.

Определение 3. (Классификация состояний)   Состояние цепи называется несущественным, если $ \exists  j,
\exists  n_0:\quad p_{ij}(n_0)>0$ (в этом случае говорят, что $ j$ достижимо из $ i$) и одновременно $ \forall  n \quad p_{ij}(n)=0$ (можно уйти в какое-то состояние, из которого невозможно вернуться). В противном случае оно называется существенным. Если $ \exists 
t,\exists  s:\quad p_{ij}(t)>0,p_{ji}(s)>0$, то состояния $ i,j$ называются сообщающимися. Обозначим $ v^{(i)}(n)$ -- вероятность того, что цепь вернется в состояние $ i$, стартовав из состояния $ i$. Состояние $ i$ называется возвратным, если $ \sum\limits_{n}
v^{(i)}(n)=1$. Если $ \sum\limits_{n} v^{(i)}(n)<1$, то состояние называется невозвратным. Можно доказать, что состояние является возвратным $ \Leftrightarrow$ $ \sum\limits_{n} p_{ii}(n)=\infty$. Состояние называется периодическим, если возвращение с положительной вероятностью возможно только за число шагов, кратное $ d>1$. Момент, в который цепь возвращается в состояние, из которого стартовала, называется моментом регенерации. Если $ \lim_{n\to\infty}
p_{ii}(n)=0$, то состояние называется нулевым, в противном случае ненулевым. Можно показать, что невозвратное состояние является нулевым, и наоборот, ненулевое -- возвратным, это непосредственно следует из сходимости ряда $ \sum p_{ii}(n)$, который расходится при возвратности состояния и сходится при невозвратности, тогда необходимо общий член стремится к нулю. Существует также возвратно-нулевое состояние -- для него ряд расходится, хотя общий член ряда все равно стремится к нулю. Заметим, что в невозвратное состояние цепь возвращается лишь конечное число раз.

Теорема 1.   Все состояния, достижимые из возвратного, сообщаются и являются возвратными, т.е. образуют замкнутый класс возвратных состояний.

Доказательство. Рассмотрим состояние $ j$, достижимое из $ i$. Пусть $ i$ -- возвратное, предположим, что $ p_{ji}(n)=0\quad
\forall  n$. Тогда с положительной вероятностью цепь не могла бы возвратиться из $ j$ в $ i$, что противоречит возвратности состояния $ i$. Значит, все состояния сообщаются с $ i$, а значит, сообщаются между собой (хотя бы через состояние $ i$). Кроме того, $ \blacksquare$

Замечание 1.   Пусть в цепи имеются невозвратные состояния, обозначим множество их $ E_0$. Если $ \vert E_0\vert=\infty$, то цепь может по цепочке невозвратных состояний уйти на бесконечность, иначе если их конечное число, то цепь через некоторое время перейдет в некоторый класс возвратных состояний и останется там.

Определение 4.   Цепь называется неприводимой, если все состояния ее образуют единственный класс либо невозвратных, либо возвратных состояний.

Определение 5.   Цепь называется непериодической, если все ее состояния непериодические.

Определение 6.   Цепь называется эргодичной, если для каждого ее состояния $ j$ существует независящий от $ i$ предел $ \lim_{n\to\infty}p_{ij}(n)>0$.

Определение 7.   Вектор $ \pi$ называется стационарным распределением цепи, если $ \pi>\mathbf 0$, $ \sum\pi_i=1$, $ \pi=\pi
P$.

Теорема 2. (солидарности)   В неприводимой цепи все состояния принадлежат одному типу: если хоть одно возвратно, то все возвратны, если хоть одно нулевое, то все нулевые, если хоть одно периодично, то все периодичны.

Теорема 3.   В неприводимой непериодической цепи Маркова возможны два случая:

Либо $ \forall i,j\quad p_{ij}(n)\to 0$ -- цепь уходит на бесконечность,

либо $ \forall i,j\quad p_{ij}(n)\to \pi_j>0$ -- тогда цепь эргодична и $ \pi$ -- единственное стационарное распределение.

Замечание 2.   Обозначим $ \tau_i$ -- независимые случайные величины, времена возвращения в состояние $ i$, стартовав из $ i$. Тогда для неприводимой непериодической цепи, в которой хотя бы одно состояние возвратно (тогда и все возвратны) по предыдущей теореме существует стационарное распределение, и оно выражается как $ \pi_i=\frac1{E\tau_i}$.

Теорема 4. (достаточное условие Мустафы)   Неприводимая непериодическая цепь Маркова эргодична, если $ \exists 
\varepsilon>0, i_0, \{x_j\}_{j\geqslant 0}:$

\begin{displaymath}\quad
\begin{cases}\sum\limits_j p_{ij} x_j \leqslant x_i-\v...
... \sum\limits_j p_{ij}x_j\leqslant\infty\quad
i<i_0\end{cases}\end{displaymath}

Последнее условие можно интерпретировать так: полагая $ x_j=j$, получим, что $ \sum\limits_j p_{ij}x_j=\sum\limits_j p_{ij}
j=E(X_{n+1}\vert X_n=i)$, тогда условие $ E(X_{n+1}\vert X_n=i)\leqslant
i-\varepsilon$ означает, что на больших значениях происходит отрицательное смещение цепи. Для малых же значений получается аналогичным образом условие $ E(X_{n+1}\vert X_n=i)<\infty$, т.е. исключен скачок цепи прямо в бесконечность.

На главную   ::   Содержание