On systematic scan for sampling H-colourings of the path

Details On systematic scan for sampling H-colourings of the path On systematic scan for sampling H-colourings of the path

2007-06-26

arxiv.org/abs/0706.3794v1

Mathematics

Probability

28 pages, 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On systematic scan for sampling H-colourings of the path does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On systematic scan for sampling H-colourings of the path, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On systematic scan for sampling H-colourings of the path will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-505795