Perfect sampling algorithms for Schur processes

MaRDI QIDQ5376432zbMATH OpenFDO

Authors Cédric Boutillier, Guillaume Chapuy, Mirjana Vuletić, Dan Betea, Bouttier, Sylvie Corteel

Publication date 17 September 2018

Full work available at URL https://arxiv.org/abs/1407.3764

zbMATH Keywords

interlaced partitionsMarkov dynamicsperfect samplingSchur processesvertex operators

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial aspects of representation theory (05E10) Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: 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.

Recommendations

• Schur dynamics of the Schur processes
• Random tilings and Markov chains for interlacing particles
• Generalized domino-shuffling.
• Random Sampling of Plane Partitions
• Generating random elements of finite distributive lattices

Cited in

(18)

• Shuffling algorithm for boxed plane partitions
• Asymptotics of random domino tilings of rectangular Aztec diamonds
• The free boundary Schur process and applications. I
• The periodic Schur process and free fermions at finite temperature
• Determinantal point processes from symplectic and orthogonal characters and applications
• Correlation functions of the Pfaffian Schur process using Macdonald difference operators
• New edge asymptotics of skew Young diagrams via free boundaries
• Muttalib-Borodin plane partitions and the hard edge of random matrix ensembles
• Random tilings with the GPU
• Yang-Baxter field for spin Hall-Littlewood symmetric functions
• Asymptotics of pure dimer coverings on rail yard graphs
• Multicritical Schur measures and higher-order analogues of the Tracy-Widom distribution
• Schur dynamics of the Schur processes
• Tilted biorthogonal ensembles, Grothendieck random partitions, and determinantal tests
• Fluctuations in the Aztec diamonds via a space-like maximal surface in Minkowski 3-space
• Local statistics and shuffling for dimers on a square-hexagon lattice
• Discrete and continuous Muttalib-Borodin processes: the hard edge
• A note on last passage percolation and Schur processes

This page was built for publication: Perfect sampling algorithms for Schur processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376432)