Shuffling algorithm for boxed plane partitions
- Creators
- Borodin, Alexei
- Gorin, Vadim
Abstract
We introduce discrete time Markov chains that preserve uniform measures on boxed plane partitions. Elementary Markov steps change the size of the box from a×b×c to (a−1)×(b+1)×c or (a+1)×(b−1)×c. Algorithmic realization of each step involves O((a+b)c) operations. One application is an efficient perfect random sampling algorithm for uniformly distributed boxed plane partitions. Trajectories of our Markov chains can be viewed as random point configurations in the three-dimensional lattice. We compute the bulk limits of the correlation functions of the resulting random point process on suitable two-dimensional sections. The limiting correlation functions define a two-dimensional determinantal point processes with certain Gibbs properties.
Additional Information
© 2008 Elsevier Inc. Received 20 May 2008; accepted 6 November 2008. Communicated by Andrei Zelevinsky; available online 10 December 2008. The first named author (A.B.) was partially supported by the NSF grant DMS-0707163. The second named author (V.G.) was partially supported by RFBR grant 07-01-91209, the Moebius Contest Foundation for Young Scientists and Leonhard Euler's Fund of Russian Mathematics Support.Attached Files
Submitted - 0804.3071.pdf
Files
Name | Size | Download all |
---|---|---|
md5:0eadd8e8aaad54d5e798528c1dc9cdad
|
1.0 MB | Preview Download |
Additional details
- Eprint ID
- 14106
- DOI
- 10.1016/j.aim.2008.11.008
- Resolver ID
- CaltechAUTHORS:20090428-165110014
- DMS-0707163
- NSF
- 07-01-91209
- Russian Foundation for Basic Research
- Moebius Contest Foundation for Young Scientists
- Leonhard Euler's Fund of Russian Mathematics Support
- Created
-
2009-08-10Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field