Постоянная Кемениса - Kemenys constant - Wikipedia

В теория вероятности, Постоянная Кемени это ожидал количество временных шагов, необходимых для Цепь Маркова перейти из исходного состояния я в случайное целевое состояние, выбранное из стационарного распределения цепи Маркова. Удивительно, но это количество не зависит от того, в каком стартовом состоянии я выбран.^[1] В этом смысле это константа, хотя для разных цепей Маркова она различна. При первой публикации Джон Кемени в 1960 году была предложена премия за интуитивное объяснение того, почему количество было постоянным.^[2][3]

Определение

Для конечной эргодической цепи Маркова^[4] с матрица перехода п и инвариантное распределение π, записывать м_ij за среднее время первого перехода из штата я заявить j (обозначающее среднее время повторения для случая я = j). потом

${\displaystyle K=\sum _{j}\pi _{j}m_{ij}}$

является константой и не зависит от я.^[5]

Приз

Кемени написал (для я начальное состояние цепи Маркова) «Приз предлагается первому, кто даст интуитивно правдоподобную причину, по которой указанная выше сумма не зависит отя.”^[2] Гринстед и Snell предложите объяснение Питера Дойла в качестве упражнения с решением «он понял!»^[6][7]

Во время прогулки со Снеллом по Миннехаха-авеню в Миннеаполисе осенью 1983 года Питер Дойл предложил следующее объяснение постоянства постоянной Кемени. Выберите целевое состояние в соответствии с фиксированным вектором ш. Начать с состояния я и подожди пока время Т что целевое состояние возникает впервые. Позволять K_я быть ожидаемой стоимостью Т. Заметьте, что

${\displaystyle K_{i}+w_{i}\cdot 1/w_{i}=\sum _{j}P_{ij}K_{j}+1}$

и поэтому

${\displaystyle K_{i}=\sum _{j}P_{ij}K_{j}.}$

Посредством принцип максимума, K_я является константой. Следует ли Питеру дать приз?

Рекомендации

1. Crisostomi, E .; Kirkland, S .; Шортен, Р. (2011). «Google-подобная модель динамики дорожной сети и ее применение для регулирования и контроля». Международный журнал контроля. 84 (3): 633. Дои:10.1080/00207179.2011.568005.
2. Кемени, Дж. Г.; Снелл, Дж. Л. (1960). Конечные цепи Маркова. Принстон, Нью-Джерси: Д. Ван Ностранд. (Следствие 4.3.6)
3. Catral, M .; Киркланд, С. Дж .; Neumann, M .; Зе, Н.-С. (2010). "Константа Кемени для конечных однородных эргодических цепей Маркова" (PDF). Журнал научных вычислений. 45 (1–3): 151–166. CiteSeerX  10.1.1.295.9600. Дои:10.1007 / s10915-010-9382-1.
4. Левен, Марк; Лойзу, Джордж (2002). "Константа Кемени и случайный серфер" (PDF). Американский математический ежемесячник. 109 (8): 741–745. CiteSeerX  10.1.1.305.937. Дои:10.2307/3072398. JSTOR  3072398.
5. Хантер, Джеффри Дж. (2012). «Роль константы Кемени в свойствах цепей Маркова». Коммуникации в статистике - теория и методы. 43 (7): 1309–1321. arXiv:1208.4716. Дои:10.1080/03610926.2012.741742.
6. Гринстед, Чарльз М .; Снелл, Дж. Лори. Введение в вероятность (PDF).
7. «Два упражнения на постоянную Кемени» (PDF). Получено 1 марта 2013.^{[постоянная мертвая ссылка ]}