A combinatorial perspective on the Kemeny constant and more
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917050230767616 |
|---|---|
| author | Fredes, Luis Marckert, Jean-François |
| author_facet | Fredes, Luis Marckert, Jean-François |
| contents | Let $M$ be an irreducible transition matrix on a finite state space $V$. For a Markov chain $C=(C_k,k\geq 0)$ with transition matrix $M$, let $τ^{\geq 1}_u$ denote the first positive hitting time of $u$ by $C$, and $ρ$ the unique invariant measure of $M$. Kemeny proved that if $X$ is sampled according to $ρ$ independently of $C$, the expected value of the first positive hitting time of $X$ by $C$ does not depend on the starting state of the chain: all the values $(E(τ^{\geq 1}_X~|~C_0=u), u \in V)$ are equal. \par
In this paper, we show that this property follows from a more general result: the generating function $\sum_{v\in V}E(x^{τ_v^{\geq 1}}~|~C_0=u)\det(Id-xM^{(v)})$ is independent of the starting state $u$, where $M^{(v)}$ is obtained from $M$ by deleting the row and column corresponding to the state $v$. The factors appearing in this generating function are: first, the probability generating function of $τ^{\geq 1}_v$, and second, the sequence of determinants $(det(Id-xM^{(v)}),v\in V),$ which, for $x=1$, is known to be proportional to the invariant measure $(ρ_u,u\in V)$.
From this property, we deduce several further results, including relations involving higher moments of $τ_X^{\geq 1}$, which are of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26207 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A combinatorial perspective on the Kemeny constant and more Fredes, Luis Marckert, Jean-François Probability Let $M$ be an irreducible transition matrix on a finite state space $V$. For a Markov chain $C=(C_k,k\geq 0)$ with transition matrix $M$, let $τ^{\geq 1}_u$ denote the first positive hitting time of $u$ by $C$, and $ρ$ the unique invariant measure of $M$. Kemeny proved that if $X$ is sampled according to $ρ$ independently of $C$, the expected value of the first positive hitting time of $X$ by $C$ does not depend on the starting state of the chain: all the values $(E(τ^{\geq 1}_X~|~C_0=u), u \in V)$ are equal. \par In this paper, we show that this property follows from a more general result: the generating function $\sum_{v\in V}E(x^{τ_v^{\geq 1}}~|~C_0=u)\det(Id-xM^{(v)})$ is independent of the starting state $u$, where $M^{(v)}$ is obtained from $M$ by deleting the row and column corresponding to the state $v$. The factors appearing in this generating function are: first, the probability generating function of $τ^{\geq 1}_v$, and second, the sequence of determinants $(det(Id-xM^{(v)}),v\in V),$ which, for $x=1$, is known to be proportional to the invariant measure $(ρ_u,u\in V)$. From this property, we deduce several further results, including relations involving higher moments of $τ_X^{\geq 1}$, which are of independent interest. |
| title | A combinatorial perspective on the Kemeny constant and more |
| topic | Probability |
| url | https://arxiv.org/abs/2510.26207 |