Gerencsér, Balázs (2020) Analysis of a non-reversible Markov chain speedup by a single edge. JOURNAL OF APPLIED PROBABILITY, közlés. ISSN 0021-9002
|
Text
1905.03223.pdf Download (963kB) | Preview |
Official URL: https://arxiv.org/pdf/1905.03223.pdf
Abstract
We present a Markov chain example where non-reversibility and an added edge jointly improve mixing time: when a random edge is added to a cycle of n vertices and a Markov chain with a drift is introduced, we get mixing time of O(n3/2) with probability bounded away from 0. If only one of the two modifications were performed, the mixing time would stay Ω(n2).
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 31 Jan 2023 14:58 |
| Last Modified: | 31 Jan 2023 14:59 |
| URI: | http://real.mtak.hu/id/eprint/157869 |
Actions (login required)
 |
Edit Item |
