| Математические заметки |
|
|
|
|
|
Коэффициент эргодичности. Новые доказательства известных свойств Ю. А. Альпин, Н. Н. Корнееваa a Казанский (Приволжский) федеральный университет
Английская версия:
Mathematical Notes, 2023, Volume 114, Issue 6, Pages DOI: https://doi.org/10.1134/S0001434623110433 
Реферативные базы данных:
 1. ВведениеНеотрицательная матрица $A=(a_{ij})$ называется стохастической, если сумма элементов любой ее строки равна единице. Стохастические матрицы служат основным инструментом теории конечных цепей Маркова [1]. Важнейшим понятием теории является коэффициент эргодичности. Коэффициентом эргодичности стохастической (необязательно квадратной) матрицы $A=(a_{ij})$ называется число
$$
\begin{equation}
\delta(A)=1-\min_{i_1,i_2}\sum_j\min (a_{i_1,j},a_{i_2,j}).
\end{equation}
\tag{1.1}
$$
Если $A$ имеет одну строку или один столбец, то логично положить $\delta(A)=0$. Традиционно считается, что коэффициент эргодичности впервые появился в работе [2]. Однако Сенета [3] установил, что коэффициент эргодичности в неявном виде использовался уже в статье Маркова [4]. Стохастическая матрица называется стягивающей, если любые две ее строки имеют положительные элементы в некотором общем столбце. Из формулы (1.1) следует, что 1) $0\leqslant \delta (A)\leqslant 1$; 2) $\delta (A)=0$ тогда и только тогда, когда все строки $A$ равны; 3) $\delta (A)<1$ тогда и только тогда, когда матрица $A$ стягивающая. Роль коэффициента эргодичности в теории цепей Маркова объясняется двумя его свойствами, приводимыми ниже. Коэффициент эргодичности обладает свойством субмультипликативности, т.е. имеет место следующая Теорема 1. Пусть $A$ и $B$ – стохастические матрицы, для которых существует произведение $AB$. Тогда Известно, что для любой стохастической матрицы порядка $n$ единица является собственным значением, причем остальные $n-1$ собственных значений по модулю не больше единицы (см., например, [1], [5]). Коэффициент эргодичности является верхней границей для собственных значений, неравных единице, т.е. имеет место следующая Теорема 2. Все собственные значения стохастической матрицы $A$, за исключением, возможно, единицы, удовлетворяют неравенству Существуют различные доказательства теорем 1 и 2. Обзор результатов, связанных с коэффицентом эргодичности, снабженный полными доказательствами и обширной библиографией, можно найти в [6]. Целью этой заметки являются новые, более простые, доказательства теорем 1 и 2. Решающее значение в этих доказательствах имеют леммы о двустрочных стохастических матрицах. 2. Двустрочные стохастические матрицыПредположим, что даны стохастические строки $\mu=(\mu_j)$, $\pi=(\pi_j)$ длины $n$. Коэффициент эргодичности матрицы обозначим через $\delta(\mu,\pi)$. Согласно (1.1)Лемма 1. Для неравных стохастических строк $\mu$ и $\pi$ существуют такие стохастические строки $\varphi$ и $\psi$, что Доказательство. Определим неотрицательные строки
$$
\begin{equation*}
\begin{gathered} \, \mu'=(\mu'_j), \qquad\text{где}\quad \mu'_j=\mu_j-\min(\mu_j,\pi_j), \\ \pi'=(\pi'_j), \qquad\text{где}\quad \pi'_j=\pi_j-\min(\mu_j,\pi_j). \end{gathered}
\end{equation*}
\notag
$$
Пусть $\mathbf{1}$ – столбец, все элементы которого равны 1. Тогда $\mu'\mathbf{1}=\pi'\mathbf{1}=\delta(\mu,\pi)$. Действительно,
$$
\begin{equation*}
\sum_j(\mu_j-\min(\mu_j,\pi_j))=\sum_j(\pi_j-\min(\mu_j,\pi_j)) =1-\sum_j\min(\mu_j,\pi_j)=\delta(\mu,\pi).
\end{equation*}
\notag
$$
Поскольку $\mu\neq\pi$, то $\delta(\mu,\pi)>0$. Определим стохастические строки
$$
\begin{equation*}
\varphi=\delta^{-1}(\mu,\pi)\mu', \qquad \psi=\delta^{-1}(\mu,\pi)\pi'.
\end{equation*}
\notag
$$
Легко проверить, что для строк $\varphi$ и $\psi$ верно равенство (2.1). Пусть $z=(z_1,\dots,z_n)^{\top}]$ – комплексный столбец. Положим, что Лемма 2. Пусть $\mu=(\mu_1,\dots,\mu_n)$, $\pi=(\pi_1,\dots,\pi_n)$ – стохастические строки, $z=(z_1,\dots,z_n)^{\top}$ – комплексный столбец. Тогда Доказательство. Вначале докажем вспомогательное неравенство Действительно,
Переходя к доказательству основного утверждения, заметим, что при $\mu=\pi$ лемма верна, так как обе части в неравенстве (2.2) обращаются в 0. Дальше считаем, что $\mu\neq \pi$. Используя представление (2.1) и применяя неравенство (2.3) к стохастическим строкам $\varphi$ и $\psi$, получим Следствие 1. Пусть $z=(z_i)$ – произвольный комплексный столбец высоты $n$, $a=(a_i)$ – вещественная строка длины $n$, причем сумма элементов $a$ равна 0. Тогда Доказательство. Обозначим через $a^+$ строку, полученную из $a$ заменой отрицательных элементов нулями, и положим, что $a^-=a^+-a$. Сумма элементов в строках $a^+$ и $a^-$ одна и та же, обозначим ее через $s$. Применим неравенство (2.3) к непересекающимся стохастическим строкам $s^{-1}a^+$ и $s^{-1}a^-$:
$$
\begin{equation*}
|(s^{-1}a^+-s^{-1}a^-)z|\leqslant d(z) \quad\Longrightarrow\quad |(a^+-a^-)z|\leqslant sd(z).
\end{equation*}
\notag
$$
Учитывая, что $a^+-a^-=a$ и $s=(1/2)\sum_{i=1}^n|a_i|$, получим (2.4). Замечание 1. Неравенство (2.4) впервые было опубликовано в [7]. Его доказательство, представленное выше, основано на иных соображениях, чем оригинальное, и намного проще. О связи неравенства (2.4) с работой Маркова [4] см. в [3]. Лемма 3. Для любых стохастических строк $\mu=(\mu_j)$, $\pi=(\pi_j)$ длины $n$ существует такой $(0,1)$-столбец $z=(z_j)$, что Доказательство. При $\mu=\pi$ утверждение леммы тривиально верно. Дальше считаем, что $\mu\neq\pi$. Для любого $(0,1)$-столбца $z=(z_j)$ имеют место равенства
$$
\begin{equation*}
(\mu-\pi)z=\sum_j(\mu_j-\pi_j)z_j=\sum_j(\mu_j-\min(\mu_j,\pi_j))z_j - \sum_j(\pi_j-\min(\mu_j,\pi_j))z_j.
\end{equation*}
\notag
$$
Определим столбец $z=(z_j)$ условиями Тогда 3. Следствия для стохастических матриц произвольного размераОбозначим $i$-ю строку стохастической $(m\times n)$-матрицы $A=(a_{ij})$ символом $a_i$. Тогда коэффициент эргодичности (1.1) можно записать так: Действительно,
$$
\begin{equation*}
\delta(A)=1-\min_{i_1,i_2}\sum_j\min (a_{i_1,j},a_{i_2,j})=\max_{i_1,i_2} \biggl(1-\sum_j\min (a_{i_1,j},a_{i_2,j})\biggr)=\max_{i_1,i_2}\delta(a_{i_1},a_{i_2}).
\end{equation*}
\notag
$$
Теорема 3. Пусть $A=(a_{ij})$ – стохастическая $(m\times n)$-матрица, $z$ – комплексный столбец высоты $n$. Тогда Доказательство. По теореме 3 для любого $(0,1)$-столбца $z$ имеем
$$
\begin{equation}
d(Az)=\max_{i_1,i_2}|(a_{i_1}-a_{i_2})z|\leqslant \max_{i_1,i_2}\delta(a_{i_1},a_{i_2})=\delta(A).
\end{equation}
\tag{3.2}
$$
Пусть строки $a_l,a_m$ таковы, что $\delta(a_l,a_m)=\max_{i_1,i_2}\delta(a_{i_1},a_{i_2})=\delta(A)$. По лемме 3 существует $(0,1)$-столбец $z$, для которого Отсюда и из (3.2) видно, что поэтому $d(Az)=\delta(A)$. Доказательство теоремы 1. Существует по лемме 4 такой $(0,1)$-столбец $z$, для которого $d(ABz)=\delta(AB)$. Далее, в силу теоремы 3 имеем Из теоремы 1 легко выводится В частности, Доказательство теоремы 2. Векторы $z\neq 0$, для которых $d(z)=0$, пропорциональны вектору $\mathbf{1}$ и потому являются собственными векторами, отвечающими собственному значению $1$. Следовательно, если собственный вектор $z$ отвечает собственному значению $\lambda\neq1$, то $d(z)>0$. Для таких векторов согласно теореме 3 имеем
$$
\begin{equation*}
d(Az)=d(\lambda z)=|\lambda|d(z)\leqslant \delta(A)d(z).
\end{equation*}
\notag
$$
Из последнего неравенства следует утверждение теоремы 2. 
Цитирование в формате AMSBIB
\RBibitem{AlpKor23} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|