Kemenysova konstanta - Kemenys constant - Wikipedia

v teorie pravděpodobnosti, Kemenyho konstanta je očekávaný počet časových kroků potřebných pro a Markovův řetězec k přechodu z počátečního stavu i do náhodného cílového stavu vzorkovaného ze stacionární distribuce řetězce Markov. Překvapivě toto množství nezávisí na tom, ve kterém počátečním stavu i je vybrán.^[1] V tomto smyslu je to konstanta, i když je to u různých markovských řetězců jiné. Při prvním publikování John Kemeny v roce 1960 byla nabídnuta cena za intuitivní vysvětlení, proč je množství konstantní.^[2][3]

Definice

Pro konečný ergodický Markovův řetězec^[4] s přechodová matice P a invariantní distribuce π, psát si m_ij pro střední dobu prvního průchodu ze stavu i do stavu j (označující průměrnou dobu opakování pro případ i = j). Pak

${ displaystyle K = součet _ {j} pi _ {j} m_ {ij}}$

je konstanta a není závislá na i.^[5]

Cena

Kemeny napsal (pro i počáteční stav řetězce Markov) „Cena je nabízena první osobě, která dává intuitivně věrohodný důvod, aby výše uvedená částka byla nezávislá nai.”^[2] Grinstead a Snell nabídněte vysvětlení Petera Doyla jako cvičení s řešením „dostal to!“^[6][7]

Na procházce se Snellem po ulici Minnehaha v Minneapolisu na podzim roku 1983 navrhl Peter Doyle následující vysvětlení stálosti Kemenyho konstanty. Vyberte cílový stav podle pevného vektoru w. Začněte od státu i a počkejte, až čas T že cílový stav nastane poprvé. Nechat K._i být očekávanou hodnotou T. Dodržujte to

${ displaystyle K_ {i} + w_ {i} cdot 1 / w_ {i} = součet _ {j} P_ {ij} K_ {j} +1}$

a tudíž

${ displaystyle K_ {i} = součet _ {j} P_ {ij} K_ {j}.}$

Podle maximální princip, K._i je konstanta. Měl Peter dostat cenu?

Reference