Пусть имеется некоторая физическая система, которая по своей природе ведет себя случайным образом: в каждый момент времени находится в одном из $n$ возможных и несовместимых состояний $S_1,\dots,S_n$, которые сменяют друг друга через конечные промежутки времени по следующему закону: в некоторый начальный момент $t_0$ вероятности этих состояний равны соответственно $p_{01},\dots,p_{0n}$, а в каждый последующий момент $$ t_1< t_2< \dots $$ вероятность системе, находившейся в этот момент в состоянии $S_j$, перейти в состояние $S_k$ в следующий момент равна числу $p_{jk},\ 0 \le p_{jk} \le 1$. Это число $p_{jk}$ не зависит от состояний системы во все предшествующие моменты времени. Известно также, что в одно из состояний система перейдет наверняка: $$ p_{j1}+\dots+p_{jn}=1 \quad \mbox{при} \ j\in\{1,\dots,n\} \, . $$ Составим из этих вероятностей матрицу.

Матрица из схемы $$ \begin{array}{c} \\ S_1 \\ S_2 \\ \vdots \\ S_n \end{array} \begin{array}{c} \begin{array}{cccc} S_1 & S_2 & \dots & S_n \end{array} \\ \left( \begin{array}{llll} p_{11} & p_{12} & \dots & p_{1n} \\ p_{21} & p_{22} & \dots & p_{2n} \\ \dots &&& \dots \\ p_{n1} & p_{n2} & \dots & p_{nn} \end{array} \right) \end{array} $$ называется матрицей переходных вероятностей, будем обозначать ее $\mathfrak P$. Величины $p_{01},\dots,p_{0n}$ назовем начальными вероятностями. Определенная этими правилами смена состояний системы называется простой однородной цепью Маркова $\mathfrak C_n$ (с конечным числом состояний).

Биографические заметки об А.А.Маркове ☞ ЗДЕСЬ

Пример 1. В так называемом братско-сестринском скрещивании скрещиваются две особи, и среди их прямых потомков случайны образом выбираются две особи разного пола. Они вновь скрещиваются, и процесс этот продолжается бесконечно. Имея три генотипа ${\sf AA}, {\sf Aa}, {\sf aa} $ для каждого родителя, мы должны различать шесть комбинаций родителей, которые пометим следующим образом:

$$S_1= {\sf AA}\times {\sf AA},\ S_2= {\sf AA}\times {\sf Aa},\ S_3= {\sf Aa}\times {\sf Aa},\ S_4= {\sf Aa}\times {\sf aa},\ S_5= {\sf aa}\times {\sf aa},\ S_6= {\sf AA}\times {\sf aa} \, . $$ Генотип потомка зависит от случайного процесса. При любых обстоятельствах каждый родительский ген может передаваться с вероятностью $1/2$, и последовательные испытания независимы. Иначе говоря, генотипы потомков можно представить как результат независимых испытаний, каждое из которых эквивалентно бросанию пары монет. Например, при скрещивании особей ${\sf Aa}\times {\sf Aa}$ могут появиться генотипы ${\sf AA}, {\sf Aa}$ и $ {\sf aa} $ с вероятностями равными соответственно $1/4,\, 1/2,\, 1/4$. Скрещивание ${\sf AA}\times {\sf aa}$ может привести к появлению лишь особей $ {\sf Aa} $ и т.п. Матрица переходных вероятностей будет иметь вид $$ \mathfrak P=\left( \begin{array}{cccccc} 1& 0 & 0 & 0 & 0 & 0 \\ 1/4 & 1/2 & 1/4 & 0 & 0 & 0 \\ 1/16 & 1/4 & 1/4 & 1/4 & 1/16 & 1/8 \\ 0 & 0 & 1/4 & 1/2 & 1/4 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{array} \right) \, . $$

Пример 2. Предположим, что студенческая жизнь в каждый момент времени состоит из трех возможных состояний: лекция, сон, буфет. Пусть известны привычки студента, т.е. задана матрица переходных вероятностей $\mathfrak P$:

$$ \begin{array}{c} \\ \mbox{лекция} \\ \mbox{сон} \\ \mbox{буфет} \end{array} \begin{array}{c} \begin{array}{c} \mbox{лекция} \mbox{ сон } \mbox{буфет} \end{array} \\ \left( \begin{array}{lcr} \frac{1}{2} &\frac{1}{4} & \frac{1}{4} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{6} & \frac{1}{2} \end{array} \right) \end{array} \enspace . $$ Требуется определить ``судьбу'' студента, т.е. вероятность нахождения в одном из состояний по истечении достаточно большого промежутка времени.

Переходные вероятности $p_{jk}$ можно назвать вероятностями перехода системы из $S_j$ в $S_k$ за один шаг. Найдем теперь вероятности перехода $p_{jk}^{(2)}$ системы из $S_j$ в $S_k$ за два шага.

На основании теоремы об умножении вероятностей вероятности каждого перехода: $$ \begin{array}{c|c} \mbox{переход} & \mbox{вероятность} \\ \hline S_j \to S_1 \rightarrow S_k & p_{j1}p_{1k} \\ S_j \rightarrow S_2 \rightarrow S_k & p_{j2}p_{2k} \\ \dots & \dots \\ S_j \rightarrow S_n \rightarrow S_k & p_{jn}p_{nk} \end{array} $$ В соответствии с теоремой о вероятности суммы событий, чтобы получить вероятность перехода из $S_j$ в $S_k$ за два шага надо просуммировать полученные выражения: $$ p_{jk}^{(2)}= \sum_{\ell=1}^n p_{j\ell}p_{\ell k} \, . $$ Вывод: матрица $\mathfrak P^{(2)}$ переходных вероятностей за два шага состоит из элементов, которые формируются по правилу умножения матриц $\mathfrak P\cdot \mathfrak P$: $$\mathfrak P^{(2)}=\mathfrak P^2 \ .$$ Этот результат обобщается на случай переходных вероятностей за $K$ шагов: $$ \mathfrak P^{(K)}=\mathfrak P^K \ ,\quad \mbox{ при } \ K\in \mathbb N \ . $$

Абсолютной вероятностью $p_j^{(K)}$ состояния $S_j$ системы в момент $t=t_{K}$ называется вероятность этого состояния независимо от того, в каких состояниях находилась система в моменты времени $t_{K-1},\dots,t_1$.

$$ p_j^{(K)}=p_1^{(K-1)}p_{1j}+\dots+ p_n^{(K-1)}p_{nj} =\left[p_1^{(K-1)},\dots, p_n^{(K-1)} \right] \left(\begin{array}{c} p_{1j} \\ \vdots \\ p_{nj} \end{array} \right) \enspace . $$ Собираем абсолютные вероятности для всех состояний $S_1,\dots,S_n$ в вектор: $$ \left[p_1^{(K)},\dots, p_n^{(K)} \right] = \left[p_1^{(K-1)},\dots, p_n^{(K-1)} \right] \mathfrak P \, . $$ Рекурсивно по $K$ применяем последнюю формулу: $$ \left[p_1^{(K)},\dots, p_n^{(K)} \right] = \left[p_1^{(K-2)},\dots, p_n^{(K-2)} \right] \mathfrak P^2=\dots= [p_{01},\dots,p_{0n}] \mathfrak P^K \ . $$

Задача. Найти $\displaystyle \lim_{K\to +\infty} p_j^{(K)}$ для $ j\in \{1,\dots,n\} $.

Если этот предел существует, то его величина $p_j^{\infty}$ называется финальной (предельной) абсолютной вероятностью.

Из последнего равенства следует, что существование $p_j^{\infty}$ зависит от существования $$\lim_{K\to +\infty} \mathfrak P^K\, . $$ Мы пришли к задаче о выяснении асимптотики степенной функции матрицы. Исследование начинаем с собственных чисел матрицы $\mathfrak P$.

Матрица $A$ называется неотрицательной (положительной) если все ее элементы неотрицательны (положительны): $ A \ge \mathbb O$ ($A> \mathbb O$). Квадратная неотрицательная матрица $A$ называется стохастической¹⁾ если равна $ 1 $ сумма элементов каждой ее строки²⁾.

Матрица $\mathfrak P$ переходных вероятностей — стохастическая (и в дальнейшем всякую стохастическую матрицу будем обозначать $\mathfrak P$).

Теорема 1. Если $\mathfrak P$ — стохастическая, то и $\mathfrak P^K$ — стохастическая.

Доказательство. Для элементов $j$-й строки матрицы $\mathfrak P^2$ выше выведена формула $$ p_{jk}^{(2)}= \sum_{\ell=1}^n p_{j\ell}p_{\ell k} \, . $$ Их неотрицательность очевидна. Просуммируем: $$ \sum_{i=1}^n p_{j i}^{(2)}=\sum_{i=1}^n \sum_{\ell =1}^n p_{j\ell}p_{\ell i} =\sum_{\ell=1}^n \sum_{i=1}^n p_{j\ell}p_{\ell i}= \sum_{\ell=1}^n \bigg(p_{j\ell} \underbrace{\sum_{i=1}^n p_{\ell i}}_{=1} \bigg) = \sum_{\ell=1}^n p_{j\ell}=1 \, . $$ Следовательно, $\mathfrak P^2$ — стохастическая. Доказательство для общего случая проводится индукцией по $K$. ♦

Теорема 2. Все собственные числа стохастической матрицы не превосходят по модулю $1$, и по крайней мере одно из них равно $1$.

Доказательство. Действительно, согласно теореме Гершгорина, собственное число $\lambda\in \mathbb C$ стохастической матрицы $\mathfrak P$ должно удовлетворять неравенству $$|\lambda - p_{jj}|\le \sum_{k\ne j} |p_{jk}|=1-p_{jj} $$ хотя бы при одном $j$. Воспользовавшись следствием к неравенству треугольника имеем: $$|\lambda| - |p_{jj}|\le |\lambda - p_{jj}| \le 1-p_{jj} \ \Rightarrow \ |\lambda| \le 1 \, . $$ Далее, $$ \mathfrak P \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) = \left( \begin{array}{c} p_{11} +\dots+p_{1n} \\ p_{21} +\dots+p_{2n} \\ \dots \\ p_{n1} +\dots+ p_{nn} \end{array} \right) = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right), $$ т.е. $\lambda=1$ — собственное число, соответствующее собственному вектору $X=[1,1,\dots,1]^{^{\top}}$. ♦

Локализация оставшейся части спектра стохастической матрицы оказывается задачей сложной. На рисунке показаны области допустимых значений для собственных чисел стохастических матриц порядков $ 3,4,5 $ (области Карпелевича). Выход граничных кривых областей на окружность $ |z|=1 $ — в корнях из единицы.

Теорема 3. Если собственное число $1$ — простое для матрицы $\mathfrak P$, а модули всех остальных собственных чисел меньше $1$, то существует конечная матрица

$$ \mathfrak P^{\infty}:= \lim_{K\to +\infty} \mathfrak P^K \, .$$ Все строки матрицы $ \mathfrak P^{\infty} $ одинаковы.

Доказательство. Теория построения жордановой нормальной формы в нашем конкретном случае дает следующую информацию о ЖНФ $\mathfrak P_{_{\mathfrak J}} $ и матрице перехода к каноническому базису: $$ \mathfrak P_{_{\mathfrak J}}=\left( \begin{array}{l|lll} 1 &0 & \dots & 0\\ \hline 0& & \mbox{клетки} & \\ \vdots& & \mbox{для} \ \lambda_j & \\ 0& & |\lambda_j|<1 & \end{array} \right), \quad C= \left( \begin{array}{l|lll} 1 & & \mbox{корневые} & \\ 1& & \mbox{векторы} & \\ \vdots& &\mbox{для} \ \lambda_j & \\ 1& & |\lambda_j|<1 & \end{array} \right) $$ На основании теоремы 7: $$\mathfrak P_{_{\mathfrak J}}^{\infty}:= \lim_{K\to +\infty} \mathfrak P_{_{\mathfrak J}}^K= \left( \begin{array}{llll} 1 &0 & \dots & 0\\ 0& & & \\ \vdots& & \mathbb O& \\ 0& & & \end{array} \right). $$ Но тогда существует $\displaystyle{ \lim_{K\to +\infty} \mathfrak P^K}$ и он равен $$C \mathfrak P_{_{\mathfrak J}}^{\infty}C^{-1}= \left( \begin{array}{llll} \tau_{11} &\tau_{12} & \dots & \tau_{1n}\\ \tau_{11} &\tau_{12} & \dots & \tau_{1n}\\ \dots & & & \dots\\ \tau_{11} &\tau_{12} & \dots & \tau_{1n} \end{array} \right), $$ где $\left[\tau_{11},\tau_{12}, \dots, \tau_{1n}\right]$ — первая строка матрицы $C^{-1}$. Действительно, как и утверждается в формулировке теоремы, все строки матрицы $\mathfrak P^{\infty}$ одинаковы! Кроме того, на основании теоремы 1, свойство стохастичности для матрицы $\mathfrak P^{\infty}$ должно сохраняться: $\tau_{11}+\tau_{12}+ \cdots+ \tau_{1n}=1$. ♦

Стохастическая матрица $\mathfrak P$, удовлетворяющая условию теоремы 3, называется регулярной (и такой же — цепь $\mathfrak C_n$).

Для регулярной цепи $\mathfrak C_n$ финальные абсолютные вероятности находятся по формулам

$$ p_j^{\infty}=\tau_{1j} \quad \mbox{для} \ j\in \{1,\dots,n\} \, , $$ и они не зависят от начальных $p_{01},\dots,p_{0n}$.

Иначе говоря: для момента времени $t_K$ достаточно удаленного от любого исходного момента поведение системы становится почти независимым от исходного состояния.

Пример. Для стохастической матрицы

$$\mathfrak P= \left( \begin{array}{llll} 0.54580 &0.36663 & 0.03519 & 0.05238\\ 0.04406 &0.00738 & 0.13600 & 0.81256\\ 0.42015 &0.27010 & 0.12121 & 0.18854\\ 0.85136 &0.00749 & 0.00123 & 0.13992 \end{array} \right) $$ имеем: $$ \mathfrak P^{32}= \left( \begin{array}{llll} 0.50875694_{\displaystyle 79} &0.203905925_{\displaystyle 3} & 0.0522576617_{\displaystyle 4} &0.23507946_{\displaystyle 60}\\ 0.50875694_{\displaystyle 76} &0.203905925_{\displaystyle 0} & 0.0522576617_{\displaystyle 9} & 0.23507946_{\displaystyle 63}\\ 0.50875694_{\displaystyle 78} &0.203905925_{\displaystyle 2} & 0.0522576617_{\displaystyle 5} & 0.23507946_{\displaystyle 61}\\ 0.50875694_{\displaystyle 81} &0.203905925_{\displaystyle 1} & 0.0522576617_{\displaystyle 2} & 0.23507946_{\displaystyle 59} \end{array} \right) \, . $$ ♦

Реальный расчет финальных вероятностей по формулам из последнего следствия затруднителен, более конструктивен следующий результат.

Теорема 4. Пусть матрица $\mathfrak P$ — регулярна. Обозначим $ f_1(\lambda) $ — частное от деления характеристического полинома этой матрицы на $ \det (\mathfrak P-\lambda E) $ на $ \lambda -1 $. Тогда

$$\mathfrak P^{\infty}=\frac{1}{f_1(1)} f_1(\mathfrak P) \, . $$

Доказательство проведем в дополнительном предположении простоты всех собственных чисел $\{1,\lambda_2,\dots,\lambda_n\} $. Воспользуемся теоремой 2 в применении к полиному $g(x)\equiv x^K$. Положим $$f_j(\lambda):=\det (\mathfrak P-\lambda E) /(\lambda-\lambda_j) \quad \mbox{ при } \ j\in \{2,\dots,n \} . $$ Тогда $$ \mathfrak P^K=1^K \frac{f_1(\mathfrak P)}{f_1(1)}+\sum_{j=2}^{n} \lambda_j^K \frac{f_j(\mathfrak P)}{f_j(\lambda_j)} \, . $$ Поскольку $|\lambda_j|<1$ при $j\in \{2,\dots,n\}$, то при $K \to \infty$ каждое слагаемое под знаком $ \sum $ стремится к нулевой матрице. ♦

Если бы удалось установить регулярность матрицы $ \mathfrak P $ без построения ее характеристического полинома то финальные абсолютные вероятности определялись бы достаточно просто.

Вектор $ \left[p_1^{\infty},\dots,p_n^{\infty} \right]^{^{\top}} $ является собственным вектором матрицы $\mathfrak P^{^{\top}}$, принадлежащим собственному числу $\lambda=1$.

Доказательство. Действительно, по теореме Гамильтона-Кэли, $$ f_1 (\mathfrak P)(\mathfrak P-E) = \mathbb O_{n\times n} \quad \iff \quad f_1 (\mathfrak P)\mathfrak P = f_1 (\mathfrak P) \, . $$ Иначе говоря, любая строка матрицы $ f_1 (\mathfrak P) $ является левым собственным вектором матрицы $\mathfrak P $, принадлежащим собственному числу $ \lambda =1 $. Но по теореме $ 3 $, все строки матрицы $ f_1(\mathfrak P)/f_1(1) $ одинаковы и совпадают с $ \left[p_1^{\infty},\dots,p_n^{\infty} \right] $. В формулировке следствия произведен перевод этого результата в привычную терминологию обычного (правого) собственного вектора транспонированной стохастической матрицы. ♦

Пример. Найти «судьбу» студента из примера 2, т.е. определить финальные абсолютные вероятности для матрицы

$$ \mathfrak P= \left( \begin{array}{ccc} \frac{1}{2} &\frac{1}{4} & \frac{1}{4} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{6} & \frac{1}{2} \end{array} \right) \, . $$

Решение. Характеристический полином $$ f(\lambda)=\det (\mathfrak P-\lambda E)= -\lambda^3+\frac{4}{3}\,\lambda^2-\frac{13}{36}\, \lambda+\frac{1}{36} \, . $$ имеет все корни по модулю не превосходящими $ 1 $. В данном примере это устанавливается непосредственным вычислением: $\lambda_{2,3}=\frac{1}{6}$; в общем же случае можно воспользоваться критерием Шура-Кона применительно к полиному $$ f_1(\lambda)=-\lambda^2+\frac{1}{3}\,\lambda-\frac{1}{36} \, . $$ Следовательно, матрица $\mathfrak P$ регулярна. Применение теоремы 4 дает: $$ \mathfrak P^{\infty}=\frac{f_1(\mathfrak P)}{f_1(1)}=-\frac{\scriptstyle 36}{\scriptstyle 25}\left(-\mathfrak P^2+\frac{1}{3}\,\mathfrak P-\frac{1}{36} E\right)= \left( \begin{array}{lll} \frac{\scriptstyle 2}{\scriptstyle 5} &\frac{\scriptstyle 6}{\scriptstyle 25} & \frac{\scriptstyle 9}{\scriptstyle 25} \\ \frac{\scriptstyle 2}{\scriptstyle 5} &\frac{\scriptstyle 6}{\scriptstyle 25} & \frac{\scriptstyle 9}{\scriptstyle 25} \\ \frac{\scriptstyle 2}{\scriptstyle 5} &\frac{\scriptstyle 6}{\scriptstyle 25} & \frac{\scriptstyle 9}{\scriptstyle 25} \end{array} \right)\, . $$

Ответ. $ p_1^{\infty}=\frac{2}{5},\ p_2^{\infty} =\frac{6}{25},\ p_3^{\infty}=\frac{9}{25}$. Студент попался трудолюбивый: наибольшая вероятность застать его на лекции.

Для нерегулярной цепи матрица $ \mathfrak P^{\infty} $ — не обязательно одноранговая, а финальные абсолютные вероятности будут зависеть от начальных.

Пример. Определить финальные абсолютные вероятности для примера 1, если

$$\left[\frac{1}{4}, \frac{1}{3}, \frac{1}{6}, \frac{1}{6}, 0, \frac{1}{12} \right]$$ — вектор начальных вероятностей распределения генотипов в популяции.

Решение. $$\det (\mathfrak P-\lambda\, E)= \left(\lambda-\frac{1}{4} \right)\left(\lambda-\frac{1}{2}\right) \left(\lambda^2-\frac{1}{2}\, \lambda-\frac{1}{4} \right) (\lambda-1)^2 \, . $$ $$ \mathfrak P^{\infty}= \left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 &0\\ \frac{3}{4} & 0 & 0 & 0 & \frac{1}{4} &0 \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} &0 \\ \frac{1}{4} & 0 & 0 & 0 & \frac{3}{4} &0\\ 0 & 0 & 0 & 0 &1 &0 \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} &0 \end{array} \right) \quad ; \operatorname{rank} (\mathfrak P^{\infty})=2 \, . $$

Ответ. $\left[ \frac{2}{3},0,0,0,\frac{1}{3},0 \right]$. И это при том, что исходно в популяции не предполагается скрещивания особей с генотипами, соответствующими $S_5$, т.е. ${\sf aa}\times {\sf aa}$.

☞ ЗДЕСЬ

Романовский В.И. Дискретные цепи Маркова. Гостехиздат. 1948