Mathematics – Probability
Scientific paper
2007-04-12
Mathematics
Probability
16 pages, 4 figures, minor details changed (mostly typos)
Scientific paper
We study the mixing time of a systematic scan Markov chain for sampling from the uniform distribution on proper 7-colourings of a finite rectangular sub-grid of the infinite square lattice, the grid. A systematic scan Markov chain cycles through finite-size subsets of vertices in a deterministic order and updates the colours assigned to the vertices of each subset. The systematic scan Markov chain that we present cycles through subsets consisting of 2x2 sub-grids and updates the colours assigned to the vertices using a procedure known as heat-bath. We give a computer-assisted proof that this systematic scan Markov chain mixes in O(log n) scans, where n is the size of the rectangular sub-grid. We make use of a heuristic to compute required couplings of colourings of 2x2 sub-grids. This is the first time the mixing time of a systematic scan Markov chain on the grid has been shown to mix for less than 8 colours. We also give partial results that underline the challenges of proving rapid mixing of a systematic scan Markov chain for sampling 6-colourings of the grid by considering 2x3 and 3x3 sub-grids.
Jalsenius Markus
Pedersen Kasper
No associations
LandOfFree
A Systematic Scan for 7-colourings of the Grid 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 A Systematic Scan for 7-colourings of the Grid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Systematic Scan for 7-colourings of the Grid will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-148383