Sampling biased lattice configurations using exponential metrics

ABSTRACT

Monotonic surfaces spanning finite regions of Z^d arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. We explore how we can sample these surfaces when the distribution is biased to favor higher surfaces. We show that a natural local chain is rapidly mixing with any bias for regions in Z², and for bias λ > d² in Z^d, when d > 2. Moreover, our bounds on the mixing time are optimal on d-dimensional hyper-cubic regions. The proof uses a geometric distance function and introduces a variant of path coupling in order to handle distances that are exponentially large.

REFERENCES

• 1: L. Adleman, Q. Cheng, A. Goel, M. D. Huang and H. Wasserman. Linear self-assemblies: Equilibria, entropies and convergence rates. 6th International Conference on Difference Equations and Applications, 2001.
• 2: D. Aldous. Random walks on finite groups and rapidly mixing Markov chains. Séminaire de Probabilités XVII, Springer Lecture Notes in Mathematics 986:243--297, 1981/82.
• 3: I. Benjamini, N. Berger, C. Hoffman and E. Mossel. Mixing times of the biased card shuffling and the asymmetric exclusion process. Transactions of the American Mathematics Society 357: 3013--3029, 2005.
• 4: Russ Bubley , Martin Dyer, Faster random generation of linear extensions, Discrete Mathematics, v.201 n.1-3, p.81-88, April 28, 1999 [doi>10.1016/S0012-365X(98)00333-1]
• 5: M. Cook, P. Gacs and E. Winfree. Self-stabilizing synchronization in 3 dimensions. Preprint, 2008.
• 6: R. Durrett. Probability: Theory and Examples, 2ed. Duxbury, 1996.
• 7: Martin Dyer , Catherine Greenhill, A more rapidly mixing Markov chain for graph colorings, Random Structures & Algorithms, v.13 n.3-4, p.285-317, Oct., 1998
• 8: T.-J. Fu and N. C. Seeman. DNA double-crossover molecules. Biochemistry, 32: 3211--3220, 1993.
• 9: D. Galvin, J. Kahn, D. Randall and G. Sorkin. In preparation, 2008.
• 10: David Galvin , Dana Randall, Torpid mixing of local Markov chains on 3-colorings of the discrete torus, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.376-384, January 07-09, 2007, New Orleans, Louisiana
• 11: Michael Luby , Dana Randall , Alistair Sinclair, Markov Chain Algorithms for Planar Lattice Structures, SIAM Journal on Computing, v.31 n.1, p.167-192, 2001 [doi>10.1137/S0097539799360355]
• 12: U. Majumder, S. Sahu and J. Reif. Stochastic analysis of reversible self-assembly. To appear in the Journal of Computational and Theoretical Nanoscience, 2008.
• 13: N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics 21: 1087--1092, 1953.
• 14: J. Linde, C. Moore and M. Nordahl. An n-Dimensional Generalization of the Rhombus Tiling. Discrete Mathematics and Theoretical Computer Science Proceedings AA, 23--42, 2001.
• 15: D. Randall and P. Tetali. Analyzing glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41: 1598--1615, 2000.
• 16: J. H. Reif, S. Sahu and P. Yin Compact Error-Resilient Computational DNA Tiling Assemblies. 10th International Meeting on DNA Computing, 293--307, 2004
• 17: N. C. Seeman. DNA in a material world. Nature, 421: 427--431, 2003.
• 18: D. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. The Annals of Applied Probability, 1: 274--325, 2004.
• 19: E. Winfree. Simulations of Computing by Self-Assembly. 4th DIMACS Meeting on DNA Based Computers, University of Pennsylvania, 1998.
• 20: E. Winfree, X. Yang and N. C. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In DNA Based Computers II, L. F. Landweber and E. B. Baum, editors, DIMACS series 44: 191--213, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General