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
| CREATOR | Luis Fredes and Jean Francois Marckert |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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