Определение 9.1:
Говорят, что последовательность целочисленных случайных величин $\{\xi_n\}$ образует цепь Маркова,
если для любого $n\in\mathbb{N}$ случайная величина $\xi_n$ независит от случайных величин $\xi_0,\ldots,\xi_{n-2}$.
При этом для любых $n\in\mathbb{N}$, $i,j\in\mathbb{Z}$ обозначают $p_{i,j}^{(n)}:=P(\xi_n=j/\xi_{n-1}=i)$.
Определение 9.2:
Цепь Маркова $\{\xi_n\}$ называется однородной, если вероятности $p_{i,j}^{(n)}$ не зависят от $n$.
При этом для любых $i,j\in\mathbb{Z}$ обозначают $p_{i,j}:=P(\xi_1=j/\xi_0=i)$.
Если число значений случайных величин $\{\xi_n\}$ конечно, то вероятности $p_{i,j}$ образуют квадратную матрицу,
которую называют матрицей переходных вероятностей цепи Маркова $\{\xi_n\}$.
Далее будем рассматривать однородные цепи Маркова с конечным числом состояний.
Пусть $P$ матрица переходных вероятностей цепи Маркова $\{\xi_n\}$.
Для любого $k>1$ обозначим $p_{i,j}(k):=P(\xi_k=j/\xi_0=i)$, $P(k)$ матрица образованная вероятностями $p_{i,j}(k)$, тогда
$$
p_{i,j}(k)=\sum_{s}P(\xi_{k-1}=s/\xi_1=i)p_{s,j}=\sum_{s}p_{i,s}(k-1)p_{s,j}\Rightarrow{P}(k)=P(k-1)P\Rightarrow{P}(k)=P^k.
$$
Таким образом, для любого $k\in\mathbb{N}$ функция распредление случайной величины $\xi_k$ полностью определяется функцией распределения случайной величины $\xi_0$ и
матрицей переходных вероятностей $P$.
Определение 9.3:
Множество $E:=\{E_1,\ldots,E_N\}$ значений,
которые могут принимать случайные величины однородной цепи Маркова $\{\xi_n\}$ называется множеством состояний цепи Маркова.
Состояние $E_i$ называется несущественным, если существует состояние $E_j$ и целое число $t_0>0$ такие,
что $p_{i,j}(t_0)>0$ и для любого $t\in\mathbb{N}$ $p_{j,i}(t)=0$.
В противном случае $E_i$ называется существенным состоянием.
Существенные состояния $E_i$, $E_j$ называются сообщающимися, если существуют целые числа $t>0$, $s>0$ такие, что $p_{i,j}(t)>0$ и $p_{j,i}(s)>0$.
Из определения следует, что множество существенных состояния цепи Мароква разбивается на непересекающиеся подмножества (классы) сообщающихся между собой состояний.
Определение 9.4:
Если цепь Маркова состоит из одного класса существенных сообщающихся состояний, то она называется неразложимой.
В противном случае цепь Маркова называется разложимой.
Определение 9.5: Матрица $P=(p_{i,j})_{m\times{n}}$ называется стохастической, если
Определение 9.6:
Состояние $E_j$ называется возвратным, если $F_j=1$ и невозвратным, если $F_j<1$.
Состояние $E_j$ называется нулевым, если $p_{j,j}\to0$ при $n\to\infty$ и ненулевым в противном случае.
Состояние $E_j$ называется периодическим с периодом $d$,
если возвращение с положительной вероятностью в $E_j$ возможно только за число шагов кратное $d$ и $d$ есть наибольшее число с таким свойством.
Другими словами период $d$ состояния $E_j$ - это НОД множества чисел $\{n\in\mathbb{N}|f_j(n)>0\}$. Ясно также, что если $d\nmid{n}$ $p_{j,j}(n)=f_j(n)=0$.
Утверждение 9.1: Состояние $E_j$ возвратно тогда и только тогда, когда ряд $\sum_{n=1}^{\infty}p_{j,j}(n)$ расходится.
Доказательство:
Доказательство в Боровков А. А.1999 г. "Теория вероятностей" стр. 250.
Теорема 9.1: В неразложимой цепи Маркова все состояния принадлежат к одному типу: если хотябы одно возвратно, то и все возвратны; если хотябы одно нулевое, то и все нулевые; если хотябы одно периодично с периодом $d$, то и все периодичны с периодом $d$.
Доказательство:
Доказательство в Боровков А. А.1999 г. "Теория вероятностей" стр. 251.
Определение 9.7:
Неразложимая цепь Маркова, все состояния которой имеют период $d$ называется периодической цепью с периодом $d$.
Теорема 9.2: Множество $E$ состояний периодической цепи Маркова с периодом $d$ разбивается на непересекающиеся классы $D_0,\ldots,D_{d-1}$ такие, что если $E_i\in{D}_{\alpha}$ и $p_{i,j}>0$ то $E_j\in{D}_{\beta}$, где $\beta:=\alpha+1\pmod{d}$.
Доказательство:
Будем считать, что $E_i\in{D}_{\alpha}$, тогда и только тогда, когда существует $n\in\mathbb{N}$ такое, что $p_{1,i}(n)>0$ и $n=kd+\alpha$, где $k\in\mathbb{N}$.
Так как цепь неразложимая, то все состояния связные, следоваетльно, для любого состояния $E_i\in{E}$ найдётся $n\in\mathbb{N}$ такое, что $p_{1,i}(n)>0$, поэтому
$$E=\bigcup_{\alpha=0}^{d-1}D_{\alpha}.$$
Покажем, что классы $D_0,\ldots,D_{d-1}$ не пересекаются.
Пусть $m,n\in\mathbb{N}$ такие, что $p_{1,i}(m)>0$, $p_{1,i}(n)>0$. Так как цепь неразложима, то существует $s\in\mathbb{N}$ такое, что $p_{i,1}(s)>0$, тогда
$$\begin{cases}p_{1,1}(m+s)\geq{p}_{1,i}(m)p_{i,1}(s)> 0 \\ p_{1,1}(n+s)\geq{p}_{1,i}(n)p_{i,1}(s)>0\end{cases}$$
Так как $d$ это НОД чисел $\{k\in\mathbb{N}\mid{p}_{1,1}(k)>0\}$, то по теореме 8.1 DM
$$\begin{cases}d|(m+s) \\ d|(n+s)\end{cases}\Rightarrow{d}|((m+s)-(n+s))\Rightarrow{d}|(m-n)\Rightarrow{m}\equiv{n}\pmod{d}.$$
Таким образом, состояние $E_i$ может принадлежать только одному классу из $D_0,\ldots{D}_{d-1}$.
Пусть $E_i\in{D}_{\alpha}$ и $p_{i,j}>0$, тогда существует натуральное число $k$ такое,
что $p_{1,i}(kd+\alpha)>0$ и $p_{1,j}(kd+\alpha+1)\geq{p}_{1,i}(kd+\alpha)p_{i,j}>0$, следовательно, $E_j\in{D}_{\alpha+1\pmod{d}}$.
Из теоремы следует, что любое состояние из класса $D_{\alpha}$ с вероятностью 1 переходит в состояние из класса $D_{\alpha+1\pmod{d}}$.
Замечание 9.1:
Из теоремы 9.2 следует, что состояния неразложимой цепи Маркова (НЦМ) с периодом $d$ можно перенумеровать так,
что её матрица перходных вероятностей (МПВ) $\Pi$ представима в виде
$$
\Pi=\begin{pmatrix}
0 & \Pi_{0,1} & 0 & \cdots & 0 \\
0 & 0 & \Pi_{1,2} & \cdots & 0 \\
\cdots & \cdots & \cdots & \cdots & \cdots \\
0 & 0 & 0 & \cdots & \Pi_{d-2,d-1} \\
\Pi_{d-1,0} & 0 & 0 & \cdots & 0
\end{pmatrix}
$$
где $\Pi_{i,j}$ - это МПВ состояний из класса $D_i$ в состояния из класса $D_j$.
Пример 9.1:
Пусть $\{\eta_k\}$ последовательность независимых случайных величин таких, что для любого $k\in\mathbb{N}$ $\eta_k\sim\left(\begin{smallmatrix}1, & 3 \\ 1/2, & 1/2\end{smallmatrix}\right)$.
Для любого $n\in\mathbb{N}$ положим $\xi_n:=\sum_{k=1}^n\eta_k\pmod{4}$.
Тогда последовательность $\{\xi_n\}$ является цепью Маркова с множеством состояний $E:=\{E_0,E_1,E_2,E_3\}=\{0, 1, 2, 3\}$ и МПВ
$$\Pi=\begin{pmatrix}0 & 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 & 0\end{pmatrix}.$$
Обозначив $D_0:=\{E_1,E_3\}$, $D_1:=\{E_0,E_2\}$ и положив $E_0':=E_1$, $E_1':=E_3$, $E_2':=E_0$, $E_3':=E_2$, получим
$$
\Pi=\begin{pmatrix}
0 & \Pi_{0,1} \\
\Pi_{1,0} & 0
\end{pmatrix}=
\begin{pmatrix}
0 & 0 & 1/2 & 1/2 \\
0 & 0 & 1/2 & 1/2 \\
1/2 & 1/2 & 0 & 0 \\
1/2 & 1/2 & 0 & 0
\end{pmatrix}
$$
Лемма 9.1: Если числа $m_1,\ldots,m_r\in\mathbb{N}$ взаимно просты, то существует $n_0\in\mathbb{N}$ такое, что для любого натурального $n>n_0$ существуют $k_1,\ldots,k_r\in\mathbb{N}_0$ такие, что $n=k_1m_1+\cdots+k_rm_r$.
Доказательство:
По теореме 6.5 DM существуют $s_1,\ldots,s_r\in\mathbb{Z}$ такие, что $s_1m_1+\cdots+s_rm_r=1$.
Положим
$$n_0:=(m_1+\dots+m_r)^2\max_{1\geq{i}\geq{r}}{|s_i|}+(m_1+\cdots+m_r).$$
Пусть $n>n_0$, поделим $n$ с остатком на $m_1+\cdots+m_r$, тогда
$$n=k(m_1+\cdots+m_r)+\alpha,$$
где $k,\alpha\in\mathbb{N}_0$ и $\alpha<(m_1+\cdots+m_r)$.
Тогда
$$k=\frac{n-\alpha}{m_1+\cdots+m_r}>\frac{n_0-(m_1+\cdots+m_r)}{m_1+\cdots+m_r}=(m_1+\cdots+m_r)\max_{1\leq{i}\leq{r}}{|s_i|}.$$
Следовательно,
$$n=k(m_1+\cdots+m_r)+\alpha(s_1m_1+\cdots+s_rm_r)=(k+s_1\alpha)m_1+\cdots+(k+s_r\alpha),$$
где для любого $i\in\overline{1,r}$ $k>|s_i|\alpha$, то есть $k+s_i\alpha>0$.
Теорема 9.3: Пусть $\Pi$ - МПВ конечной, ацикличной (период равен 1) НЦМ. Тогда существует $n_2\in\mathbb{N}$ такое, что для любого натурального ${n\geq{n}_2}$ все элементы матрицы $\Pi^n$ положительны.
Доказательство:
Пусть $E_1,\ldots,E_N$ - множество состояний цепи. Для любого $i\in\overline{1,N}$ обозначим $M_i:=\{n\in\mathbb{N}\mid{p}_{i,i}(n)>0\}$,
и зафиксируем $i\in\overline{1,N}$. Так как период цепи равен 1, то существуют
$m_1,\ldots,m_r\in{M_i}$ такие, что $(m_1,\ldots,m_r)=1$. Тогда по лемме 9.1 существует $n_{0_i}\in\mathbb{N}$ такое,
что для любого натурального $n\geq{n}_{0_i}$ существуют $k_1,\ldots,k_r\in\mathbb{N}_0$ такие, что
${n=k_1m_1+\cdots+k_rm_r}$. Тогда
$$
p_{i,i}(n)=p_{i,i}(k_1m_1+\cdots+k_rm_r)\geq{p}_{i,i}(k_1m_1)+\cdots+p_{i,i}(k_rm_r)\geq{p}_{i,i}^{k_1}(m_1)\cdots{p}_{i,i}^{k_r}(m_r)>0.
$$
Таким образом,
$$\forall{i}\in\overline{1,N}\,\exists{n_{0_i}}\in\mathbb{N}:\forall{n}\geq{n_{0_i}}(p_{i,i}(n)>0).$$
Положим $\displaystyle{n}_0:=\max_{1\geq{i}\geq{N}}n_{0_i}$,
тогда
$$\forall{i}\in\overline{1,N}\,\forall{n}\geq{n}_0(p_{i,i}(n)>0),$$
то есть все диагональные элементы матрицы $\Pi^n$ положительны.
Так как цепь Маркова неразложима, то для любых неравных $i,j\in\overline{1,N}$ существует $n_{i,j}\in\mathbb{N}$ такое, что $p_{i,j}(n_{i,j})>0$, тогда
$p_{i,j}(n_{i,j}+n_0)\geq{p}_{i,j}(n_{i,j})p_{j,j}(n_0)>0$ и для числа $\displaystyle{n}_2:=\max_{1\geq{i,j}\geq{N}}(n_{i,j})+n_0$
выполняется утверждение теоремы.
Теорема 9.4: Эргодическая теорема для цепей Маркова.
Если $E_1,\ldots,E_N$ множество состояний конечной и ацикличной (период равен 1) НЦМ, то для любого $i\in\overline{1,N}$ существует предел
$$p_j:=\lim_{n\to\infty}p_{i,j}(n)>0.$$
Доказательство:
Пусть $\Pi$ - МПВ цепи Маркова. По теореме 9.3 существует $n_2\in\mathbb{N}$ такое, что для любого натурального $n>n_2$ матрица $\Pi^n$ положительна.
Для любого $n>n_2$, $j\in\overline{1,N}$ обозначим $M_j(n):=\max_{1\leq{i}\leq{N}}p_{i,j}(n)>0$, $m_j(n):=\min_{1\leq{i}\leq{N}}p_{i,j}(n)>0$.
Тогда для люббых $i,j\in\overline{1,N}$
$$p_{i,j}(n+1)=\sum_{k=1}^Np_{i,k}p_{k,j}(n)\leq{M}_j(n)\sum_{k=1}^Np_{i,j}=M_j(n).$$
Следовательно, для любого $j\in\overline{1,N}$ последовательность $M_j(n)$ неубывает.
Аналогично показыавается, что последовательность $m_j(n)$ невозрастает. Фиксируем различные $i_1,i_2\in\overline{1,N}$, тогда
$$
\begin{cases}
p_{i_1,j}(n)=\sum_{k=1}^Np_{i_1,k}(n_2)p_{k,j}(n-n_2) \\
p_{i_2,j}(n)=\sum_{k=1}^Np_{i_2,k}(n_2)p_{k,j}(n-n_2)
\end{cases}\Rightarrow
p_{i_1,j}(n)-p_{i_2,j}(n)=\sum_{k=1}^N\bigl(p_{k,j}(n-n_2)(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))\bigr)
$$
Обозначим
$$E^+:=\{k\in\overline{1,N}\mid{p}_{i_1,k}(n_2)-p_{i_2,k}(n_2)\geq0\},$$
$$E^-:=\{k\in\overline{1,N}\mid{p}_{i_1,k}(n_2)-p_{i_2,k}(n_2)<0\},$$
тогда
$$
\sum_{k=1}^N(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))=\sum_{k=1}^Np_{i_1,k}(n_2)-\sum_{k=1}^Np_{i_2,k}(n_2)=1-1=0\Rightarrow
\sum_{k\in{E}^+}(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))=-\sum_{k\in{E}^-}(p_{i_1,k}(n_2)-p_{i_2,k}(n_2)).
$$
Следовательно,
\begin{multline*}
p_{i_1,k}(n_2)-p_{i_2,k}(n_2)=\sum_{k\in{E}^+}\bigl(p_{k,j}(n-n_2)(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))\bigr)+
\sum_{k\in{E}^-}\bigl(p_{k,j}(n-n_2)(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))\bigr)\leq\\\leq
{M_j}(n-n_2)\sum_{k\in{E}^+}(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))+m_j(n-n_2)\sum_{k\in{E}^-}(p_{i_1,k}(n_2)-p_{i_2,k}(n_2))=
h(i_1,i_2)(M_j(n-n_2)-m_j(n-n_2))\leq{h}(M_j(n-n_2)-m_j(n-n_2)),
\end{multline*}
где
$$h(i_1,i_2):=\sum_{k\in{E}^+}(p_{i_1,k}(n_2)-p_{i_2,k}(n_2)),\,h:=\max_{1\leq{i}_1,i_2\leq{N}}h(i_1,i_2)<1.$$
Таким образом,
$$
\forall{i}_1,i_2\in\overline{1,N}\bigl(p_{i_1,j}(n)-p_{i_2,j}(n)\leq{h}(M_j(n-n_2)-m_j(n-n_2))\bigr)\Rightarrow{M}_j(n)-m_j(n)\leq{h}(M_j(n-n_2)-m_j(n-n_2)).\,(*)
$$
Поделим с остатком $n$ на $n_2$, тогда $n=kn_2+\alpha$, где $0\leq\alpha<n_2$. Применив последовательно $k$ раз неравенство $(*)$ получим
$$
M_j(n)-m_j(n)=M_j(kn_2+\alpha)-m_j(kn_2+\alpha)leq{h}(M_j((k-1)n_2+\alpha)-m_j((k-1)n_2+\alpha))\leq\cdots\leq{h}^k(M_j(\alpha)-m_j(\alpha))\leq{h^k},
$$
где последнее неравенство в силу того, что $M_j(\alpha)\leq1$. Так как если $n\to\infty$, то $k\to\infty$ и последовательность $M_j(n)-m_j(n)$ неотрицательна,
следовательно, по п. 2 теоремы 4.2.3 MA ("теорема о двух милиционерах") существует предел
$$\lim_{n\to\infty}(M_j(n)-m_j(n))=\lim_{k\to\infty}h^k=0.$$
Так как последовательности $M_j(n)$ и $m_j(n)$ монотонны и ограничены,
то по теореме 4.3.2 MA существуют пределы $\lim_{n\to\infty}M_j(n)$, $\lim_{n\to\infty}m_j(n)$ и
по теореме 4.2.2 MA
$$
\lim_{n\to\infty}(M_j(n)-m_j(n))=\lim_{n\to\infty}M_j(n)-\lim_{n\to\infty}m_j(n)=0\Rightarrow{p_j}:=\lim_{n\to\infty}M_j(n)=\lim_{n\to\infty}m_j(n)>0,
$$
Так как для любых $n\in\mathbb{N}$, $i\in\overline{1,N}$ $m_j(n)\leq{p}_{i,j}(n)\leq{M}_j(n)$,
то по п. 2 теоремы 4.2.3 MA для любого $i\in\overline{1,N}$ существует предел
$$\lim_{n\to\infty}p_{i,j}(n)=p_j.$$
Из теоремы следует, что цепь Маркова "забывает" откуда она вышла.
Множество чисел $p_1,\ldots,p_N$ может рассматриваться как распределение случайной величины, так как для любого $k\in\overline{1,N}$ $p_k>0$ и
$$\sum_{k=1}^Np_k=\sum_{k=1}^N\lim_{n\to\infty}p_{i,k}(n)=\lim_{n\to\infty}\sum_{k=1}^Np_{i,k}(n)=1.$$
Следствие 9.1: Если НЦМ конечна и ациклична, то все её состояния ненулевые и возвратные.
Доказательство:
Так как по теореме 9.4 для любого $j\in\overline{1,N}$ существует предел
$$\lim_{n\to\infty}p_{j,j}(n)=p_j>0,$$
то состояние $E_j$ ненулевое и по п. 2 теоремы 7.1.1 MA ряд $\sum_{n=1}^{\infty}p_{j,j}(n)$
расходится.
Следовательно, по утверждению 9.1 состояние $E_j$ возвратно.
Замечание 9.2:
Если для любых $i,j\in\overline{1,N}$ существует положительный предел $\lim_{n\to\infty}p_{i,j}(n)$,
то для любых $i,j\in\overline{1,N}$ существует $n_{i,j}\in\mathbb{N}$ такое, что для любого натурального $n>n_{i,j}$ $p_{i,j}(n)>0$.
То есть все состояния сообщаются как минимум за $\max_{1\leq{i}\leq{N}}n_{i,j}$ шагов, следовательно, цепь Маркова неразложима.
Определение 9.8:
Если для цепи Маркова с множеством состяний $E_1,\ldots,E_N$ для любого $i\in\overline{1,N}$ существуюте пределы
$$p_1:=\lim_{n\to\infty}p_{i,1}(n),\ldots,p_N:=\lim_{n\to\infty}p_{i,N}(n),$$
то распределение $p_1,\ldots,p_N$ называется предельным распределением цепи Маркова.
Теорема 9.5: Если у цепи Маркова с множеством состояний $E_1,\ldots,E_N$ и матрицей переходных вероятностей $\Pi$ существует предельное распределение $\overline{p}=(p_1,\ldots,p_N)$, то оно является единственным решением системы уравнений $$ \begin{cases} x_k=\sum_{m=1}^Nx_mp_{mk},k\in\overline{1,N},\\ \sum_{m=1}^Nx_m=1 \end{cases} $$
Доказательство:
Фиксируем $i\in\overline{1,N}$, тогда для любого $n\in\mathbb{N}$
$$\sum_{m=1}^Np_{im}(n)=1.$$
Переходя к пределу при $n\to\infty$ получим
$$\lim_{n\to\infty}\sum_{m=1}^Np_{im}(n)=\sum_{m=1}^N\lim_{n\to\infty}p_{im}(n)=\sum_{m=1}^Np_m=1.$$
Для любого $k\in\overline{1,N}$
$$p_{ik}(n+1)=\sum_{m=1}^Np_{im}(n)p_{mk}.$$
Переходя к пределу при $n\to\infty$ получим для любого $k\in\overline{1,N}$
$$p_k=\lim_{n\to\infty}\sum_{m=1}^Np_{im}(n)p_{mk}=\sum_{m=1}^Np_mp_{mk}.$$
Докажем, что решение $\overline{p}$ единственно. Пусть $\overline{q}:=(q_1,\ldots,q_n)$ решение системы уравнений, тогда для любого $n\in\mathbb{N}$
$$
\left(\forall{k}\in\overline{1,N}q_k=\sum_{m=1}^Nq_mp_{mk}\right)\Rightarrow\overline{q}=\overline{q}\Pi\Rightarrow\overline{q}=\left(\overline{q}\Pi\right)\Pi=\overline{q}\Pi^2\Rightarrow\ldots
\Rightarrow\overline{q}=\overline{q}\Pi^n\Rightarrow\left(\forall{k}\in\overline{1,N}q_k=\sum_{m=1}^Nq_mp_{mk}\right)
$$
Переходя к пределу при $n\to\infty$ для любого $k\in\overline{1,N}$ получим
$$q_k=\sum_{m=1}^Nq_mp_{k}=p_k\sum_{m=1}^Nq_m=p_k.$$
Следствие 9.2: Если цепь Маркова удовлетворяет условиям эргодической теоремы (теорема 9.4) и её матрица переходных вероятностей дважды стохастическая, то предельное распределение такой цепи равномерно.
Доказательство:
Вектор $\overline{q}:=(q_1,\ldots,q_N)=:(1/N,\ldots,1/N)\in\mathbb{R}^N$ удовлетворяет системе уравнений
$$
\begin{cases}
x_k=\sum_{m=1}^Nx_mp_{mk},k\in\overline{1,N},\\
\sum_{m=1}^Nx_m=1.
\end{cases}
$$
Действительно, так как матрица переходных вероятностей дважды стохостическая, то для любого $k\in\overline{1,N}$
$$\sum_{m=1}^Nq_mp_{mk}=\sum_{m=1}^N\frac1{N}p_{mk}=\frac1{N}\sum_{m=1}^Np_{mk}=\frac1{N}=q_k,$$
и
$$\sum_{m=1}^Np_m=\sum_{m=1}^N\frac1{N}=1.$$
Следовательно, по теореме 9.5 вектор $\overline{q}$ является предельным распределением для данной цепи Маркова.
Пример 9.2:
Пусть $\{\eta_k\}$ последовательность независимых одинаково распределённых величин такая, что для любого $k\in\mathbb{N}$
$$\eta_k\sim\begin{pmatrix}0, & 1, & \ldots, & N-1, & N \\ q_0, & q_1, & \ldots, & q_{N-1}, & q_N\end{pmatrix}.$$
Для любого $n\in\mathbb{N}$ положим
$$\xi_n:=\sum_{k=1}^n\eta_k\pmod{N+1},$$
тогда последовательность $\{\xi_n\}$ является цепью Маркова удовлетворяющей условиям теоремы 9.4 с матрицей переходных вероятностей
$$
\Pi=\begin{pmatrix}
q_0 & q_1 & \ldots & q_{N-1} & q_N \\
q_N & q_0 & \ldots & q_{N-2} & q_{N-1} \\
\cdots & \cdots & \cdots & \cdots & \cdots \\
q_2 & q_3 & \ldots & q_0 & q_1 \\
q_1 & q_2 & \ldots & q_N & q_0 \\
\end{pmatrix}
$$
Очевидно, что матрица $\Pi$ является дважды стохастической, следовательно, по следствию 9.2 для любого $j\in\overline{0,N}$
$$p_j:=\lim_{n\to\infty}p_{i,j}(n)=\frac1{N+1}.$$
Теорема 9.6: Пусть $\{\xi_n\}$ цепь Макова с периодом $d>1$, $D_0,\ldots,D_{d-1}$ непересекающиеся классы состояний такие, что для любых $\alpha\in\overline{0,d-1}$, $E_i\in{D}_{\alpha}$, если $p_{i,j}>0$, $E_j\in{D}_{\alpha+1\pmod{d}}$. Тогда для любых $\alpha\in\overline{1,d-1}$, $r\in\overline{0,d-1}$, $E_i\in{D}_{\alpha}$, $E_j\in{D}_{\alpha+r\pmod{d}}$ существует предел $$p_j:=\lim_{k\to\infty}p_{i,j}(kd)>0.$$ Предела вероятности $p_{i,j}(n)$ при $n\to\infty$ не существует.
Доказательство:
По теореме 9.2 множество состояний данной цепи Маркова есть $E=D_0\cup\cdots\cup{D}_{d-1}$.
При этом если $\Pi$ матрица переходных вероятностей данной цепи, то
$$
\Pi^d=
\begin{pmatrix}
\Pi_0 & 0 & \ldots & 0 \\
0 & \Pi_1 & \ldots & 0 \\
\cdots & \cdots & \cdots & \cdots \\
0 & 0 & \ldots & \Pi_{d-1}
\end{pmatrix}
$$
где для любого $\alpha\in\overline{0,d-1}$ $\Pi_{\alpha}:=\{p_{i,j}(d)\mid{E}_i,E_{j}\in{D}_{\alpha}\}$.
Пусть $\xi_0\in{D}_{\alpha}$, тогда для любого $k\in\mathbb{N}$ $\xi_{kd}\in{D}_{\alpha}$, то есть $\{\xi_{kd}\}$
НЦМ с матрицей переходных вероятностей $\Pi_{\alpha}$.
Если предположить, что НЦМ $\{\xi_{kd}\}$ имеет период $d_1>1$, то период исходной цепи Маркова равнялся бы $dd_1>d$. Следовательно,
НЦМ $\{\xi_{kd}\}$ ациклична и для можно применить теорему 9.4, то есть для любого
$\alpha\in\overline{0,d-1}$, если $E_j\in{D}_{\alpha}$, то для любого $E_i\in{D}_{\alpha}$ существует предел
$$p_j:=\lim_{k\to\infty}p_{i,j}(kd)>0.$$
Таким образом, утверждение доказано при $r=0$. Фиксируем $\alpha\in\overline{0,d-1}$, $r\in\overline{1,d-1}$ и $E_j\in{D}_{\beta}$,
где $\beta:=\alpha+r\pmod{d}$. Тогда для любого $E_i\in{D}_{\alpha}$
$$
p_{i,j}(kd+r)=\sum_{m=1}^Np_{i,m}(r)p_{m,j}(kd)=\sum_{m:E_m\in{D}_{\beta}}p_{i,m}(r)p_{m,j}(kd)\Rightarrow\exists\lim_{k\to\infty}p_{i,j}(kd+r)=
p_j\sum_{m:E_m\in{D}_{\beta}}p_{i,j}(r)=p_j>0.
$$
Предела последовательности $p_{i,j}(n)$ при $n\to\infty$ не существует,
по критерию Коши (теорема 4.3.1 MA) так как для любого $n_0>0$ существует $k\in\mathbb{N}$ такое,
что $kd+r>n_0$ и при этом
$$p_{i,j}(kd+r)-p_{i,j}(kd+r+1)=p_j-0=p_j.$$
Теорема 9.7: Пусть $\{\xi_n\}$ конечная, ацикличная цепь Маркова с множеством состояний $E_1,\ldots,E_N$. Обозначим через $S_0$ множество всех чисел таких, что для любого $k\in{S}_0$ состояние $E_k$ несущественно, через $S_1$ множество всех чисел таких, что для любого $k\in{S}_1$ состояние $E_k$ существенно. Тогда если $i,j\in{S}_0$, то существует предел $$\lim_{n\to\infty}p_{i,j}(n)=0,$$ если $i\in{S}_0$, $j\in{S}_1$, то существует предел $$p_j:=\lim_{n\to\infty}p_{i,j}(n)>0.$$
Доказательство: