The Cover Time of a (Multiple) Markov Chain with Rational Transition Probabilities is Rational
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929226794401792 |
|---|---|
| author | Sylvester, John |
| author_facet | Sylvester, John |
| contents | The cover time of a Markov chain on a finite state space is the expected time until all states are visited. We show that if the cover time of a discrete-time Markov chain with rational transitions probabilities is bounded, then it is a rational number. The result is proved by relating the cover time of the original chain to the hitting time of a set in another higher dimensional chain. We also extend this result to the setting where $k\geq 1 $ independent copies of a Markov chain are run simultaneously on the same state space and the cover time is the expected time until each state has been visited by at least one copy of the chain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_12356 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Cover Time of a (Multiple) Markov Chain with Rational Transition Probabilities is Rational Sylvester, John Probability Discrete Mathematics Combinatorics 60J10, 05C81, 60C05, 05C20 The cover time of a Markov chain on a finite state space is the expected time until all states are visited. We show that if the cover time of a discrete-time Markov chain with rational transitions probabilities is bounded, then it is a rational number. The result is proved by relating the cover time of the original chain to the hitting time of a set in another higher dimensional chain. We also extend this result to the setting where $k\geq 1 $ independent copies of a Markov chain are run simultaneously on the same state space and the cover time is the expected time until each state has been visited by at least one copy of the chain. |
| title | The Cover Time of a (Multiple) Markov Chain with Rational Transition Probabilities is Rational |
| topic | Probability Discrete Mathematics Combinatorics 60J10, 05C81, 60C05, 05C20 |
| url | https://arxiv.org/abs/2102.12356 |