You are here: Home :: Area NEM :: Mathematics :: Stochastics :: Statistics

Johannes Fehrenbach, Ludger Rüschendorf

Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids

In this paper we establish that the natural single point update Markov chain (also known as Glauber dynamics) for counting the number of Euler orientations of 2-dimensional Cartesian grids is rapidly mixing. This extends a result of Luby, Randall, and Sinclair (2001) who consider the case where orientations in the boundary are fixed. Similarly, we also obtain a rapid mixing result for the 3-colouring of rectangular Cartesian grids without fixing the boundaries. The proof uses path coupling and comparison to related Markov chains which allow additional transitions and which can be analysed directly.

Statistics & Decisions, Oldenbourg Wissenschaftsverlag

Print ISSN: 0721-2631
Volume: 22, 02/2004
Pages: 109 - 130

Journal homepage (external site)

Show all available items of this journal

 

Area NEM