Exact sampling and approximate counting techniques

摘要: We present two algorithms for uniformly sampling from the proper colorings of a graph using colors. use exact stationary distribution Markov chain with states that are -colorings maximum degree . As opposed to approximate based on rapid mixing, these have termination criteria allow them stop some inputs much more quickly than in worst case running time bound. For first algorithm we show when , has an upper limit expected is polynomial. second where integer satisfies Previously, Jerrum showed it was possible approximately sample polynomial set but our this problem. Using sampling, also how count number -colorings. give new procedure counting improves by factor nodes be colored and edges. In addition, improved analysis Luby Vigoda independent sets graph. Finally, method exactly sink free orientations Bubley Dyer state space ! " $#&%(') +*-,/.0 1 time, takes 23 45 time. 6 This work partially supported Office Naval Research Fellowship NSF grants CCR-9307391, CCR-9700029, DMS-9505155, ONR grant N00014-96-1-00500 Introduction Recently exciting results appeared area Monte Carlo Chain (MCMC) theory. One such result Propp Wilson [10] known as coupling past (CFTP), which allows us directly certain chains without visiting each chain. Many arise naturally out statistical mechanics problems exponential size input. Although makes impossible efficiently compute entire distribution, CFTP can still distribution. The primarily interested here 798 ;: A coloring 7 assignment colors so no neighboring receive same color. special framework Potts model. ability spaces model leads better applications (see [1]). -coloring problem interest complexity Jerrum, Valiant, Vazirani [6] class includes efficient could used construct approximating space. Counting ?A@ -complete problem, making unlikely will found solve exactly. next section describe detail, after brief description CFTP, along 5 algorithm, run then uses both rejection briefly discuss extension methods general B upon previous (due Jerrum) $ C ED Finally longer due [2]. total variation distance quantify what mean sampling. If distributions F G put probability mass finite set, between H IJG KML 8 N O P  D These weaker Jerrum’s they require However, whereas only generates sample. Moreover, might finish before bounds given would indicate. rely must always take amount steps like ours, end samplers, does not depend * faster %(') *E Unlike method, however, random, ensure terminates at least I | necessary extra Note variation, usually smaller complete schedule. Since often many times (for example applications) even closely concentrated around consider here, there color Ž vertex : ‘ L example, graph, 7m8’  Some examples include hard core gas discussed 2.