kemenyConstant: Kemeny's constant of a Markov chain

In markovchain: Easy Handling Discrete Time Markov Chains

Kemeny's constant of a Markov chain

Description

Computes Kemeny's constant for a finite, irreducible discrete-time Markov chain. It is the stationary-distribution-weighted mean hitting time of a randomly selected destination and is independent of the starting state.

Usage

kemenyConstant(object)

## S4 method for signature 'markovchain'
kemenyConstant(object)

Arguments

object

A markovchain object representing a finite, irreducible discrete-time Markov chain.

Details

For a row-stochastic transition matrix P, let \pi be its unique stationary distribution and define

Z = (I - P + \mathbf{1}\pi^T)^{-1}.

With hitting times defined by T_j = \inf\{n \ge 0: X_n=j\}, so that m_{jj}=0, the function returns

K = \sum_j \pi_j m_{ij} = \mathrm{tr}(Z)-1.

The value does not depend on the starting state i.

Irreducibility is sufficient; aperiodicity is not required. Reducible chains can have multiple stationary distributions and are rejected.

Some references instead put the mean first-return time m_{jj}=1/\pi_j on the diagonal. Under that convention the corresponding stationary weighted sum is K+1, not K. This function uses the zero-diagonal hitting-time convention, consistently with meanFirstPassageTime().

The implementation uses a dense LAPACK solve for the fundamental matrix Z. Its time complexity is O(n^3) and its memory use is O(n^2), as expected for a dense exact computation. It supports both row- and column-stochastic storage.

Value

A numeric scalar containing Kemeny's constant.

References

Kemeny, J. G. and Snell, J. L. (1960). Finite Markov Chains. D. Van Nostrand, Princeton, NJ.

See Also

meanFirstPassageTime, steadyStates, is.irreducible

Examples

statesNames <- c("a", "b")
mc <- new("markovchain",
  states = statesNames,
  transitionMatrix = matrix(c(0.7, 0.3, 0.1, 0.9),
    byrow = TRUE, nrow = 2,
    dimnames = list(statesNames, statesNames)))
kemenyConstant(mc)

markovchain documentation built on Oct. 10, 2026, 9:07 a.m.