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

Константа Кемени — среднее число шагов перехода в случайно выбранное состояние конечной цепи Маркова, находящейся в стационарном состоянии, из некоторого исходного состояния ${\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]