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

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

Найдена в 1960 году Кемени и Снеллом

Определение

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

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

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

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

не зависит от $i$ и называется константой Кемени.

Свойства

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

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

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

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

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

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

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

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