On the Shuffling Algorithm for Domino Tilings

Eric J. G. Nordenstam (Swedish Royal Institute of Technology (KTH))

Abstract


We study the dynamics of a certain discrete model of interacting interlaced particles that comes from the so called shuffling algorithm for sampling a random tiling of an Aztec diamond. It turns out that the transition probabilities have a particularly convenient determinantal form. An analogous formula in a continuous setting has recently been obtained by Jon Warren studying certain model of interlacing Brownian motions which can be used to construct Dyson's non-intersecting Brownian motion. We conjecture that Warren's model can be recovered as a scaling limit of our discrete model and prove some partial results in this direction. As an application to one of these results we use it to rederive the known result that random tilings of an Aztec diamond, suitably rescaled near a turning point, converge to the GUE minor process.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 75-95

Publication Date: January 12, 2010

DOI: 10.1214/EJP.v15-730

References

  1. Borodin, Alexei; Ferrari, Patrik L. Large time asymptotics of growth models on space-like paths. I. PushASEP. Electron. J. Probab. 13 (2008), no. 50, 1380--1418. MR2438811 (2009d:82104)
  2. Borodin, Alexei; Gorin, Vadim. Shuffling algorithm for boxed plane partitions. Adv. Math. 220 (2009), no. 6, 1739--1770. MR2493180 (Review)
  3. Billingsley, Patrick. Convergence of probability measures. Second edition. Wiley Series in Probability and Statistics: Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. x+277 pp. ISBN: 0-471-19745-9 MR1700749 (2000e:60008)
  4. Dieker, A. B.; Warren, J. Determinantal transition kernels for some interacting particles on the line. Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), no. 6, 1162--1172. MR2469339 (2010a:60236)
  5. Eichelsbacher, Peter; König, Wolfgang. Ordered random walks. Electron. J. Probab. 13 (2008), no. 46, 1307--1336. MR2430709 (Review)
  6. Elkies, Noam; Kuperberg, Greg; Larsen, Michael; Propp, James. Alternating-sign matrices and domino tilings. II. J. Algebraic Combin. 1 (1992), no. 3, 219--234. MR1194076 (94f:52036)
  7. Johansson, Kurt; Nordenstam, Eric. Eigenvalues of GUE minors. Electron. J. Probab. 11 (2006), no. 50, 1342--1371 (electronic). MR2268547 (2008d:60066a)
  8. Johansson, Kurt. Discrete orthogonal polynomial ensembles and the Plancherel measure. Ann. of Math. (2) 153 (2001), no. 1, 259--296. MR1826414 (2002g:05188)
  9. Johansson, Kurt. The arctic circle boundary and the Airy process. Ann. Probab. 33 (2005), no. 1, 1--30. MR2118857 (2005k:60304)
  10. Johansson, Kurt. A multi-dimenstional Markov chain and the Meixner ensemble. arXiv:0707.0098
  11. König, Wolfgang; O'Connell, Neil; Roch, Sébastien. Non-colliding random walks, tandem queues, and discrete orthogonal polynomial ensembles. Electron. J. Probab. 7 (2002), no. 5, 24 pp. (electronic). MR1887625 (2003e:60174)
  12. Krattenthaler, C. Advanced determinant calculus. The Andrews Festschrift (Maratea, 1998). Sém. Lothar. Combin. 42 (1999), Art. B42q, 67 pp. (electronic). MR1701596 (2002i:05013)
  13. Okounkov, Andrei; Reshetikhin, Nicolai. The birth of a random matrix. Mosc. Math. J. 6 (2006), no. 3, 553--566. MR2274865 (2008h:60195)
  14. Propp, James. Generalized domino-shuffling. Tilings of the plane. Theoret. Comput. Sci. 303 (2003), no. 2-3, 267--301. MR1990768 (2004j:05038)
  15. Warren, Jon. Dyson's Brownian motions, intertwining and interlacing. Electron. J. Probab. 12 (2007), no. 19, 573--590 (electronic). MR2299928 (2008f:60088)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.