On Kemeny's Constant for Markov Processes

Basic Information

• Paper ID: 2509.19273
• Title: On Kemeny's Constant for Markov Processes
• Author: P.J. Fitzsimmons (UC San Diego)
• Classification: math.PR (Probability Theory)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2509.19273

Abstract

The average time for an irreducible finite-state Markov chain to reach a target state randomly selected according to the stationary distribution does not depend on the chain's initial state. This average time is called Kemeny's constant. This paper proposes a novel approach based on time reversal and mean occupation time formulas, and applies it to prove analogous results for continuous-time Markov processes. Under this greater generality, the constancy of the constant holds almost everywhere with respect to the stationary distribution, but through additional effort, the exceptional set can be eliminated in many cases. Several examples are provided.

Research Background and Motivation

1. Core Problem: Kemeny's constant is an important concept in Markov process theory, defined as the expected time from an arbitrary initial state to reach a target state randomly selected according to the stationary distribution. Classical results show that for irreducible Markov chains with finite state spaces, this expected time does not depend on the initial state.
2. Problem Significance:
   • Kemeny's constant holds a foundational position in Markov chain theory
   • Closely related to concepts such as mixing time and effective resistance
   • Important applications in random walks, network analysis, and other fields
3. Limitations of Existing Methods:
   • Classical results primarily address discrete-time finite-state Markov chains
   • Lack of unified methods for continuous-time cases and infinite state spaces
   • Existing proof techniques are difficult to generalize to more general settings
4. Research Motivation:
   • Develop new proof methods applicable to continuous-time Markov processes
   • Address technical difficulties in infinite state space cases
   • Provide a unified framework based on time reversal and occupation times

Core Contributions

1. Novel Proof Method: Innovative proof technique based on time reversal and mean occupation time formulas
2. Extension to Continuous Time: Extends the constancy result of Kemeny's constant to continuous-time Hunt processes
3. Treatment of Exceptional Sets: Identifies and eliminates, under specific conditions, exceptional sets where constancy fails
4. Sufficient Conditions: Provides two classes of sufficient conditions ensuring Kemeny's function is constant everywhere
5. Concrete Examples: Validates theoretical results through three specific examples

Methodology Details

Task Definition

For a Markov process $X = (X_t)_{t \geq 0}$, define Kemeny's function: $K(x) := E^x[T_Z] = \int_E E^x[T_y] \pi(dy)$ where $T_y$ is the first hitting time to state $y$, and $Z$ is a target state randomly selected according to the stationary distribution $\pi$.

Model Architecture

1. Time Reversal Duality

• Construct a dual process $\hat{X}$ satisfying the duality relation: $\int_E f(x)P_t g(x)\pi(dx) = \int_E \hat{P}_t f(y)g(y)\pi(dy)$

2. Mean Occupation Time Formula (Lemma 3.12) For a stopping time $S$ and initial distribution $\mu$, if $P^\mu[X_S \in \cdot] = \mu$, then: $E^\mu\left[\int_0^S f(X_t)dt\right] = \pi(f)E^\mu[S]$

3. Hunt's Switching Identity Utilize Hunt's switching identity to establish connections between the original and dual processes: $E^f[g(X_t); t < T_z] = \hat{E}^g[f(\hat{X}_t); t < \hat{T}_z]$

Technical Innovations

1. Unified Proof Framework

• Unifies discrete-time and continuous-time cases within a single framework
• Avoids complex combinatorial arguments in traditional methods

2. Clever Application of Duality

• Establishes deep connections between original and dual processes through time reversal
• Transforms problems into more tractable forms using duality

3. Fine Continuity Analysis

• Introduces fine topology analysis of Kemeny's function continuity
• Proves fine lower semicontinuity through properties of $\alpha$-excessive functions

Experimental Setup

Theoretical Verification Examples

Example 1: Three-Dimensional Bessel Process

• State space: $E = ]0,1]$
• Generator: $Lf(x) = \frac{1}{2}f''(x) + \frac{1}{x}f'(x)$
• Stationary distribution: $\pi(dx) = 3x^2 dx$

Example 2: Ornstein-Uhlenbeck Process

• State space: $E = \mathbb{R}$
• Generator: $Lf(x) = \frac{1}{2}f''(x) - \frac{x}{2}f'(x)$
• Stationary distribution: Standard normal distribution

Example 3: Walsh Brownian Motion

• State space: Star graph structure
• Spoke structure with $n$ branches
• Reflecting boundary conditions

Evaluation Metrics

• Exact computed values of Kemeny's constant
• Computation of effective resistance distance $\gamma$
• Consistency between theoretical predictions and computed results

Experimental Results

Main Results

Theorem 3.9 (Main Result) Let $K(x) := E^x[T_Z]$ and $\hat{\kappa} := \hat{E}^\pi[\hat{T}_Z]$. If $\hat{\kappa} < \infty$, then:

• $K(x) \leq \hat{\kappa}$ for all $x \in E$
• $K(x) = \hat{\kappa}$ for $\pi$-almost all $x \in E$

Theorem 4.18 (Sufficient Condition 1) If there exists a measurable function $C: E \to ]0,\infty[$ such that $E^x[T_z] \leq C(z)$ for all $x,z$, then $K$ is finely continuous, and thus $K(x) = \hat{\kappa}$ for all $x$.

Theorem 5.9 (Sufficient Condition 2) Assume all points are regular. If $\gamma := \int_E \int_E h(x,y)\pi(dx)\pi(dy) < \infty$, then $K(x) = \hat{K}(x) = \kappa = \hat{\kappa} = \gamma/2$ for all $x \in E$.

Specific Computational Results

Three-Dimensional Bessel Process:

• $K(x) = \frac{1}{5}$ (constant)
• $\gamma = \frac{2}{5}$
• Verified the relation $\kappa = \gamma/2$

Ornstein-Uhlenbeck Process:

• $\gamma = \infty$
• $K(x) = \infty$ for all $x$

Walsh Brownian Motion:

• $n$ branches case: $\kappa = \frac{n-2}{3}$
• Infinite branches case: $\kappa = \infty$

Experimental Findings

1. Role of Effective Resistance: In the reversible case, $h(x,y)$ is precisely the effective resistance distance
2. Impact of Boundary Conditions: For diffusion processes, boundary type determines the finiteness of Kemeny's constant
3. Patterns in Branch Structures: Results for Walsh Brownian motion reveal how graph structure influences Kemeny's constant

Related Work

Historical Development

• Kemeny-Snell (1960): First introduced the concept of Kemeny's constant for finite Markov chains
• Doyle (2009): Provided a concise proof method
• Pinsky (2019): Extended results to one-dimensional diffusion processes

Related Theory

• Aldous-Fill Formula: Foundational theory for mean occupation times
• Hunt Process Theory: General framework for continuous-time Markov processes
• Effective Resistance Theory: Connections to random walks on graphs

Advantages of This Work

1. Provides a unified method applicable to general Hunt processes
2. Addresses technical difficulties in infinite state spaces
3. Establishes deep connections with effective resistance distance

Conclusions and Discussion

Main Conclusions

1. General Results: Establishes constancy of Kemeny's constant within the continuous-time Hunt process framework
2. Treatment of Exceptional Sets: Identifies and eliminates, under specific conditions, exceptional sets where constancy fails
3. Sufficient Conditions: Provides two classes of practical sufficient conditions ensuring constancy everywhere
4. Geometric Interpretation: Connects Kemeny's constant to effective resistance distance

Limitations

1. Technical Assumptions: Requires processes to satisfy duality and regularity assumptions
2. Exceptional Sets: In the most general case, $\pi$-null exceptional sets may still exist
3. Computational Complexity: Actual computation of Kemeny's constant remains difficult

Future Directions

1. Ray-Knight Compactification: Explore connections with Ray space theory
2. More General Processes: Extend to broader classes of Markov processes
3. Algorithm Development: Develop efficient numerical computation methods

In-Depth Evaluation

Strengths

1. Theoretical Depth: Generalizes classical results to continuous-time cases with refined technical treatment
2. Methodological Innovation: The combination of time reversal and occupation time formulas provides new proof insights
3. Complete Results: Provides not only main theorems but also sufficient conditions for eliminating exceptional sets
4. Rich Examples: Three concrete examples effectively validate and illustrate theoretical results

Weaknesses

1. Readability: Highly technical with some barriers for non-specialist readers
2. Application-Oriented: Emphasizes theoretical development with limited discussion of practical applications
3. Computational Methods: Lacks systematic numerical computation algorithms

Impact

1. Theoretical Contribution: Provides important theoretical supplements to Markov process theory
2. Methodological Value: Time reversal techniques may have applications in other problems
3. Future Research: Establishes foundation for further theoretical development

Applicable Scenarios

1. Stochastic Process Theory: Research in Markov process theory
2. Probability Theory: Problems related to first hitting times and stationary distributions
3. Applied Mathematics: Theoretical foundations for network analysis, queueing theory, and other fields

References

Main references include:

• Kemeny, J.G. and Snell, J.L.: Finite Markov Chains (1960)
• Blumenthal, R.M. and Getoor, R.K.: Markov Processes and Potential Theory (1968)
• Pinsky, R.: Kemeny's constant for one-dimensional diffusions (2019)
• Eisenbaum, N. and Kaspi, H.: On the continuity of local times (2007)

This paper makes important contributions to Markov process theory, particularly in establishing general theory for the constancy of Kemeny's constant in continuous-time cases. Although technically demanding, it provides a solid foundation for theoretical development in this field.