Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T15:09:27.347Z Has data issue: false hasContentIssue false
  • English
  • Français

Sampling biased monotonic surfaces using exponential metrics

Published online by Cambridge University Press:  30 June 2020

Sam Greenberg ,
Dana Randall  and
Amanda Pascoe Streib
Sam Greenberg
Affiliation:
Department of Defense, Arlington, VA, USA
Dana Randall
Affiliation:
School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA
Amanda Pascoe Streib*
Affiliation:
Center for Computing Sciences, Bowie, MD 20715, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Monotonic surfaces spanning finite regions of ℤd arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. One method that has been used to uniformly generate these surfaces is a Markov chain that iteratively adds or removes a single cube below the surface during a step. We consider a biased version of the chain, where we are more likely to add a cube than to remove it, thereby favouring surfaces that are ‘higher’ or have more cubes below it. We prove that the chain is rapidly mixing for any uniform bias in ℤ2 and for bias λ > d in ℤd when d > 2. In ℤ2 we match the optimal mixing time achieved by Benjamini, Berger, Hoffman and Mossel in the context of biased card shuffling [2], but using much simpler arguments. The proofs use a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile. We show that the chain continues to be rapidly mixing if the biases are close to uniform, but that the chain can converge exponentially slowly in the general setting.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 5 , September 2020 , pp. 672 - 697
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

A preliminary version of this paper appeared in Proceedings of the 20th ACM–SIAM Symposium on Discrete Algorithms (2009), pp. 76–85.

‡

Supported in part by NSF grants CCF-1526900, CCF-1637031 and CCF-1733812.

References

Aldous, D. (1983) Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilités XVII, Vol. 986 of Lecture Notes in Mathematics, Springer, pp. 243–297.CrossRefGoogle Scholar
Benjamini, I., Berger, N., Hoffman, C. and Mossel, E. (2005) Mixing times of the biased card shuffling and the asymmetric exclusion process. Trans. Amer. Math. Soc. 357 3013–3029.CrossRefGoogle Scholar
Berger, N., Kenyon, C., Mossel, E. and Peres, Y. (2005) Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields 131 311–340.CrossRefGoogle Scholar
Bhakta, P., Miracle, S., Streib, A. and Randall, D. (2014) Mixing times of self-organizing lists and biased permutations. In 25th ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 1–15.Google Scholar
Bubley, R. and Dyer, M. (1999) Faster random generation of linear extensions. Discrete Math. 201 81–88.CrossRefGoogle Scholar
Cannon, S., Miracle, S. and Randall, D. (2015) Phase transitions in random dyadic tilings and rectangular dissections. In 26th ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 1573–1589.CrossRefGoogle Scholar
Caputo, P., Martinelli, F., Sinclair, A. and Stauffer, A. (2015) Dynamics of lattice triangulations on thin rectangles. In ACM Symposium on Theory of Computing (STOC).CrossRefGoogle Scholar
Caputo, P., Martinelli, F. and Toninelli, F. (2012) Mixing times of monotone surfaces and SOS interfaces: A mean curvature approach. Commun. Math. Phys. 311 157–189.CrossRefGoogle Scholar
Dyer, M. and Greenhill, C. (1998) A more rapidly mixing Markov chain for graph colorings. Random Struct. Alg. 13 285–317.3.0.CO;2-R>CrossRefGoogle Scholar
Fu, T.-J. and Seeman, N. (1993) DNA double-crossover molecules. Biochemistry 32 3211–3220.CrossRefGoogle ScholarPubMed
Jerrum, M. and Sinclair, A. (1989) Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. Comput. 82 93–133.Google Scholar
Levin, D. and Peres, Y. (2016) Mixing of the exclusion process with small bias. J. Statist. Phys. 165 1035–1050.CrossRefGoogle Scholar
Luby, M., Randall, D. and Sinclair, A. (2001) Markov chains for planar lattice structures. SIAM J. Comput. 31 167–192.CrossRefGoogle Scholar
Majumder, U., Sahu, S. and Reif, J. (2008) Stochastic analysis of reversible self-assembly. J. Comput. Theoret. Nanosci. 5 1289–1305.CrossRefGoogle Scholar
McShine, L. and Tetali, P. (1998) On the mixing time of the triangulation walk and other Catalan structures. In Randomization Methods in Algorithm Design, Vol. 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 147–160.CrossRefGoogle Scholar
Randall, D. and Tetali, P. (2000) Analyzing Glauber dynamics by comparison of Markov chains. J. Math. Phys. 41 1598–1615.CrossRefGoogle Scholar
Seeman, N. (2003) DNA in a material world. Nature 421 427–431.CrossRefGoogle Scholar
Wilson, D. (2004) Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 1 274–325.CrossRefGoogle Scholar
Winfree, E. (1998) Simulations of computing by self-assembly. In 4th DIMACS Meeting on DNA Based Computers.Google Scholar
Winfree, E., Yang, X. and Seeman, N. (1996) Universal computation via self-assembly of DNA: Some theory and experiments. In DNA Based Computers II, Vol. 44 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 191–213.Google Scholar