Kemeny's constant and the Lemoine point of a simplex

Karel Devriendt

TL;DR

This paper reveals a surprising geometric identity for Kemeny’s constant—a fundamental measure of how fast a Markov chain mixes. By mapping a Markov chain to a high-dimensional triangle (a simplex), the author proves that Kemeny’s constant is exactly the difference between the squared circumradius of the simplex and the squared distance from its center to its "Lemoine point."

What Problem Does This Paper Address?

In the study of Markov chains (mathematical systems that hop between states based on probabilities), Kemeny’s constant ($K$) is a bit of a celebrity. It represents the average number of steps it takes to reach a randomly chosen state, starting from anywhere. Remarkably, no matter which state you start from, this average is always the same—hence, it's a "constant."

While we have many ways to calculate $K$ using matrix algebra or eigenvalues, these methods often feel abstract. The author seeks to provide a geometric intuition. If we imagine the states of a Markov chain as the corners of a geometric shape, can we "see" Kemeny’s constant in the dimensions of that shape?

Methods

The author builds on a "dictionary" established by mathematician Miroslav Fiedler, which translates graph theory into the language of simplex geometry.

  1. The Mapping: For a specific class of Markov chains (finite, reversible, and loop-free), the author identifies each state with a vertex of a $d$-dimensional simplex (the generalization of a triangle or tetrahedron).
  2. Edge Lengths: The "distance" (specifically, the squared Euclidean distance) between two vertices in this simplex is set equal to the commute time between those two states—the average time to go from state A to B and back again.
  3. Geometric Points: The author focuses on two special points within this simplex:
  4. The Circumcenter ($\gamma$): The point equidistant from all vertices, with radius $R$.
  5. The Lemoine Point ($\ell$): A classical geometric point that minimizes the sum of squared distances to the "walls" (facets) of the simplex.
  6. The Proof: Using Laplacian matrices and Moore-Penrose pseudoinverses, the author algebraically links the coordinates of these geometric points back to the stationary distribution and hitting times of the Markov chain.

Datasets

Not discussed in the paper. This is a theoretical mathematics paper; it uses a small, constructed three-state Markov chain as a numerical example to demonstrate the theorem.

Key Insights and Ideas

  • The Lemoine Point is the Stationary Distribution: One of the most elegant findings is that the barycentric coordinates of the Lemoine point in the simplex are exactly the probabilities of the Markov chain's stationary distribution ($\pi$). In other words, the "steady state" of the system has a direct physical location in the simplex.
  • $K$ as a Geometric Deficit: The main result (Theorem A) shows that: $$K = R^2 - \|\gamma - \ell\|_2^2$$ This means Kemeny’s constant is the "leftover" squared radius after you subtract the distance between the simplex's center and its Lemoine point.

  • Simplex Geometry as a Tool: The paper suggests that the rich history of simplex geometry (dating back to the 19th century) might contain untapped tools for solving modern problems in Markov chain theory and network science.

Key Results

The paper successfully proves a new geometric expression for Kemeny’s constant.

  • Theorem A: For a finite, irreducible, aperiodic, reversible, loop-free Markov chain, Kemeny’s constant is the squared circumradius minus the squared distance between the circumcenter and the Lemoine point.
  • Numerical Validation: In a 3-state example where the circumradius $R \approx 1.1859$ and the distance $\|\gamma - \ell\| \approx 0.2372$, the formula yields $K = 1.35$, matching the value derived from traditional algebraic methods.

Limitations and Future Work

  • Restrictive Conditions: The current geometric interpretation only works for reversible Markov chains. Reversibility is a strong assumption (it implies the "flow" between any two states is balanced). Many real-world directed networks or non-reversible chains do not yet fit into this geometric framework.
  • Loop-free Assumption: The proof requires the chain to be loop-free (no staying in the same state for one step), though the author notes this is mainly to ensure the transition matrix can be represented by a Laplacian.
  • Future Directions: The author hints that this geometric perspective could be useful for understanding "nonnegative discrete curvature" in graphs. A natural next step would be exploring whether a similar geometric "point" exists for non-reversible chains or if this helps in designing chains with specific mixing properties.

Summary updated

Abstract

Kemeny's constant is an invariant of discrete-time Markov chains, equal to the expected number of steps between two states sampled from the stationary distribution. It appears in applications as a concise characterization of the mixing properties of a Markov chain and has many alternative definitions. In this short article, we derive a new geometric expression for Kemeny's constant, which involves the distance between two points in a simplex associated to the Markov chain: the circumcenter and the Lemoine point. Our proof uses an expression due to Wang, Dubbeldam and Van Mieghem of Kemeny's constant in terms of effective resistances and Fiedler's interpretation of effective resistances as edge lengths of a simplex.
BibTeX
@inproceedings{devriendt2024kemeny,
  author = {Karel Devriendt},
  title = {{Kemeny's constant and the Lemoine point of a simplex}},
  booktitle = {Electronic},
  year = {2024},
  doi = {10.13001/ela.2024.8681},
}

Loading related content...

Figure