Kemeny Random-Target Hitting
Average hitting times over a stationary random target and discover start-state invariance.
By Riano · Published · Updated · Report a correction
Kemeny Random-Target Hitting
Kemeny's constant is an intriguing invariant of finite, irreducible Markov chains. It reveals that the expected time to hit a randomly chosen target state (chosen according to the chain's stationary distribution) is the same regardless of the starting state.
Check out the model and verify the results yourself.
Worked Example
Let's verify Kemeny's constant for a simple 3-state Cycle chain (states 0, 1, 2) with a move probability α = 1. The transition matrix P is simply the cycle P0.
Check out the model and verify the results yourself.
| Quantity | Values | Explanation |
|---|---|---|
| P (Transition) | [[0, 1, 0], [0, 0, 1], [1, 0, 0]] | Deterministic cycle 0 → 1 → 2 → 0 |
| Stationary π | [1/3, 1/3, 1/3] | By symmetry, each state has equal probability. |
| Hitting m0,j | m0,0=0, m0,1=1, m0,2=2 | Time from state 0 to state j. |
| K from 0 | 1/3(0) + 1/3(1) + 1/3(2) = 1.0 | Expected time to a randomly chosen target. |
| K from 1 | 1/3(2) + 1/3(0) + 1/3(1) = 1.0 | Invariant holds for start state 1. |
Experiment
You can test the start-state invariance in the interactive model:
Check out the model and verify the results yourself.
- Open the Kemeny Random-Target Hitting module.
- Set the Chain control to
Completeand Move probability to0.5. - Observe that the K from zero, K from one, and K from two result cards all display exactly
4.0. - Change the Start control to a different state (e.g.,
1). Notice that the Selected hitting time changes depending on the Target, but the Kemeny constants remain exactly4.0.
Limitations
Kemeny's constant theorem applies to finite, irreducible Markov chains. If the move probability α is 0, the matrix becomes the identity matrix (P = I), rendering the chain reducible. In this case, states cannot communicate, the hitting times to different states are unreachable, and the theorem does not assign a unique stationary distribution or a well-defined Kemeny constant. Additionally, the hitting time to the starting state itself is conventionally 0 (not the first positive return time).
Check out the model and verify the results yourself.
References
Learn more from these primary sources.
- Markov Chains (Cambridge Statslab Draft) - Covers fundamental properties of Markov Chains, hitting times, and stationary distributions supporting the calculations used in the module.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Kemeny Random-Target Hitting module.
Try Kemeny Random-Target Hitting on Riano →