|
Published Articles >> Table of Contents >> Abstract
41st Annual Symposium on Foundations of Computer Science
p. 492
Sampling adsorbing staircase walks using a new Markov chain decomposition method
R.A. Martin, Sch. of Math., Georgia Inst. of Technol., Atlanta, GA, USA
D. Randall, Sch. of Math., Georgia Inst. of Technol., Atlanta, GA, USA
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2000.892137
Send link to a friend
| Abstract |
|
Staircase walks are lattice paths from (0,0) to (2n,0) which take diagonal steps and which never fall below the x-axis. A path hitting the x-axis /spl kappa/ times is assigned a weight of /spl lambda//sup /spl kappa//, where /spl lambda/<0. A simple local Markov chain, which connects the state space and converges to the Gibbs measure (which normalizes these weights) is known to be rapidly mixing when /spl lambda/=1, and can easily be shown to be rapidly mixing when /spl lambda/>1. We give the first proof that this Markov chain is also mixing in the more interesting case of /spl lambda/<1, known in the statistical physics community as adsorbing staircase walks. The main new ingredient is a decomposition technique which allows us to analyze the Markov chain in pieces, applying different arguments to analyze each piece.
|
 Additional Information
|
Index Terms- Markov processes; theorem proving; lambda calculus; adsorbing staircase walks; Markov chain decomposition method; lattice paths; diagonal steps; local Markov chain; state space; /spl lambda//sup /spl kappa//; Gibbs measure; first proof; Markov chain; statistical physics community; decomposition technique
Citation:
R.A. Martin, D. Randall,
"Sampling adsorbing staircase walks using a new Markov chain decomposition method,"
focs,
p. 492,
41st Annual Symposium on Foundations of Computer Science,
2000
|
|
