A Markov Chain Sampler for Plane Curves

Abstract

A plane curve is a knot diagram in which each crossing is replaced by a 4-valent vertex, and so are dual to a subset of planar quadrangulations. The aim of this article is to introduce a new tool for sampling diagrams via sampling of plane curves. At present the most efficient method for sampling diagrams is rejection sampling, however that method is inefficient at even modest sizes. We introduce Markov chains that sample from the space of plane curves using local moves based on Reidemeister moves. By then mapping vertices on those curves to crossings we produce random knot diagrams. Combining this chain with flat histogram methods we achieve an efficient sampler of plane curves and knot diagrams. By analyzing data from this chain we are able to estimate the number of knot diagrams of a given size and also compute knotting probabilities and so investigate their asymptotic behavior.

Keywords:

• Planar maps
• Markov chain
• flat histogram
• asymptotics
• random knots

Acknowledgments

The authors would like to thank the Pacific Institute of Mathematics Sciences for funding the collaborative research group (CRG) on Applied Combinatorics. Part of this work started at a summer school on applied combinatorics funded by that CRG. The second author acknowledges funding from NSERC in the form of a Discovery Grant. The authors would also like to thank Chris Soteros, Jason Cantarella, and Stu Whittington for many helpful discussions. We would also like to thank the anonymous referee whose suggestions improved the quality of the data, results, and exposition of this article.

Declaration of Interest

No potential conflict of interest was reported by the authors.

Additional information

Funding

Natural Sciences and Engineering Research Council of Canada.