\documentclass{../../common/topic}

\TopicSetup
{
  number=17,
  title={Марковски вериги с дискретно време. Класификация на състоянията. Ергодична теорема. Приложения.},
  basedate={25 юни 2019},
  author={Янис Василев}
}

% Bibliography
\addbibresource{./references.bib}

\begin{document}

\maketitle

\section{Теория}

Теорията е базирана на \cite{Божкова2012Лекции}, но някои неща са заимствани от \cite{Боровков1999Вероятности}. Ергодичната теорема е отчасти базирана на \cite{Halidias2017}.

\subsection{Анотация}

Изложената анотацията е взета от \cite{Syllabus}.

\begin{enumerate}
  \item Дефиниция за марковска верига.
  \item Уравнения на Чепмен-Колмогоров.
  \item Класификация на състоянията - критерии за преходност и възвратност, ергодичност.
  \item Гранични вероятности.
  \item Стационарни гранични разпределения.
  \item Ергодична теорема.
\end{enumerate}

\subsection{Основни понятия}

Ще считаме, че е фиксирано някакво вероятностно пространство \( (\Omega, \mscrF, \Prob) \).

\begin{definition}
  \textbf{Случаен процес с дискретно време} наричаме редица от случайни величини \( \set{ \xi_0, \xi_1, \ldots } \).

  Ще предполагаме, че всички \( \xi_0, \xi_1, \ldots \) са дискретни със стойности неотрицателни цели числа.

  Ако \( \xi_n = i \), ще казваме, че процесът е в \textbf{състояние} \( i \) в \textbf{момента} \( n \).

  Вероятността \( \Prob(\xi_n = j \mid \xi_{n-1} = i) \) наричаме \textbf{вероятност за преход} от \( i \) към \( j \) в момента \( n \). Ако вероятностите за преход не зависят от момента, казваме, че процесът е \textbf{стационарен}.

  Процесът \( \set{ \xi_0, \xi_1, \ldots } \) наричаме \textbf{марковска верига}, ако за произволно цяло число \( n > 0 \) и състояния \( j_0, \ldots, j_n \) е изпълнено
  \begin{equation*}
    \Prob(\xi_n = j_n \mid \xi_{n-1} = j_{n-1}, \xi_{n-2} = j_{n-2}, \ldots, \xi_0 = j_0) = \Prob(\xi_n = j_n \mid \xi_{n-1} = j_{n-1}).
  \end{equation*}

  Ако означим \( \sigma(\xi_k) \coloneqq \set{ \xi_k^{-1}(B) \mid B \in \mfrakB(\BbbR) } \), горното условие може да се запише и чрез
  \begin{equation*}
    \Prob(\xi_n = j_n \mid \sigma(\xi_{n-1}), \sigma(\xi_{n-2}), \ldots, \sigma(\xi_0)) = \Prob(\xi_n = j_n \mid \sigma(\xi_{n-1})).
  \end{equation*}
\end{definition}

\begin{remark}
  Предполагаме, че случайните величини \( \xi_0, \xi_1, \ldots \) могат да приемат за стойности произволни положителни цели числа. Затова ще работим с безкрайни вектори и матрици. Поради нормираността и неотрицателността на вероятностната мярка, обаче, работата с тези вектори и матрици няма да ни създава проблеми.
\end{remark}

С \( V \) ще означаваме линейното пространство от редици от положителни цели числа, а с \( V \times V \) пространството от безкрайни матрици от положителни цели числа.

Ще разгледаме само еднородни марковски вериги, за които са зададени вектор от начални вероятности \( B = (b_0, b_1, \ldots) \in V \) и матрица на преходите
\begin{align*}
  P = \begin{pmatrix}
    p_{00} & p_{01} & p_{02} & \ldots \\
    p_{10} & p_{11} & p_{12} & \ldots \\
    p_{20} & p_{21} & p_{22} & \ldots \\
    \vdots & \vdots & \vdots & \ddots
  \end{pmatrix} \in V \times V,
\end{align*}
така че са изпълнени \( \Prob(\xi_0 = i) = b_i \) и \( \Prob(\xi_1 = j \mid \xi_0 = i) = p_{ij} \) за произволни състояния \( i \) и \( j \).

\begin{definition}
  Векторът \( v \in V \) наричаме \textbf{стохастичен}, ако елементите му са неотрицателни и се сумират до единица. Матрицата \( A \in V \times V \) наричаме \textbf{(дясно) стохастична}, ако всеки неин ред е стохастичен.
\end{definition}

\begin{remark}
  Горната дефиниция се пренася без изменения върху крайномерни линейни пространства.
\end{remark}

\begin{proposition}
  Вектор-редът \( B \) от начални вероятности и матрицата на преходите \( P \) на една марковска верига са стохастични.
\end{proposition}
\begin{proof}
  Тъй като векторът \( B \) напълно описва разпределението на \( \xi_0 \), елементите му се сумират до единица.

  За фиксирано число \( i \) дефинираме събитието \( A_i \coloneqq \set{ \omega \in \Omega \mid \xi_0(\omega) = i } \). Тогава \( i \)-тият ред на матрицата \( P \) напълно описва условното разпределение
  \begin{equation*}
    \Prob(\xi_1 = j \mid A_i)
    =
    \Prob(\xi_1 = j \mid \xi_0 = i).
  \end{equation*}

  Следователно
  \begin{equation*}
    \sum_{j=0}^\infty p_{ij}
    =
    \sum_{j=0}^\infty \Prob(\xi_1 = j \mid \xi_0 = i)
    =
    \sum_{j=0}^\infty \Prob(\xi_1 = j \mid A_i)
    =
    1.
  \end{equation*}
\end{proof}

\subsection{Уравнения на Чепмен-Колмогоров}

Нека е дадена марковска верига с начални вероятности \( B \) и матрица на преходите \( P \).

Означаваме с \( p^{(n)}_{ij} \) вероятността да преминем от състояние \( i \) в състояние \( j \) за \( n \) стъпки, т.е.
\begin{equation*}
  p^{(n)}_{ij} \coloneqq \Prob(\xi_n = j \mid \xi_0 = i).
\end{equation*}

\begin{lemma}\label{thm:transition_matrix_power}
  За произволно цяло \( n > 0 \) е изпълнено, че \( n \)-кратната степен \( P^n \) на матрицата \( P \) има елементи \( p_{ij}^{(n)} \).
\end{lemma}
\begin{proof}
  Ще докажем теоремата по индукция. Случаят \( n = 1 \) е тривиален, тъй като \( P \) по определение е матрицата от преходни вероятности за една стъпка.

  Нека предположим, че теоремата е вярна за \( P^{n-1} \). Вероятността да преминем от състояние \( i \) към състояние \( j \) за \( n \) стъпки тогава е сумата на вероятностите по всички траектории. От формулата за пълната вероятност имаме
  \begin{align*}
    p^{(n)}_{ij}
    &=
    \Prob(\xi_n = j \mid \xi_0 = i)
    = \\ &=
    \sum_{k=0}^\infty \Prob(\xi_n = j \mid \xi_{n-1} = k, \xi_0 = i) \Prob(\xi_{n-1} = k \mid \xi_0 = i)
    = \\ &=
    \sum_{k=0}^\infty \Prob(\xi_n = j \mid \xi_{n-1} = k) \Prob(\xi_{n-1} = k \mid \xi_0 = i)
    = \\ &=
    \sum_{k=0}^\infty p_{kj} p^{(n-1)}_{ik}
    = \\ &=
    \sum_{k=0}^\infty p^{(n-1)}_{ik} p_{kj}.
  \end{align*}

  Но това по определение са именно елементите на матрицата \( P^{n-1} P \). Следователно матрицата \( P^n \) има елементи \( p^{(n)}_{ij} \).
\end{proof}

\begin{remark}
  Лемата важи и за \( n = 0 \), в който случай получаваме единичната матрица. Вероятностната интерпретация на този факт е, че всяко състояние с вероятност \( 1 \) достига себе си за \( 0 \) стъпки.
\end{remark}

\begin{theorem}[Уравнения на Чепмен-Колмогоров]\label{thm:chapman_kolmogorov}
  За произволни цели \( m, n \geq 0 \) е изпълнено
  \begin{equation*}
    p^{(n+m)}_{ij} = \sum_{k=0}^\infty p^{(n)}_{ik} p^{(m)}_{kj}
  \end{equation*}
  за всеки две състояния \( i, j \geq 0 \).
\end{theorem}
\begin{proof}
  От свойствата на матричното умножение имаме \( P^{n+m} = P^n P^m \). \Cref{thm:transition_matrix_power} ни казва, че това е просто матричен запис на уравненията от условието.
\end{proof}

\begin{corollary}
  Безусловната вероятност \( \Prob(\xi_n = i) \) за това да се намираме в състояние \( i \) в момента \( n \) е \( i \)-тата координата на вектора \( B P^n \).
\end{corollary}
\begin{proof}
  От формулата за пълната вероятност имаме
  \begin{equation*}
    \Prob(\xi_n = i)
    =
    \sum_{k=1}^\infty \Prob(\xi_n = i \mid \xi_0 = k) \Prob(\xi_0 = k)
    =
    \sum_{k=1}^\infty p^{(n)}_{ki} s_k
    =
    \sum_{k=1}^\infty b_k p^{(n)}_{ki},
  \end{equation*}
  което по определение е именно \( i \)-тата координата на вектор-реда \( B P^n \).
\end{proof}

\subsection{Класификация на състоянията}

За състояния \( i \) и \( j \) въвеждаме означенията
\begin{align*}
  f_{ij}^{(n)} &\coloneqq \Prob(\xi_n = j, \xi_{n-1} \neq j \ldots, \xi_1 \neq j \mid \xi_0 = i), \\
  f_{ij} &\coloneqq \sum_{n=0}^\infty f_{ij}^{(n)}.
\end{align*}

В частност, \( f_{ij}^{(0)} = p_{ij}^{(0)} = \delta_{ij} \). Стойността \( f^{(n)}_{ij} \) е вероятността започвайки от състояние \( i \) да достигнем за пръв път състояние \( j \) за точно \( n \) стъпки, а \( f_{ij} \) е вероятността излизайки от състояние \( i \) някога да стигнем до състояние \( j \).  В \cref{thm:state_is_transient_iff_p_is_divergent} ще видим, че \( f_{ii} \in [0, 1] \).

\begin{definition}
  \hfill
  \begin{itemize}
    \item Състоянието \( j \) се нарича \textbf{достижимо} от състоянието \( i \), ако \( p^{(n)}_{ij} > 0 \) за някое \( n > 0 \).
    \item Състоянията \( i \) и \( j \) се наричат \textbf{съобщаващи се}, ако те са достижими едно от друго. Пишем \( i \leftrightarrow j \).
    \item Една марковска верига се нарича \textbf{неразложима}, ако всеки две нейни състояния са съобщаващи се.
    \item Състоянието \( i \) се нарича \textbf{поглъщащо}, ако никое друго състояние не може да бъде достигнато от него.
    \item Състоянието \( i \) се нарича \textbf{възвратно}, ако \( f_{ii} = 1 \).
    \item Състоянието \( i \) се нарича \textbf{преходно}, ако \( f_{ii} < 1 \).
    \item Ако \( f_{ii} > 0 \), числото \( d_i \coloneqq \gcd (\set{ n > 0 \mid p_{ii}^{(n)} > 0 }) \) се нарича \textbf{период} на състоянието \( i \). Състояние с период \( d > 1 \) се нарича \textbf{периодично} с период \( d \), а състояние с период \( 1 \) се нарича \textbf{апериодично}.
    \item Ако всички състояния на една неразложима марковска верига имат период \( d \), самата верига се нарича \textbf{периодична} с период \( d \).
  \end{itemize}
\end{definition}

\begin{proposition}
  Релацията \( \leftrightarrow \) е релация на еквивалентност в множеството от състояния.
\end{proposition}
\begin{proof}
  \hfill
  \begin{enumerate}
    \item \( i \leftrightarrow i \), тъй като всяко състояние достига себе си за \( 0 \) стъпки.
    \item Ако \( i \leftrightarrow j \), то по определение \( j \leftrightarrow i \).
    \item Ако \( i \leftrightarrow j \) и \( j \leftrightarrow k \), тогава от уравненията на Чепмен-Колмогоров следва, че \( i \leftrightarrow k \).
  \end{enumerate}
\end{proof}

Това ни позволява да разбием множеството състояния на непресичащи се класове.

\begin{corollary}
  Една марковска верига е неразложима точно тогава, когато има единствен клас съобщаващи се състояния.
\end{corollary}

\begin{proposition}
  Периодичността е съгласувана с класовете съобщаващи се състояния, т.е. две периодични или апериодични съобщаващи се състояние имат един и същи период.
\end{proposition}
\begin{proof}
  Нека \( i \leftrightarrow j \), т.е. за някои числа \( n, m > 0 \) са изпълнени \( p_{ij}^{(n)} > 0 \) и \( p_{ji}^{(m)} > 0 \).

  Нека първо \( i \) е апериодично. Тогава за произволно \( k \), за което \( \pi_{ii}^{(k)} > 0 \), е изпълнено \( p_{ii}^{(n+k+m)} > 0 \). Но ако \( \gcd (\set{ k \mid k > 0, p_{ii}^{(k)} > 0 }) = 1 \), то \( \gcd (\set{ n+k+m \mid k > 0, p_{ii}^{(n)} > 0 }) \) = 1. Следователно състоянието \( j \) също е апериодично.

  Нека сега \( i \) не е апериодично. Тогава \( p_{ii}^{(n+m)} > 0 \) и следователно \( d_i \mid (n+m) \). Аналогично получаваме \( p_{jj}^{(m+n)} > 0 \), следователно \( d_j \mid (m+n) \).

  Това е вярно за всички \( n, m > 0 \), за които \( p_{ij}^{(n)} > 0 \) и \( p_{ji}^{(m)} > 0 \). Да забележим, че тъй като и двете състояния не са апериодични, \( p_{ii} = p_{jj} = 0 \), т.е. \( i \) може да достигне себе си само преминавайки през \( j \). Следователно числата \( d_i \) и \( d_j \) имат едни и същи кратни и значи \( d_i = d_j \).
\end{proof}

\begin{corollary}
  Една неразложима марковска верига е периодична с период \( d \) ако поне едно, а оттам и всички състояния имат период \( d \).
\end{corollary}

\begin{theorem}\label{thm:state_is_transient_iff_p_is_divergent}
  Състоянието \( i \) е преходно, точно когато редът \( \sum_{n=1}^\infty p^{(n)}_{ii} \) е сходящ. В противен случай, състоянието е възвратно.
\end{theorem}
\begin{proof}
  Разглеждаме пораждащите функции
  \begin{align*}
    f(z) \coloneqq \sum_{n=1}^\infty f_{ii}^{(n)} z^n,
    &&
    p(z) \coloneqq \sum_{n=1}^\infty p_{ii}^{(n)} z^n.
  \end{align*}
  за редиците
  \begin{align*}
    \set{ f_{ii}^{(k)} }_{k=1}^\infty,
    &&
    \set{ p_{ii}^{(k)} }_{k=1}^\infty.
  \end{align*}

  По формулата за пълната вероятност за \( n > 0 \) имаме
  \small{
  \begin{align*}
    p_{ii}^{(n)}
    &=
    \Prob(\xi_n = i \mid \xi_0 = i)
    = \\ &=
    \sum_{k=1}^n \Prob(\xi_n = i \mid \xi_k = i, \xi_{k-1} \neq i, \ldots, \xi_1 \neq i, \xi_0 = i) \Prob(\xi_k = i, \xi_{k-1} \neq i, \ldots, \xi_1 \neq i \mid \xi_0 = i)
    = \\ &=
    \sum_{k=1}^n \Prob(\xi_n = i \mid \xi_k = i) \Prob(\xi_k = i, \xi_{k-1} \neq i, \ldots, \xi_1 \neq i \mid \xi_0 = i)
    = \\ &=
    \sum_{k=1}^n p_{ii}^{(n-k)} f_{ii}^{(k)}.
  \end{align*}
  }

  Тогава за \( z \in (-1, 1) \) имаме
  \begin{align*}
    p(z)
    &=
    \sum_{n=1}^\infty p_{ii}^{(n)} z^n
    = \\ &=
    \sum_{n=1}^\infty p_{ii}^{(n)} z^n
    = \\ &=
    \sum_{n=1}^\infty z^n \sum_{k=1}^n p_{ii}^{(n-k)} f_{ii}^{(k)}
    = \\ &=
    \sum_{n=1}^\infty \sum_{k=1}^n (p_{ii}^{(n-k)} z^{n-k}) (f_{ii}^{(k)} z^k)
    = \\ &=
    \sum_{n=1}^\infty f_{ii}^{(n)} z^n \parens*{ 1 + \sum_{k=1}^\infty p_{ii}^{(n-k)} z^{n-k} }
    = \\ &=
    \sum_{n=1}^\infty f_{ii}^{(n)} z^n (1 + p(z))
    = \\ &=
    f(z) (1 + p(z)).
  \end{align*}

  Получихме
  \begin{equation*}
    f(z) = \frac {p(z)} {1 + p(z)}.
  \end{equation*}

  Редът
  \begin{equation*}
    \sum_{n=1}^\infty p^{(n)}_{ii} = \lim_{z \to 1} p(z)
  \end{equation*}
  е разходящ точно тогава, когато \( \lim_{z \to 1} f(z) = 1 \).

  От друга страна, горният ред е сходящ, точно когато
  \begin{equation*}
    \sum_{n=1}^\infty f_i^{(n)} = \frac {p(1)} {1 + p(1)} < 1,
  \end{equation*}
  т.е. когато състоянието \( i \) е преходно.
\end{proof}

\subsection{Гранични вероятности и ергодична теорема}

Интересува ни граничното поведение на вероятностите за преходите.

\begin{definition}
  Случайните величини
  \begin{align*}
    T_j^{(n)}
    \coloneqq
    \begin{cases}
      0, &n = 0 \\
      \min \set{ k > T_j^{(n-1)} \mid \xi_k = j }, &n > 0
    \end{cases}
  \end{align*}
  са \textbf{моментите на \( n \)-тото попадане в състояние \( j \)}.

  Случайните величини \( M_j^{(n)} \)
  \begin{align*}
    \mu_j^{(n)}
    \coloneqq
    \begin{cases}
      1, \xi_n = j \\
      0, \xi_n \neq j
    \end{cases},
    &&
    M_j^{(n)}
    \coloneqq
    \sum_{k=1}^n \mu_j^{(k)},
  \end{align*}
  са \textbf{броят попадания в състоянието \( j \) до момента \( n \)}.

  Очакваният брой стъпки, които са необходими, за да се върнем в състояние \( j \), тръгвайки от него, означаваме с
  \begin{equation*}
    \tau_i
    \coloneqq
    \Expect(T_i^{(1)} \mid \xi_0 = i)
    =
    \sum_{n=1}^\infty n \Prob(\xi_n = i, \xi_{n-1} \neq i, \ldots, \xi_1 \neq i \mid \xi_0 = i)
    =
    \sum_{n=1}^\infty n f^{(n)}_{ii}.
  \end{equation*}
\end{definition}

\begin{definition}
  Възвратното състояние \( i \) се нарича \textbf{положително възвратно}, ако очакването \( \tau_i \) е крайно. В противен случай, състоянието се нарича \textbf{нулево възвратно}.

  Положително възвратно апериодично състояние се нарича \textbf{ергодично}.

  Ако в една неразложима марковска верига поне едно състояние, а оттам и всички състояния са положително възвратни, то самата верига се нарича \textbf{положително възвратна}. Ако поне едно състояние е ергодично, самата верига се нарича \textbf{ергодична}.
\end{definition}

\begin{definition}
  Нека е дадена марковска верига с матрица на преходите \( P \). Стохастичният вектор \( \pi = (\pi_1, \pi_2, \ldots) \) наричаме \textbf{стационарно разпределение} на веригата, ако \( \pi \) удовлетворява матричното уравнение
  \begin{equation*}
    \pi = \pi P.
  \end{equation*}

  Ако границата \( \lim_{n \to \infty} P^n \) съществува и редовете на получената матрица са равни, то произволен ред на матрицата наричаме \textbf{гранично разпределение} на веригата.
\end{definition}

\begin{theorem}[Ергодична теорема]
  Нека е дадена неразложима положително възвратна марковска верига. Тогава са в сила равенствата
  \begin{equation*}
    \frac 1 {\tau_j}
    =
    \lim_{n \to \infty} \frac {M^{(n)}_j} n
    =
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n p_{ij}^{(k)}\quad\forall i \geq 0,
  \end{equation*}
  където сходимостта е по вероятност.

  Освен това векторът \( \pi = (\pi_1, \pi_2, \ldots) \) с координати \( \pi_j = \frac 1 {\tau_j} \) е стационарно разпределение на веригата.
\end{theorem}
\begin{proof}
  Тъй като веригата е положително възвратна, очакването \( \tau_j \geq 1 \) е крайно и следователно стойностите \( \pi_j = \frac 1 {\tau_j} \in (0, 1] \) са добре дефинирани.

  Първо ще докажем равенството
  \begin{equation*}
    \frac 1 {\tau_j}
    =
    \lim_{n \to \infty} \frac {M^{(n)}_j} n.
  \end{equation*}

  Фиксираме произволни състояние \( j \) и момент \( n > 0 \). Да забележим, че за произволно \( k \geq 0 \) разликите \( T_j^{(k+1)} - T_j^{(k)} \) са независими и еднакво разпределени с (условно) очакване
  \begin{equation*}
   \Expect(T_j^{(k)} - T_j^{(k-1)} \mid \xi_0 = i) = \tau_j.
  \end{equation*}

  От усиления закон за големите числа имаме
  \begin{equation*}
    \frac {T_j^{(n)}} n = \frac 1 n \sum_{k=0}^{n-1} (T_j^{(k+1)} - T_j^{(k)}) \xrightarrow[n \to \infty]{} \tau_j
  \end{equation*}
  почти сигурно.

  Случайната величина \( T_j^{(M_j^{(n)})} \) е моментът на последното попадане в състояние \( j \) преди момента \( n \). По тази причина е изпълнено
  \begin{equation*}
    T_j^{(M_j^{(n)})} \leq n \leq T_j^{(M_j^{(n)} + 1)}.
  \end{equation*}

  Делим на \( M_j^{(n)} \) и получаваме
  \begin{equation*}
    \frac {T_j^{(M_j^{(n)})}} {M_j^{(n)}} \leq \frac n {M_j^{(n)}} \leq \frac {T_j^{(M_j^{(n)} + 1)}} {M_j^{(n)} + 1} \frac {M_j^{(n)} + 1} {M_j^{(n)}}
  \end{equation*}

  От лемата за милиционерите получаваме, че
  \begin{equation*}
    \lim_{n \to \infty} \frac n {M^{(n)}_j}
    =
    \tau_j
  \end{equation*}
  по вероятност. Еквивалентно,
  \begin{equation}\label{thm:ergodic_theorem/squeeze_lemma_application}
    \lim_{n \to \infty} \frac {M^{(n)}_j} n
    =
    \pi_j.
  \end{equation}

  Сега ще докажем равенството
  \begin{equation*}
    \lim_{n \to \infty} \frac {M^{(n)}_j} n
    =
    \lim_{n \to \infty} p_{ij}^{(n)} \quad\forall i \geq 0.
  \end{equation*}

  Фиксираме изходно състояние \( i \). Понеже сходимостта в \eqref{thm:ergodic_theorem/squeeze_lemma_application} е по вероятност, важи и сходимост по разпределение, следователно за всяка ограничена непрекъсната функция \( g \) имаме
  \begin{equation}\label{thm:ergodic_theorem/expectation_of_limit}
    \lim_{n \to \infty} \Expect g\parens*{ \frac {M^{(n)}_j} n \Bigl\vert \xi_0 = i } = \Expect g\parens*{ \lim_{n \to \infty} \frac {M^{(n)}_j} n \Bigl\vert \xi_0 = i } = \Expect g(\pi_j \mid \xi_0 = i).
  \end{equation}

  Последното следва от, например, \cite[следствие 2 на стр. 119]{Боровков1999Вероятности}.

  Да забележим, че \( \frac {M^{(n)}_j} n \leq 1 \) с вероятност \( 1 \). Понеже \( g(x) \coloneqq \max(x, 1) \) е ограничена непрекъсната функция, \eqref{thm:ergodic_theorem/expectation_of_limit} придобива вида
  \begin{equation*}
    \lim_{n \to \infty} \Expect \parens*{ \frac {M^{(n)}_j} n \Bigl\vert \xi_0 = i } = \Expect (\pi_j \mid \xi_0 = i) = \pi_j.
  \end{equation*}

  От друга страна,
  \begin{equation*}
    \pi_j
    =
    \lim_{n \to \infty} \frac {\Expect(M^{(n)}_j \mid \xi_0 = i)} n
    =
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n \Expect(\mu^{(k)}_j \mid \xi_0 = i)
    =
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n 1 \cdot p_{ij}^{(k)}.
  \end{equation*}

  В частност, получената стойност не зависи от началното състояние \( i \).

  Векторът \( \pi \) е стохастичен, тъй като
  \begin{equation*}
    \sum_{j=0}^\infty \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n p_{ij}^{(k)}
    =
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n \sum_{j=0}^\infty p_{ij}^{(k)}
    =
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n 1
    =
    1.
  \end{equation*}

  Остана само да докажем, че векторът \( \pi \) е стационарен. Уравненията на Чепмен-Колмогоров ни дават
  \begin{align*}
    \sum_{i=0}^\infty \pi_i p_{ij}
    &=
    \sum_{i=0}^\infty \parens*{ \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n p_{mi}^{(k)} } p_{ij}
    = \\ &=
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n \sum_{i=0}^\infty p_{mi}^{(k)} p_{ij}
    = \\ &=
    \lim_{n \to \infty} \frac 1 n \sum_{k=1}^n p_{mj}^{(k+1)}
    = \\ &=
    \lim_{n \to \infty} \frac {n+1} n \frac 1 {n+1} \sum_{k=0}^n p_{mj}^{(k)}
    =
    \pi_j.
  \end{align*}
\end{proof}

Ако марковската верига е и апериодична, редицата \( {\set{ p_{ij}^{(n)} }}_n \) схожда към \( \pi_j \). Доказателството на този факт е трудоемко и затова само ще го формулираме.

То се базира на факта, че ако редицата \( {\set{ p_{ij}^{(n)} }}_n \) е сходяща, тя схожда към същата стойност като съответната редица на Чезаро \( {\set{ \frac 1 n \sum_{k=1}^n p_{ij}^{(k)} }}_n \), за която знаем, че клони към \( \pi_j \). Ако веригата е периодична с период \( d \), \( p_{jj}^{(nd)} = 0\quad\forall n > 0 \), т.е. редицата има безброй нулеви членове и не може да схожда към положително число.

\begin{corollary}
  Ако веригата е ергодична, тогава
  \begin{equation*}
    \pi_j = \lim_{n \to \infty} p_{ij}^{(n)}.
  \end{equation*}
\end{corollary}

\subsection{Приложения}

\subsubsection{Случайно блуждаене}

Един прост пример за марковска верига с безброй състояния е \textbf{случайното блуждаене с вероятност \( p \in [0, 1] \)}, наричано още \textbf{случайна разходка}. В този случай множеството от състояния е \( \BbbZ \), началното състояние е \( 0 \) с вероятност \( 1 \) и вероятностите за преход са
\begin{align*}
  \Prob(\xi_n = j \mid \xi_{n-1} = i)
  =
  \begin{cases}
    p,     &j = i + 1 \\
    1 - p, &j = i - 1 \\
    0,       &\text{иначе}
  \end{cases}.
\end{align*}

Очевидно едно случайно блуждаене е неразложима, възвратна и периодична марковска верига с период \( 2 \).

Нека \( \eta_1, \eta_2, \ldots \) са независими случайни величини с еднакво разпределение
\begin{equation*}
  \Prob(\eta_n = 1) = 1 - \Prob(\eta_k = -1) = p.
\end{equation*}

Сумите им \( \xi_n \coloneqq \sum_{k=1}^n \eta_k \) тогава образуват случайно блуждаене.

Това ни позволява да пресметнем лесно очакването на процеса:
\begin{align*}
  \Expect(\xi_n)
  &=
  \Expect \parens*{\sum_{k=1}^n \eta_k }
  = \\ &=
  \sum_{k=1}^n \Expect \parens*{\eta_k }
  = \\ &=
  \sum_{k=1}^n (1 \cdot p + (-1) \cdot (1-p))
  = \\ &=
  \sum_{k=1}^n (2p - 1)
  = \\ &=
  n (2p - 1).
\end{align*}

Ако \( p = \frac 1 2 \), очакваме процеса да флуктира около началото. В противен случай, границата \( \lim_{n \to \infty} \Expect(\xi_n) \) не съществува.

Ако възможните състояния са крайно множество \( \set{ m, m+1, \ldots, M-1, M } \) от цели числа, състоянията с \( m \) и \( M \) се наричат \textbf{бариери}. Разглеждаме два случая:
\begin{itemize}
  \item Бариерите наричаме \textbf{поглъщащи}, ако
  \begin{align*}
    \Prob(\xi_n = j \mid \xi_{n-1} = m)
    &=
    \begin{cases}
      1,     &j = m \\
      0,     &\text{иначе}
    \end{cases},
    \\
    \Prob(\xi_n = j \mid \xi_{n-1} = M)
    &=
    \begin{cases}
      1,     &j = M \\
      0,     &\text{иначе}
    \end{cases}.
  \end{align*}

  \item Бариерите наричаме \textbf{отразяващи}, ако
  \begin{align*}
    \Prob(\xi_n = j \mid \xi_{n-1} = m)
    &=
    \begin{cases}
      1,     &j = {m+1} \\
      0,     &\text{иначе}
    \end{cases},
    \\
    \Prob(\xi_n = j \mid \xi_{n-1} = M)
    &=
    \begin{cases}
      1,     &j = {M-1} \\
      0,     &\text{иначе}
    \end{cases}.
  \end{align*}
\end{itemize}

Разбира се, възможно е едната бариера да бъда поглъщата, а другата - отразяваща.

Случайните разходки са изключително приложими като прост модел, описващ
\begin{enumerate}
  \item дали цената на една акция ще се покачи или ще падне за даден период от време.
  \item едномерни проекции на хаотични движения на частици.
  \item дифузията на изкуствено въведена популация животни.
\end{enumerate}

\subsubsection{Генериране на текст}

Марковските вериги с краен брой състояния позволяват лесно да се генерира текст. Нека \( W \) е краен речник, т.е. множество от думи. Обикновено \( W \) се събира от истински текст.

Дефинираме марковска верига над \( W \) като задаваме матрица \( P \) от преходни вероятности, базирани на това колко често се срещат думите от \( W \) последователно. По-точно, дефинираме редица \( w_0, w_1, \ldots \) от думи, всяка от които е случайна величина със стойности във \( W \) и условни вероятности \( \Prob(w_n = j \mid w_{n-1} = i) \), базирани на матрицата \( P \). Траекториите на този процес са безкрайни изречения, базирани на оригиналния текст.

Ако разполагаме с метод за симулиране на дискретни случайни величини с краен брой стойности, можем да генерираме текст с произволна дължина.

Като прост пример можем да разгледаме изречението \enquote{Ту вали, ту не вали}. Преходните вероятности за него са
\begin{center}
  \begin{tabular}{l l l l}
                    & \textbf{ту} & \textbf{вали} & \textbf{не} \\
      \textbf{ту}   & 0           & 0.5           & 0.5         \\
      \textbf{вали} & 1           & 0             & 0           \\
      \textbf{не}   & 0           & 1             & 0           \\
  \end{tabular}
\end{center}

Като примерен резултат от генериране на текст с марковска верига, обучена с горното изречение, можем да получим изречението \enquote{ту вали, ту не вали, ту вали, ту не вали, ту не вали} (с вмъкнати запетайки за четимост).

\printbibliography

\end{document}
