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

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

Определение

Рассмотрим дискретную, несократимую и непериодическую цепь Маркова ${\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}$ и называется константой Кемени.

Свойства

Константа Кемени не ограничена сверху. ${\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 году . С тех пор исследованию этого важного и популярного математического объекта было посвящено множество работ в том числе и выдающихся математиков. Однако инвариантная сумма средних времён перехода была найдена только в 1960 году в период широкого внедрения компьютеров в университетах США.

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

Примечания