Константа Кемени

Константа Кемени — среднее число шагов перехода в случайно выбранное состояние конечной цепи Маркова, находящейся в стационарном состоянии, из некоторого исходного состояния ${\displaystyle i}$. Эта величина не зависит от номера исходного состояния и является инвариантом цепи Маркова.

Найдена в 1960 году Кемени и Снеллом^{[англ.][1]}

Определение

Рассмотрим дискретную, несократимую и непериодическую цепь Маркова ${\displaystyle (X_{t}:t=0,1,...)}$ на конечном пространстве состояний ${\displaystyle S}$ с матрицей вероятностей переходов ${\displaystyle P}$ и вектором стационарных вероятностей ${\displaystyle \pi }$ таким, что ${\displaystyle \pi ^{T}P=\pi ^{T}}$ и ${\displaystyle \pi ^{T}1=1}$. Для ${\displaystyle j\in S}$ определим «время первого перехода» в состояние ${\displaystyle j}$.

${\displaystyle T_{j}=\inf(t\geq 1:X_{t}=j).}$

Обозначим ${\displaystyle E_{i}()}$ математическое ожидание при условии, что ${\displaystyle X_{0}=i}$. Тогда

${\displaystyle K=\sum _{j\in S}\pi _{j}E_{i}(T_{j})}$

не зависит от ${\displaystyle i}$ и называется константой Кемени.^[1][2]

Свойства

Константа Кемени не ограничена сверху. ${\displaystyle K\to \infty }$ при ${\displaystyle p\to 0}$ например для цепи Маркова с матрицей вероятностей переходов

${\displaystyle \left({\begin{matrix}1-p&p\\p&\ 1-p\end{matrix}}\right)}$

Константа Кемени для цепи Маркова, имеющей ${\displaystyle n}$ состояний, ограничена снизу величиной ${\displaystyle (n+1)/2}$. Стремление к нижней грани имеет место, если в каждой строке матрицы вероятностей переходов один элемент с несовпадающими индексами строки и столбца стремится к 1, например для матрицы

${\displaystyle \left({\begin{matrix}p&1-p\\1-p&\ p\end{matrix}}\right)}$

В пределе такая цепь циклично проходит ${\displaystyle n}$ своих состояний в некотором порядке.

Любопытные факты

Понятие цепи Маркова было введено российским учёным Марковым в 1906 году^[3]. С тех пор исследованию этого важного и популярного математического объекта было посвящено множество работ в том числе и выдающихся математиков. Однако инвариантная сумма средних времён перехода была найдена только в 1960 году в период широкого внедрения компьютеров в университетах США.

В 1997 году Гримстед и Шелл предложили премию за простое и интуитивно понятное объяснение, почему константа Кемени — это константа.^[4] В 2009 году этот приз выиграл Дойл.^[5] Последняя статья под названием «Почему константа Кемени — это константа?» опубликована несколькими учёными в 2017 году. В статье описана и физическая интерпретация этой константы.^[6]

Примечания

1. J. G. Kemeny and J. L. Snell. Finite Markov Chains. Van Nostrand, Princeton, NJ, 1960.
2. Hunter, Jeffrey J. The Role of Kemeny's Constant in Properties of Markov Chains (англ.) // Communications in Statistics - Theory and Methods : journal. — 2012. — Vol. 43, no. 7. — P. 1309—1321. — doi:10.1080/03610926.2012.741742. — arXiv:1208.4716.
3. Gagniuc, Paul A. Markov Chains: From Theory to Implementation and Experimentation (англ.). — USA, NJ: John Wiley & Sons, 2017. — P. 2—8. — ISBN 978-1-119-38755-8.
4. C. M. Grinstead and J. L. Snell. Introduction to Probability. AMS, Providence, R.I., 1997. (с. 469)
5. The Kemeny constant of a Markov chain.
6. Why is Kemeny’s constant a constant?