Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908714178445312 |
|---|---|
| author | Durastante, Fabio Gnazzo, Miryam Meini, Beatrice |
| author_facet | Durastante, Fabio Gnazzo, Miryam Meini, Beatrice |
| contents | Kemeny's constant measures the efficiency of a Markov chain in traversing its states. We investigate whether structure-preserving perturbations to the transition probabilities of a reversible Markov chain can improve its connectivity while maintaining a fixed stationary distribution. Although the minimum achievable value for Kemeny's constant can be estimated, the required perturbations may be infeasible. We reformulate the problem as an optimization task, focusing on solution existence and efficient algorithms, with an emphasis to the problem of minimizing Kemeny's constant under sparsity constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24679 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations Durastante, Fabio Gnazzo, Miryam Meini, Beatrice Numerical Analysis Probability 60J22, 65C40, 90C30, 53A99 Kemeny's constant measures the efficiency of a Markov chain in traversing its states. We investigate whether structure-preserving perturbations to the transition probabilities of a reversible Markov chain can improve its connectivity while maintaining a fixed stationary distribution. Although the minimum achievable value for Kemeny's constant can be estimated, the required perturbations may be infeasible. We reformulate the problem as an optimization task, focusing on solution existence and efficient algorithms, with an emphasis to the problem of minimizing Kemeny's constant under sparsity constraints. |
| title | Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations |
| topic | Numerical Analysis Probability 60J22, 65C40, 90C30, 53A99 |
| url | https://arxiv.org/abs/2510.24679 |