On Kemeny's constant and stochastic complement
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914948487053312 |
|---|---|
| author | Bini, Dario Andrea Durastante, Fabio Kim, Sooyeong Meini, Beatrice |
| author_facet | Bini, Dario Andrea Durastante, Fabio Kim, Sooyeong Meini, Beatrice |
| contents | Given a stochastic matrix $P$ partitioned in four blocks $P_{ij}$, $i,j=1,2$, Kemeny's constant $κ(P)$ is expressed in terms of Kemeny's constants of the stochastic complements $P_1=P_{11}+P_{12}(I-P_{22})^{-1}P_{21}$, and $P_2=P_{22}+P_{21}(I-P_{11})^{-1}P_{12}$. Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real-world problems show the high efficiency and reliability of this algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_13201 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Kemeny's constant and stochastic complement Bini, Dario Andrea Durastante, Fabio Kim, Sooyeong Meini, Beatrice Numerical Analysis 60J22, 65C40, 65F15 Given a stochastic matrix $P$ partitioned in four blocks $P_{ij}$, $i,j=1,2$, Kemeny's constant $κ(P)$ is expressed in terms of Kemeny's constants of the stochastic complements $P_1=P_{11}+P_{12}(I-P_{22})^{-1}P_{21}$, and $P_2=P_{22}+P_{21}(I-P_{11})^{-1}P_{12}$. Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real-world problems show the high efficiency and reliability of this algorithm. |
| title | On Kemeny's constant and stochastic complement |
| topic | Numerical Analysis 60J22, 65C40, 65F15 |
| url | https://arxiv.org/abs/2312.13201 |