Surf Wiki
Save to docs
general/markov-processes

From Surf Wiki (app.surf) — the open knowledge base

Kemeny's constant

In probability theory, Kemeny’s constant is the expected number of time steps required for a Markov chain to transition from a starting state i to a random destination state sampled from the Markov chain's stationary distribution. Surprisingly, this quantity does not depend on which starting state i is chosen. It is in that sense a constant, although it is different for different Markov chains. When first published by John Kemeny in 1960 a prize was offered for an intuitive explanation as to why the quantity was constant.

Beyond its theoretical importance, Kemeny’s constant is also applied in practice to evaluate the efficiency of robotic surveillance strategies. More precisely, Kemeny's constant measures how quickly a robot can navigate its environment using Markov chain-based methods.

Definition

For a finite ergodic Markov chain with transition matrix P and invariant distribution π, write m**ij for the mean first passage time from state i to state j (denoting the mean recurrence time for the case i = j). Then :K = \sum_{j} \pi_j m_{ij} is a constant and not dependent on i.

Prize

Kemeny wrote, (for i the starting state of the Markov chain) “A prize is offered for the first person to give an intuitively plausible reason for the above sum to be independent of i.” Grinstead and Snell offer an explanation by Peter Doyle as an exercise, with solution “he got it!”

In the course of a walk with Snell along Minnehaha Avenue in Minneapolis in the fall of 1983, Peter Doyle suggested the following explanation for the constancy of Kemeny's constant. Choose a target state according to the fixed vector w. Start from state i and wait until the time T that the target state occurs for the first time. Let K**i be the expected value of T. Observe that :K_i+w_i \cdot 1/w_i = \sum_j P_{ij}K_j + 1 and hence :K_i = \sum_j P_{ij}K_j. By the maximum principle, K**i is a constant. Should Peter have been given the prize?

References

References

  1. (2011). "A Google-like model of road network dynamics and its application to regulation and control". International Journal of Control.
  2. (1960). "Finite Markov Chains". D. Van Nostrand.
  3. (2010). "The Kemeny Constant for Finite Homogeneous Ergodic Markov Chains". [[Journal of Scientific Computing]].
  4. (2024). "On the Trade-Off Between Efficiency and Unpredictability in Stochastic Robotic Surveillance". IEEE Control Systems Letters.
  5. (2015). "Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant". IEEE Transactions on Automatic Control.
  6. (2002). "Kemeny's Constant and the Random Surfer". The American Mathematical Monthly.
  7. (2012). "The Role of Kemeny's Constant in Properties of Markov Chains". Communications in Statistics - Theory and Methods.
  8. "Introduction to Probability".
  9. "Two exercises on Kemeny's constant".
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

markov-processes
Want to explore this topic further?

Ask Mako anything about Kemeny's constant — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report