Large deviations for non-crossing partitions

Janosch Ortmann (University of Warwick)


We prove a large deviations principle for the empirical law of the block sizes of a uniformly distributed non-crossing partition. Using well-known bijections we relate this to other combinatorial objects, including Dyck paths, permutations and parking functions. As an application we obtain a variational formula for the maximum of the support of a compactly supported probability measure in terms of its free cumulants, provided these are all non negative. This is useful in free probability theory, where sometimes the R-transform is known but cannot be inverted explicitly to yield the density.

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

Pages: 1-25

Publication Date: May 6, 2012

DOI: 10.1214/EJP.v17-2007


  • Arizmendi, O. Statistics of blocks in k-divisible non-crossing partitions. arXiv:1201.6576/ (2012).
  • Armstrong, D. Generalized Non-Crossing Partitions and Combinatorics of Coxeter Groups. PhD thesis, Cornell University, 2006.
  • Aval, Jean-Christophe. Multivariate Fuss-Catalan numbers. Discrete Math. 308 (2008), no. 20, 4660--4669. MR2438172
  • Banica, T.; Belinschi, S. T.; Capitaine, M.; Collins, B. Free Bessel laws. Canad. J. Math. 63 (2011), no. 1, 3--37. MR2779129
  • Barndorff-Nielsen, Ole E.; Thorbjørnsen, Steen. Lévy processes in free probability. Proc. Natl. Acad. Sci. USA 99 (2002), no. 26, 16576--16580. MR1947757
  • Barndorff-Nielsen, Ole E.; Thorbjørnsen, Steen. Self-decomposability and Lévy processes in free probability. Bernoulli 8 (2002), no. 3, 323--366. MR1913111
  • Bessis, David. The dual braid monoid. Ann. Sci. École Norm. Sup. (4) 36 (2003), no. 5, 647--683. MR2032983
  • Biane, Philippe. On the free convolution with a semi-circular distribution. Indiana Univ. Math. J. 46 (1997), no. 3, 705--718. MR1488333
  • Biane, Philippe. Some properties of crossings and partitions. Discrete Math. 175 (1997), no. 1-3, 41--53. MR1475837
  • Biane, P. Parking functions of types A and B. Electron. J. Combin. 9 (2002), no. 1, Note 7, 5 pp. (electronic). MR1912816
  • Biane, Philippe. Free probability for probabilists. Quantum probability communications, Vol. XI (Grenoble, 1998), 55--71, QP-PQ, XI, World Sci. Publ., River Edge, NJ, 2003. MR2032363
  • Bollobás, Béla. Linear analysis. An introductory course. Second edition. Cambridge University Press, Cambridge, 1999. xii+240 pp. ISBN: 0-521-65577-3 MR1711398
  • Brady, Thomas; Watt, Colum. Non-crossing partition lattices in finite real reflection groups. Trans. Amer. Math. Soc. 360 (2008), no. 4, 1983--2005. MR2366971
  • Callan, David. Sets, lists and noncrossing partitions. J. Integer Seq. 11 (2008), no. 1, Article 08.1.3, 7 pp. MR2377569
  • Dembo, Amir; Zajic, Tim. Large deviations: from empirical mean and measure to partial sums process. Stochastic Process. Appl. 57 (1995), no. 2, 191--224. MR1334969
  • Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036
  • Deuschel, Jean-Dominique; Stroock, Daniel W. Large deviations. Pure and Applied Mathematics, 137. Academic Press, Inc., Boston, MA, 1989. xiv+307 pp. ISBN: 0-12-213150-9 MR0997938
  • Deutsch, Emeric. Dyck path enumeration. Discrete Math. 204 (1999), no. 1-3, 167--202. MR1691869
  • Durrett, Richard. Probability. Theory and examples. The Wadsworth & Brooks/Cole Statistics/Probability Series. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. x+453 pp. ISBN: 0-534-13206-5 MR1068527
  • Edelman, Paul H. Chain enumeration and noncrossing partitions. Discrete Math. 31 (1980), no. 2, 171--180. MR0583216
  • Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete mathematics. A foundation for computer science. Second edition. Addison-Wesley Publishing Company, Reading, MA, 1994. xiv+657 pp. ISBN: 0-201-55802-5 MR1397498
  • Hiai, Fumio; Petz, Dénes. The semicircle law, free random variables and entropy. Mathematical Surveys and Monographs, 77. American Mathematical Society, Providence, RI, 2000. x+376 pp. ISBN: 0-8218-2081-8 MR1746976
  • Hinz, Melanie; Młotkowski, Wojciech. Free powers of the free Poisson measure. Colloq. Math. 123 (2011), no. 2, 285--290. MR2811179
  • Kreweras, G. Sur les partitions non croisées d'un cycle. (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747
  • Lynch, James; Sethuraman, Jayaram. Large deviations for processes with independent increments. Ann. Probab. 15 (1987), no. 2, 610--627. MR0885133
  • McCammond, Jon. Noncrossing partitions in surprising locations. Amer. Math. Monthly 113 (2006), no. 7, 598--610. MR2252931
  • Młotkowski, Wojciech. Fuss-Catalan numbers in noncommutative probability. Doc. Math. 15 (2010), 939--955. MR2745687
  • Nica, Alexandru; Speicher, Roland. Commutators of free random variables. Duke Math. J. 92 (1998), no. 3, 553--592. MR1620518
  • Nica, Alexandru; Speicher, Roland. Lectures on the combinatorics of free probability. London Mathematical Society Lecture Note Series, 335. Cambridge University Press, Cambridge, 2006. xvi+417 pp. ISBN: 978-0-521-85852-6; 0-521-85852-6 MR2266879
  • Ortmann, J. Functionals of the Free Brownian Bridge. arXiv:1107.0218.
  • Prodinger, Helmut. A correspondence between ordered trees and noncrossing partitions. Discrete Math. 46 (1983), no. 2, 205--206. MR0710893
  • Reiner, Victor. Non-crossing partitions for classical reflection groups. Discrete Math. 177 (1997), no. 1-3, 195--222. MR1483446
  • Schied, Alexander. Cramer's condition and Sanov's theorem. Statist. Probab. Lett. 39 (1998), no. 1, 55--60. MR1649347
  • Simion, Rodica. Noncrossing partitions. Formal power series and algebraic combinatorics (Vienna, 1997). Discrete Math. 217 (2000), no. 1-3, 367--409. MR1766277
  • Speicher, Roland. Multiplicative functions on the lattice of noncrossing partitions and free convolution. Math. Ann. 298 (1994), no. 4, 611--628. MR1268597
  • Stanley, Richard P. Parking functions and noncrossing partitions. The Wilf Festschrift (Philadelphia, PA, 1996). Electron. J. Combin. 4 (1997), no. 2, Research Paper 20, approx. 14 pp. (electronic). MR1444167
  • Stanley, Richard P. Enumerative combinatorics. Vol. 2. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999. xii+581 pp. ISBN: 0-521-56069-1; 0-521-78987-7 MR1676282
  • Voiculescu, D. V.; Dykema, K. J.; Nica, A. Free random variables. A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups. CRM Monograph Series, 1. American Mathematical Society, Providence, RI, 1992. vi+70 pp. ISBN: 0-8218-6999-X MR1217253
  • Yano, Fujine; Yoshida, Hiroaki. Some set partition statistics in non-crossing partitions and generating functions. Discrete Math. 307 (2007), no. 24, 3147--3160. MR2370117

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