Publication : t14/101
Perfect sampling algorithm for Schur processes
Betea D. (Laboratoire de Probabilités et Modèles Aléatoires, CNRS UMR 7599, Université Pierre et Marie Curie et Université Denis Diderot, 4 Place Jussieu, 75252 Paris Cedex 05, France)Boutillier C. (Laboratoire de Probabilités et Modèles Aléatoires, UMR 7599, Université Pierre et Marie Curie, 4 place Jussieu, F-75005 Paris)
Bouttier J. (CEA, IPhT (Institut de Physique Théorique), F-91191 Gif-sur-Yvette, France)
Chapuy G. (LIAFA, CNRS et Université Paris Diderot, Case 7014, F-75205 Paris Cedex 13)
Corteel S. (LIAFA, CNRS et Université Paris Diderot, Case 7014, F-75205 Paris Cedex 13)
Vuletić V. (Department of Mathematics, University of Massachusetts Boston, 100 William T. Morrissey Boulevard, Boston, MA 02125)
Abstract:Année de publication : 2018
We describe random generation algorithms for a large class of random combinatorial objects called Schur processes, which are sequences of random (integer) partitions subject to certain interlacing conditions. This class contains several fundamental combinatorial objects as special cases, such as plane partitions, tilings of Aztec diamonds, pyramid partitions and more generally steep domino tilings of the plane. Our algorithm, which is of polynomial complexity, is both exact (i.e. the output follows exactly the target probability law, which is either Boltzmann or uniform in our case), and entropy optimal (i.e. it reads a minimal number of random bits as an input). The algorithm encompasses previous growth procedures for special Schur processes related to the primal and dual RSK algorithm, as well as the famous domino shuffling algorithm for domino tilings of the Aztec diamond. It can be easily adapted to deal with symmetric Schur processes and general Schur processes involving infinitely many parameters. It is more concrete and easier to implement than Borodin's algorithm, and it is entropy optimal. At a technical level, it relies on unified bijective proofs of the different types of Cauchy and Littlewood identities for Schur functions, and on an adaptation of Fomin's growth diagram description of the RSK algorithm to that setting. Simulations performed with this algorithm suggest interesting limit shape phenomena for the corresponding tiling models, some of which are new.
Revue : Markov Proces. Relat. Fields 24 381-418 (2018)
Preprint : arXiv:1407.3764
Lien : http://math-mprf.org/journal/articles/id1508/
Keywords : Schur processes, Markov dynamics, interlaced partitions, perfect sampling, vertex operators
Langue : Anglais
Fichier(s) à télécharger :
sampling_paper_journal_MPRF.pdf publi.pdf
