Mixing times of lozenge tiling and card shuffling Markov chains

Diaconis, P. (1988). <i>Group Representations in Probability and Statistics</i>. IMS, Hayward, CA.

Diaconis, P. and Saloff-Coste, L. (1996). Logarithmic Sobolev inequalities for finite Markov chains. <i>Ann. Appl. Probab.</i> <b>6</b> 695--750.

Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. <i>Z. Wahrsch. Verw. Gebiete</i> <b>57</b> 159--179.

Diaconis, P. and Shahshahani, M. (1987). Time to reach stationarity in the Bernoulli--Laplace diffusion model. <i>SIAM J. Math. Anal.</i> <b>18</b> 208--218.

Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. <i>Séminaire de Probabilités XVII</i>. <i>Lecture Notes in Mathematics</i> <b>986</b> 243--297. Springer, Berlin.

Aldous, D. (1997). Personal communication.

Aldous, D. and Diaconis, P. (1987). Strong uniform times and finite random walks. <i>Adv. in Appl. Math.</i> <b>8</b> 69--97.

Aldous, D. J. and Fill, J. A. (2004). Reversible Markov chains and random walks on graphs. Unpublished manuscript. Available at www.stat.berkeley.edu/~aldous/book.html.

Bayer, D. and Diaconis, P. (1992). Trailing the dovetail shuffle to its lair. <i>Ann. Appl. Probab.</i> <b>2</b> 294--313.

Blum, M. D. (1996). Unpublished notes.

Brightwell, G. and Winkler, P. (1991). Counting linear extensions. <i>Order</i> <b>8</b> 225--242.

Bubley, R. and Dyer, M. (1997). Path coupling: A technique for proving rapid mixing in Markov chains. In <i>Proceedings of the 38th Annual Symposium on Foundations of Computer Science</i> 223--231.

Bubley, R. and Dyer, M. (1998). Faster random generation of linear extensions. In <i>Proceedings of the Ninth Annual ACM--SIAM Symposium on Discrete Algorithms</i> 350--354.

Cancrini, N. and Martinelli, F. (2000). On the spectral gap of Kawasaki dynamics under a mixing condition revisited. <i>J. Math. Phys.</i> <b>41</b> 1391--1423.

Chen, M.-F. (1998). Trilogy of couplings and general formulas for lower bound of spectral gap. <i>Probability Towards 2000</i>. <i>Lecture Notes in Statist.</i> <b>128</b> 123--136. Springer, Berlin.

Ciucu, M. and Propp, J. (1996). Unpublished manuscript.

Cohn, H. (1995). Personal communication.

Cohn, H., Kenyon, R. and Propp, J. (2001). A variational principle for domino tilings. <i>J. Amer. Math. Soc.</i> <b>14</b> 297--346.

Cohn, H., Larsen, M. and Propp, J. (1998). The shape of a typical boxed plane partition. <i>New York J. Math.</i> <b>4</b> 137--165.

Destainville, N. (2002). Flip dynamics in octagonal rhombus tiling sets. <i>Phys. Rev. Lett.</i> <b>88</b> 30601.

Diaconis, P. (1996). The cutoff phenomenon in finite Markov chains. <i>Proc. Nat. Acad. Sci. U.S.A.</i> <b>93</b> 1659--1664.

Diaconis, P. (1997). Personal communication.

Diaconis, P., Fill, J. A. and Pitman, J. (1992). Analysis of top to random shuffles. <i>Combin. Probab. Comput.</i> <b>1</b> 135--155.

Diaconis, P., Graham, R. L. and Morrison, J. A. (1990). Asymptotic analysis of a random walk on a hypercube with many dimensions. <i>Random Structures Algorithms</i> <b>1</b> 51--72.

Diaconis, P. and Saloff-Coste, L. (1993a). Comparison techniques for random walk on finite groups. <i>Ann. Probab.</i> <b>21</b> 2131--2156.

Diaconis, P. and Saloff-Coste, L. (1993b). Comparison theorems for reversible Markov chains. <i>Ann. Appl. Probab.</i> <b>3</b> 696--730.

Dyer, M. and Frieze, A. (1991). Computing the volume of convex bodies: A case where randomness provably helps. In <i>Proceedings of the 44th Symposium in Applied Mathematics</i> 123--169.

Dyer, M., Frieze, A. and Kannan, R. (1991). A random polynomial-time algorithm for approximating the volume of convex bodies. <i>J. Assoc. Comput. Mach.</i> <b>38</b> 1--17.

Felsner, S. and Wernisch, L. (1997). Markov chains for linear extensions, the two-dimensional case. In <i>Proceedings of the Eighth Annual ACM--SIAM Symposium on Discrete Algorithms</i> 239--247.

Fill, J. A. (1998). An interruptible algorithm for perfect sampling via Markov chains. <i>Ann. Appl. Probab.</i> <b>8</b> 131--162.

Fisher, M. E. (1961). Statistical mechanics of dimers on a plane lattice. <i>Phys. Rev.</i> <b>124</b> 1664--1672.

Häggström, O. (2001). Personal communication.

Handjani, S. and Jungreis, D. (1996). Rate of convergence for shuffling cards by transpositions. <i>J. Theoret. Probab.</i> <b>9</b> 983--993.

Henley, C. L. (1997). Relaxation time for a dimer covering with height representation. <i>J. Statist. Phys.</i> <b>89</b> 483--507.

Hester, J. H. and Hirschberg, D. S. (1985). Self-organizing linear search. <i>Computing Surveys</i> <b>17</b> 295--311. Available at www.acm.org/pubs/contents/journals/surveys/.

Karzanov, A. and Khachiyan, L. (1991). On the conductance of order Markov chains. <i>Order</i> <b>8</b> 7--15.

Kasteleyn, P. W. (1963). Dimer statistics and phase transitions. <i>J. Math. Phys.</i> <b>4</b> 287--293.

Kenyon, R. W., Propp, J. G. and Wilson, D. B. (2000). Trees and matchings. <i>Electron. J. Combin.</i> <b>7</b> R25.

Lee, T.-Y. and Yau, H.-T. (1998). Logarithmic Sobolev inequality for some models of random walks. <i>Ann. Probab.</i> <b>26</b> 1855--1873.

Lu, S. and Yau, H.-T. (1993). Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics. <i>Comm. Math. Phys.</i> <b>156</b> 399--433.

Luby, M., Randall, D. and Sinclair, A. (1995). Markov chain algorithms for planar lattice structures. In <i>36th Annual Symposium on Foundations of Computer Science</i> 150--159. [Expanded version <i>SIAM J. Comput.</i> (2001) <b>31</b>.]

Mannila, H. and Meek, C. (2000). Global partial orders from sequential data. In <i>Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining</i> 161--168.

Matthews, P. (1991). Generating a random linear extension of a partial order. <i>Ann. Probab.</i> <b>19</b> 1367--1392.

Ng, L. L. (1996). Heisenberg model, Bethe <i>Ansatz</i>, and random walks. Bachelor's thesis, Harvard Univ.

Propp, J. G. (1995--1997). Personal communications.

Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. <i>Random Structures Algorithms</i> <b>9</b> 223--252.

Randall, D. (1998). Personal communication.

Randall, D. and Tetali, P. (2000). Analyzing Glauber dynamics by comparison of Markov chains. <i>J. Math. Phys.</i> <b>41</b> 1598--1615.

Wilson, D. B. (1997a). Determinant algorithms for random planar structures. In <i>Proceedings of the Eighth Annual ACM--SIAM Symposium on Discrete Algorithms</i> 258--267.

Wilson, D. B. (1997b). Random random walks on $\Z_2^d$. <i>Probab. Theory Related Fields</i> <b>108</b> 441--457.

Wilson, D. B. (2001). Diagonal sums of boxed plane partitions. <i>Electron. J. Combin.</i> <b>8</b> N1.