On systematic scan for sampling H-colourings of the path
| dc.creator | Pedersen, Kasper | |
| dc.date | 2007-06-26 | |
| dc.date.accessioned | 2026-07-07T08:12:26Z | |
| dc.date.available | 2026-07-07T08:12:26Z | |
| dc.description | This paper is concerned with sampling from the uniform distribution on H-colourings of the n-vertex path using systematic scan Markov chains. An H-colouring of the n-vertex path is a homomorphism from the n-vertex path to some fixed graph H. We show that systematic scan for H-colourings of the n-vertex path mixes in O(log n) scans for any fixed H. This is a significant improvement over the previous bound on the mixing time which was O(n^5) scans. Furthermore we show that for a slightly more restricted family of H (where any two vertices are connected by a 2-edge path) systematic scan also mixes in O(log n) scans for any scan order. Finally, for completeness, we show that a random update Markov chain mixes in O(n log n) updates for any fixed H, improving the previous bound on the mixing time from O(n^5) updates. | |
| dc.description | 28 pages, 5 figures | |
| dc.identifier | https://arxiv.org/abs/0706.3794 | |
| dc.identifier | http://arxiv.org/abs/0706.3794 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132454 | |
| dc.subject | Probability | |
| dc.subject | 60J10 | |
| dc.title | On systematic scan for sampling H-colourings of the path | |
| dc.type | text |