A combinatorial perspective on the Kemeny constant and more

Luis Fredes and Jean Francois Marckert · 2025

Read A combinatorial perspective on the Kemeny constant and more by Luis Fredes and Jean Francois Marckert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26207.txt.

Introduction

Luis Fredes and Jean-Francois Marckert give a combinatorial account of a famous constant for random walks on finite state spaces. For a Markov chain, a system that jumps between states with fixed probabilities. Kemeny proved that the expected time to hit a randomly chosen target state is the same no matter where the chain starts. That striking independence bears his name.

Fredes and Marckert show the property follows from a more general identity. They form a generating function that mixes hitting time distributions with determinants of matrices obtained by deleting one state at a time. They prove the whole sum does not depend on the start. The determinant factors at a special value recover the invariant measure, the long run state frequencies, and further results follow.

Catalog record

CREATORLuis Fredes and Jean Francois Marckert
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26207

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A combinatorial perspective on the Kemeny constant and more Luis Fredes and Jean Francois Marckert Abstract Let 𝖬 {\sf M} be an irreducible transition matrix on a finite state space V V . For a Markov chain C = ( C k , k ≥ 0 ) C=(C_{k},k\geq 0) with transition matrix 𝖬 {\sf M} , let τ u ≥ 1 \tau^{\geq 1}_{u} denote the first positive hitting time of u u by C C , and ρ \rho the unique invariant measure of 𝖬 {\sf M} . Kemeny proved that if X X is sampled according to ρ \rho independently of C C , the expected value of the first positive hitting time of X X by C C does not depend on the starting state of the chain: all the values ( 𝔼 ⁡ ( τ X ≥ 1 | C 0 = u ) , u ∈ V ) \left(\mathbb{E}(\tau^{\geq 1}_{X}\penalty\ |\penalty\ C_{0}=u),u\in V\right) are equal. In this paper, we show that this property follows from a more general result: the generating function ∑ v ∈ V 𝔼 ⁡ ( x τ v ≥ 1 | C 0 = u ) ​ det ( 𝖨𝖽 − x ​ 𝖬 ( v ) ) \sum_{v\in V}\mathbb{E}\left(x^{\tau_{v}^{\geq 1}}\penalty\ |\penalty\ C_{0}=u\right)\det\left({\sf Id}-x{\sf M}^{(v)}\right) is independent of the starting state u u , where 𝖬 ( v ) {\sf M}^{(v)} is obtained from 𝖬 {\sf M} by deleting the row and column corresponding to the state v v . The factors appearing in this generating function are: first, the probability generating function of τ v ≥ 1 \tau^{\geq 1}_{v} , and second, the sequence of determinants ( det ( 𝖨𝖽 − x ​ 𝖬 ( v ) ) , v ∈ V ) , \left(\det({\sf Id}-x{\sf M}^{(v)}),v\in V\right), which, for x = 1 x=1 , is known to be proportional to the invariant measure ( ρ u , u ∈ V ) (\rho_{u},u\in V) . From this property, we deduce several further results, including relations involving higher moments of τ X ≥ 1 \tau_{X}^{\geq 1} , which are of independent interest. 1 Introduction Notation/convention. The identity matrix of size d\times d is denoted by {\sf Id}_{d} . 1.1 Kemeny constant and a new functional identity All along the paper, C:=(C_{j},j\geq 0) stands for a Markov chain with irreducible transition matrix {\sf M} defined on a finite set V of cardinality d . The invariant measures of {\sf M} are all proportional to (\pi_{v},v\in V ) defined by \displaystyle\pi_{v}:=\det\big({\sf Id}_{d-1}-{\sf M}^{(v)}\big),\penalty\ \penalty\ \textrm{ for all }v\in V, (1.1) where {\sf M}^{(v)} is the matrix obtained from {\sf M} by the suppression of the row and column associated with v (this is a classical result that can be proved directly; see, e.g. [ 6 , Sec.1.1] , or by using the Markov chain tree theorem used to prove the correctness of Aldous-Broder algorithm [ 3 , 1 , 8 , 6 ] ). The invariant probability distribution of {\sf M} is therefore (\rho_{u},u\in V) where \rho_{u}=\pi_{u}/{\bf Z}\textrm{\penalty\ \penalty\ \penalty\ for\penalty\ \penalty\ \penalty\ }{\bf Z}=\sum_{v\in V}\pi_{v}. For any integer t\geq 0 , any state u\in V , let \displaystyle\tau_{u}^{\geq t}=\inf\big\{k\geq t:C_{k}=u\big\} (1.2) the first hitting time of state u after (and including) time t . For any real-valued function f of C , we write \mathbb{E}_{u}(f(C)) for the expectation of f(C) conditional on C_{0}=u , and {\mathbb{P}}_{u} for the distribution of C conditional on C_{0}=u . For u\in V , set Q^{\geq 1}(u):=\sum_{v\in V}\mathbb{E}_{u}\left(\tau_{v}^{\geq 1}\right)\pi_{v}. Proposition 1.1 (Kemeny [ 10 ] ) . The values \left(Q^{\geq 1}(u),u\in V\right) are all equal. Their common value, denoted by {\bf Q}^{\geq 1} , is finite. Equivalently, if X is a random variable distributed according to \rho and independent of C , the real numbers \left(\mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\right),u\in V\right) are all equal (and finite). This constancy has been discussed in many papers, and we refer to some of them here, for historical notes and applications: Kemeny and Snell [ 10 , Thm. 4.4.10] , Levene and Loizou [ 11 ] , Pitman & Tang [ 14 ] . Further discussions, connections, and references can also be found in Grinstead and Snell [ 7 , p.469-470] , Doyle [ 5 ] and Hunter [ 9 ] . Notice that the second statement is indeed equivalent to the first because \mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\right)=\sum_{v}\mathbb{E}_{u}\left(\tau_{v}^{\geq 1}\right)\rho_{v}={\bf Q}^{\geq 1}\,/\,{\bf Z} . This means that the expected value of the first positive hitting time of a point chosen according to the stationary distribution does not depend on the starting state of the chain. In the literature the common value of \mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\right)={\bf Q}^{\geq 1}\,/\,{\bf Z} is known as the Kemeny constant . There is an analogue property, concerning the \tau^{\geq t}_{v} , the first visit time of v after time t . Set Q^{\geq t}(u):=\sum_{v}\mathbb{E}_{u}\left(\tau_{v}^{\geq t}\right)\pi_{v}={\bf Z}\;\mathbb{E}_{u}(\tau_{X}^{\geq t}). A corollary of 1.1 is the following: Corollary 1.2 . For each fixed t\geq 0 , all the real numbers (Q^{\geq t}(u),u\in V) are equal. Moreover, their common value {\bf Q}^{\geq t} satisfies \displaystyle{\bf Q}^{\geq t}={\bf Z}\,t+{\bf Q}^{\geq 0}. (1.3) Proof. For each t\geq 1 , by the strong Markov property, we have \displaystyle\mathbb{E}_{u}\left(\tau_{X}^{\geq t}\right) \displaystyle= \displaystyle t-1+\sum_{v}{\mathbb{P}}_{u}(C_{t-1}=v)\mathbb{E}_{v}\left(\tau_{X}^{\geq 1}\right) \displaystyle= \displaystyle t-1+\sum_{v}{\mathbb{P}}_{u}(C_{t-1}=v)\,{\bf Q}^{\geq 1}/{\bf Z}=t-1+{\bf Q}^{\geq 1}/{\bf Z}. This expression is independent of u . Hence, {\bf Q}^{\geq t}={\bf Z}\,(t-1)+{\bf Q}^{\geq 1} . It remains to prove that {\bf Q}^{\geq 1}={\bf Z}\,+{\bf Q}^{\geq 0} . Write \displaystyle\mathbb{E}_{u}\left(\tau_{X}^{\geq 0}\right) \displaystyle= \displaystyle\mathbb{E}_{u}\left(\tau_{X}(\textbf{1}_{\tau_{X}=0}+\textbf{1}_{\tau_{X}\geq 1})\right)=\mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\textbf{1}_{X\neq u}\right)=\mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\right)-\mathbb{E}_{u}\left(\tau_{X}^{\geq 1}\textbf{1}_{X=u}\right) \displaystyle= \displaystyle{\bf Q}^{\geq 1}/{\bf Z}-\mathbb{E}_{u}\left(\tau_{u}^{\geq 1}\right)\rho_{u}={\bf Q}^{\geq 1}/{\bf Z}-1. This last equality comes from the fact that the stationary distribution satisfies \rho_{u}=1/\mathbb{E}_{u}(\tau_{u}^{\geq 1}) (see e.g. [ 13 , Theo.1.7.7] and Corollary 2.9 ). ∎ 1.2 Main result For each t\geq 0 , consider the probability-generating function of \tau_{v}^{\geq t} , starting from u : \displaystyle{\sf G}_{u,v}^{\geq t}(x) \displaystyle:= \displaystyle\mathbb{E}_{u}\left(x^{\tau_{v}^{\geq t}}\right). (1.4) It is straightforward to verify that, for all pairs (u,v) , {\sf G}_{u,v}^{\geq t} seen as the power series \sum_{k\geq 0}{\mathbb{P}}(\tau_{v}^{\geq t}=k)x^{k} , has a radius of convergence R_{u,v,t} strictly greater 1 1 1 Irreducibility implies that the graph (V,E) where E=\{(u,v)\penalty\ :\penalty\ M_{u,v}>0\} is strongly connected. Take \Delta the diameter of the directed graph (V,E) , and p the minimum, over all pairs (u,v)\in V^{2} , of the probability to go from u to v in at most \Delta steps. Clearly p>0 . Hence, starting from u , within each \Delta steps, the probability to hit v is larger than p , which implies, in fine , that {\cal L}(\tau_{v}^{\geq 0}\penalty\ |\penalty\ C_{0}=u) is smaller for the stochastic order than \Delta multiplied by a geometric random variable g with parameter p . The conclusion follows, since the radius of convergence of the probability generating function of g is R=1/(1-p) , and then the one of g\Delta is 1/(1-p)^{1/\Delta} , which is larger than 1. than 1. Hence, since V is finite, there exists a real number R_{t} satisfying 1<R_{t}<\min\{R_{u,v,t}\penalty\ :\penalty\ (u,v)\in V^{2}\}, so that all the {\sf G}_{u,v}^{\geq t} converge normally in the closed ball \overline{B}(0,R_{t}) , and even in an open ball containing \overline{B}(0,R_{t}) . Of course, here and everywhere else, power-series when considered as functions, are defined from (a subset of) \mathbb{C} to \mathbb{C} . For any u\in V

Read the complete text