Title
Disjoint Decomposition of Markov Chains and Sampling Circuits in Cayley Graphs
Abstract
Markov chain decomposition is a tool for analysing the convergence rate of a complicated Markov chain by studying its behaviour on smaller, more manageable pieces of the state space. Roughly speaking, if a Markov chain converges quickly to equilibrium when restricted to subsets of the state space, and if there is sufficient ergodic flow between the pieces, then the original Markov chain also must converge rapidly to equilibrium. We present a new version of the decomposition theorem where the pieces partition the state space, rather than forming a cover where pieces overlap, as was previously required. This new formulation is more natural and better suited to many applications. We apply this disjoint decomposition method to demonstrate the efficiency of simple Markov chains designed to uniformly sample circuits of a given length on certain Cayley graphs. The proofs further indicate that a Markov chain for sampling adsorbing staircase walks, a problem arising in statistical physics, is also rapidly mixing.
Year
DOI
Venue
2006
10.1017/S0963548305007352
Combinatorics, Probability & Computing
Keywords
Field
DocType
markov chain decomposition,disjoint decomposition,simple markov chain,decomposition theorem,disjoint decomposition method,new version,complicated markov chain,new formulation,original markov chain,sampling circuits,state space,markov chains,cayley graphs,markov chain,cayley graph
Discrete mathematics,Markov chain mixing time,Combinatorics,Markov process,Markov property,Markov chain,Variable-order Markov model,Markov kernel,Mathematics,Absorbing Markov chain,Examples of Markov chains
Journal
Volume
Issue
ISSN
15
3
0963-5483
Citations 
PageRank 
References 
5
0.61
9
Authors
2
Name
Order
Citations
PageRank
Russell Martin118017.35
Dana Randall2298.15