Premium
On systematic scan for sampling H‐colorings of the path
Author(s) -
Pedersen Kasper
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20243
Subject(s) - combinatorics , vertex (graph theory) , completeness (order theory) , path (computing) , mathematics , markov chain , block (permutation group theory) , algorithm , discrete mathematics , computer science , statistics , graph , mathematical analysis , programming language
We show that systematic scan for H ‐colorings of the n ‐vertex path mixes in O (log n ) scans for any fixed H using block dynamics. For a restricted family of H we furthermore show that systematic scan mixes in O (log n ) scans for any scan order. For completeness we show that a random update Markov chain mixes in O ( n log n ) updates for any fixed H . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009