Главная
Константа Кемени — среднее число шагов перехода в случайно выбранное состояние конечной цепи Маркова, находящейся в стационарном состоянии, из некоторого исходного состояния i {displaystyle i} . Эта величина не зависит от номера исходного состояния и является инвариантом цепи Маркова.
Найдена в 1960 году Кемени и Снеллом
Определение
Рассмотрим дискретную, несократимую и непериодическую цепь Маркова ( X t : t = 0 , 1 , . . . ) {displaystyle (X_{t}:t=0,1,...)} на конечном пространстве состояний S {displaystyle S} с матрицей вероятностей переходов P {displaystyle P} и вектором стационарных вероятностей π {displaystyle pi } таким, что π T P = π T {displaystyle pi ^{T}P=pi ^{T}} и π T 1 = 1 {displaystyle pi ^{T}1=1} . Для j ∈ S {displaystyle jin S} определим «время первого перехода» в состояние j {displaystyle j} .
T j = inf ( t ≥ 1 : X t = j ) . {displaystyle T_{j}=inf(tgeq 1:X_{t}=j).}
Обозначим E i ( ) {displaystyle E_{i}()} математическое ожидание при условии, что X 0 = i {displaystyle X_{0}=i} . Тогда
K = ∑ j ∈ S π j E i ( T j ) {displaystyle K=sum _{jin S}pi _{j}E_{i}(T_{j})}не зависит от i {displaystyle i} и называется константой Кемени.
Свойства
Константа Кемени не ограничена сверху. K → ∞ {displaystyle K o infty } при p → 0 {displaystyle p o 0} например для цепи Маркова с матрицей вероятностей переходов
( 1 − p p p 1 − p ) {displaystyle left({egin{matrix}1-p&pp& 1-pend{matrix}} ight)}Константа Кемени для цепи Маркова, имеющей n {displaystyle n} состояний, ограничена снизу величиной ( n + 1 ) / 2 {displaystyle (n+1)/2} . Стремление к нижней грани имеет место, если в каждой строке матрицы вероятностей переходов один элемент с несовпадающими индексами строки и столбца стремится к 1, например для матрицы
( p 1 − p 1 − p p ) {displaystyle left({egin{matrix}p&1-p1-p& pend{matrix}} ight)}В пределе такая цепь циклично проходит n {displaystyle n} своих состояний в некотором порядке.
Любопытные факты
Понятие цепи Маркова было введено российским учёным Марковым в 1906 году. С тех пор исследованию этого важного и популярного математического объекта было посвящено множество работ в том числе и выдающихся математиков. Однако инвариантная сумма средних времён перехода была найдена только в 1960 году в период широкого внедрения компьютеров в университетах США.
В 1997 году Гримстед и Шелл предложили премию за простое и интуитивно понятное объяснение, почему константа Кемени — это константа. В 2009 году этот приз выиграл Дойл. Последняя статья под названием «Почему константа Кемени — это константа?» опубликована несколькими учёными в 2017 году. В статье описана и физическая интерпретация этой константы.