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

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

Найдена в 1960 году Кемени и Шаблон:Iw

Определение

Рассмотрим дискретную, несократимую и непериодическую цепь Маркова $(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\ge 1:X_t=j).$

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

$K=\sum _{j\in S}{\pi }_j{E}_i(T_j)$

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

Свойства

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

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

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

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

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

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

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

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