Kemeny's constant #
For a finite Markov chain with transition matrix P, a stationary distribution π and finite
expected hitting times m s t (m t t = 0, m s t = 1 + Σ_k P s k · m k t for s ≠ t), the
expected time Σ_t π t · m s t to reach a π-random target does not depend on s (Theorem of the
Day). Proof: Kac's formula π_t (1 + Σ_k P_tk m_kt) = 1 from stationarity turns
f(s) = Σ_t π_t m_st into a harmonic function f = P f, and the hitting-time equations force a
harmonic function to be constant (minimum principle on the set where f is maximal).
Main results #
Kemeny.kac: Kac's formula π_t (1 + Σ_k P t k · m k t) = 1Kemeny.harmonic: f(s) = Σ_t π t · m s t satisfies f = P fKemeny.exists_const: Kemeny: Σ_t π t · m s t does not depend on s
References #
- R. Whitty, Theorem of the Day, «Kemeny's Constant» (Statistics/Kemeny).
- J. G. Kemeny, J. L. Snell, Finite Markov Chains, Van Nostrand 1960; P. Doyle, The Kemeny constant of a Markov chain (math.dartmouth.edu/~doyle/docs/kc/kc.pdf).
theorem
Kemeny.exists_const
{ι : Type u_1}
[Fintype ι]
[DecidableEq ι]
(P : Matrix ι ι ℝ)
(hP0 : ∀ (s k : ι), 0 ≤ P s k)
(hP1 : ∀ (s : ι), ∑ k : ι, P s k = 1)
(π : ι → ℝ)
(hπ : ∀ (k : ι), ∑ s : ι, π s * P s k = π k)
(hπ1 : ∑ s : ι, π s = 1)
(m : ι → ι → ℝ)
(hmt : ∀ (t : ι), m t t = 0)
(hm : ∀ (s t : ι), s ≠ t → m s t = 1 + ∑ k : ι, P s k * m k t)
: