skip to main content
10.5555/1496770.1496779guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Sampling biased lattice configurations using exponential metrics

Published: 04 January 2009 Publication History

Abstract

Monotonic surfaces spanning finite regions of Zd 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 Z2, and for bias λ > d2 in Zd, 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]
R. Bubley and M. Dyer. Faster random generation of linear extensions. Discrete Math., 201:81--88, 1999.
[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]
M. Dyer and C. Greenhill. A more rapidly mixing Markov chain for graph colorings. Random Structures and Algorithms, 13:285--317, 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]
D. Galvin and D. Randall. Torpid mixing of local Markov chains on 3-colorings of the discrete torus. 17th Symposium on Discrete Algorithms (SODA), 376--384, 2007.
[11]
M. Luby, D. Randall, and A. J. Sinclair. Markov chains for planar lattice structures. SIAM Journal on Computing, 31: 167--192, 2001.
[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.

Cited By

View all
  • (2019)Mixing of Permutations by Biased TranspositionsTheory of Computing Systems10.1007/s00224-018-9899-563:5(1068-1088)Online publication date: 1-Jul-2019
  • (2017)Approximately sampling elements with fixed rank in graded posetsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039805(1828-1838)Online publication date: 16-Jan-2017
  • (2015)Phase transitions in random dyadic tilings and rectangular dissectionsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722233(1573-1589)Online publication date: 4-Jan-2015
  • Show More Cited By

Index Terms

  1. Sampling biased lattice configurations using exponential metrics

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
    January 2009
    1297 pages

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    Published: 04 January 2009

    Qualifiers

    • Research-article

    Acceptance Rates

    Overall Acceptance Rate 411 of 1,322 submissions, 31%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)41
    • Downloads (Last 6 weeks)10
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Mixing of Permutations by Biased TranspositionsTheory of Computing Systems10.1007/s00224-018-9899-563:5(1068-1088)Online publication date: 1-Jul-2019
    • (2017)Approximately sampling elements with fixed rank in graded posetsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039805(1828-1838)Online publication date: 16-Jan-2017
    • (2015)Phase transitions in random dyadic tilings and rectangular dissectionsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722233(1573-1589)Online publication date: 4-Jan-2015
    • (2014)Clustering and mixing times for segregation models on Z2Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634098(327-340)Online publication date: 5-Jan-2014
    • (2013)Mixing times of Markov chains for self-organizing lists and biased permutationsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627818(1-15)Online publication date: 6-Jan-2013
    • (2013)Random lattice triangulationsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488685(615-624)Online publication date: 1-Jun-2013

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media