On adding a list of numbers (and other one-dependent determinantal processes)

Borodin, Alexei; Diaconis, Persi; Fulman, Jason

doi:10.1090/S0273-0979-2010-01306-9

On adding a list of numbers (and other one-dependent determinantal processes)
HTML articles powered by AMS MathViewer

by Alexei Borodin, Persi Diaconis and Jason Fulman PDF

Bull. Amer. Math. Soc. 47 (2010), 639-670 Request permission

Abstract:

Adding a column of numbers produces “carries” along the way. We show that random digits produce a pattern of carries with a neat probabilistic description: the carries form a one-dependent determinantal point process. This makes it easy to answer natural questions: How many carries are typical? Where are they located? We show that many further examples, from combinatorics, algebra and group theory, have essentially the same neat formulae, and that any one-dependent point process on the integers is determinantal. The examples give a gentle introduction to the emerging fields of one-dependent and determinantal point processes.

References

T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165–219. MR 884118, DOI 10.1016/0024-3795(87)90313-2
Barry C. Arnold, N. Balakrishnan, and H. N. Nagaraja, A first course in order statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1992. A Wiley-Interscience Publication. MR 1178934
Louis J. Billera, Hugh Thomas, and Stephanie van Willigenburg, Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions, Adv. Math. 204 (2006), no. 1, 204–240. MR 2233132, DOI 10.1016/j.aim.2005.05.014
Alexei Borodin, Loop-free Markov chains as determinantal point processes, Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), no. 1, 19–28 (English, with English and French summaries). MR 2451569, DOI 10.1214/07-AIHP115
Borodin, A., Determinantal point processes, arXiv:0911.1153 (2009), to appear in Oxford Handbook of Random Matrix Theory.
Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481–515. MR 1758751, DOI 10.1090/S0894-0347-00-00337-4
Alexei Borodin and Eric M. Rains, Eynard-Mehta theorem, Schur process, and their Pfaffian analogs, J. Stat. Phys. 121 (2005), no. 3-4, 291–317. MR 2185331, DOI 10.1007/s10955-005-7583-z
Richard C. Bradley, On a stationary, triple-wise independent, absolutely regular counterexample to the central limit theorem, Rocky Mountain J. Math. 37 (2007), no. 1, 25–44. MR 2316436, DOI 10.1216/rmjm/1181069318
Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. MR 963833, DOI 10.1090/memo/0413
Erik I. Broman, One-dependent trigonometric determinantal processes are two-block-factors, Ann. Probab. 33 (2005), no. 2, 601–609. MR 2123203, DOI 10.1214/009117904000000595
Robert Burton and Robin Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab. 21 (1993), no. 3, 1329–1371. MR 1235419
Chebikin, D., Polytopes, generating functions, and new statistics related to descents and inversions in permutations, Ph.D. thesis, Department of Mathematics, MIT, 2008.
Louis H. Y. Chen and Qi-Man Shao, Normal approximation under local dependence, Ann. Probab. 32 (2004), no. 3A, 1985–2028. MR 2073183, DOI 10.1214/009117904000000450
Cifarelli, D. M. and Fortini, S., A short note on one-dependent trigonometric determinantal probability measures. Technical report, Istituto di Metodi Quantitativi, Università Bocconi, 2005.
Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
Douglas E. Critchlow, Metric methods for analyzing partially ranked data, Lecture Notes in Statistics, vol. 34, Springer-Verlag, Berlin, 1985. MR 818986, DOI 10.1007/978-1-4612-1106-8
Ann Cutler and Rudolph McShane, The Trachtenberg speed system of basic mathematics, Doubleday & Co., Inc., Garden City, N.Y., 1960. MR 0117137
D. J. Daley and D. Vere-Jones, An introduction to the theory of point processes, Springer Series in Statistics, Springer-Verlag, New York, 1988. MR 950166
Amir Dembo and Yosef Rinott, Some examples of normal approximations by Stein’s method, Random discrete structures (Minneapolis, MN, 1993) IMA Vol. Math. Appl., vol. 76, Springer, New York, 1996, pp. 25–44. MR 1395606, DOI 10.1007/978-1-4612-0719-1_{3}
Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
Persi Diaconis and Jason Fulman, Carries, shuffling, and symmetric functions, Adv. in Appl. Math. 43 (2009), no. 2, 176–196. MR 2531920, DOI 10.1016/j.aam.2009.02.002
Persi Diaconis and Phil Hanlon, Eigen-analysis for some examples of the Metropolis algorithm, Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991) Contemp. Math., vol. 138, Amer. Math. Soc., Providence, RI, 1992, pp. 99–117. MR 1199122, DOI 10.1090/conm/138/1199122
Persi Diaconis, Michael McGrath, and Jim Pitman, Riffle shuffles, cycles, and descents, Combinatorica 15 (1995), no. 1, 11–29. MR 1325269, DOI 10.1007/BF01294457
Persi Diaconis and Arun Ram, Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques, Michigan Math. J. 48 (2000), 157–190. Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786485, DOI 10.1307/mmj/1030132713
Peter Doubilet, Gian-Carlo Rota, and Richard Stanley, On the foundations of combinatorial theory. VI. The idea of generating function, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 267–318. MR 0403987
Freeman J. Dyson, Statistical theory of the energy levels of complex systems. I, J. Mathematical Phys. 3 (1962), 140–156. MR 143556, DOI 10.1063/1.1703773
Freeman J. Dyson, Statistical theory of the energy levels of complex systems. II, J. Mathematical Phys. 3 (1962), 157–165. MR 143557, DOI 10.1063/1.1703774
Freeman J. Dyson, Statistical theory of the energy levels of complex systems. III, J. Mathematical Phys. 3 (1962), 166–175. MR 143558, DOI 10.1063/1.1703775
Albert Edrei, Proof of a conjecture of Schoenberg on the generating function of a totally positive sequence, Canad. J. Math. 5 (1953), 86–94. MR 53176, DOI 10.4153/cjm-1953-010-3
Diane L. Evans, Lawrence M. Leemis, and John H. Drew, The distribution of order statistics for discrete random variables with applications to bootstrapping, INFORMS J. Comput. 18 (2006), no. 1, 19–30. MR 2205744, DOI 10.1287/ijoc.1040.0105
William Feller, An introduction to probability theory and its applications. Vol. II. , 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
Michael A. Fligner and Joseph S. Verducci (eds.), Probability models and statistical analyses for ranking data, Lecture Notes in Statistics, vol. 80, Springer-Verlag, New York, 1993. Papers from the conference held at the University of Massachusetts, Amherst, Massachusetts, June 8–13, 1990. MR 1237197, DOI 10.1007/978-1-4612-2738-0
Dominique Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 27–49 (French). With a comment by Richard P. Stanley. MR 519777
H. O. Foulkes, Enumeration of permutations with prescribed up-down and inversion sequences, Discrete Math. 15 (1976), no. 3, 235–252. MR 406809, DOI 10.1016/0012-365X(76)90028-5
R. Fröberg, Koszul algebras, Advances in commutative ring theory (Fez, 1997) Lecture Notes in Pure and Appl. Math., vol. 205, Dekker, New York, 1999, pp. 337–350. MR 1767430
Jason Fulman, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, J. Algebraic Combin. 16 (2002), no. 2, 165–194. MR 1943587, DOI 10.1023/A:1021177012548
A. M. Garsia and C. Reutenauer, A decomposition of Solomon’s descent algebra, Adv. Math. 77 (1989), no. 2, 189–262. MR 1020585, DOI 10.1016/0001-8708(89)90020-0
Ira M. Gessel and Christophe Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), no. 2, 189–215. MR 1245159, DOI 10.1016/0097-3165(93)90095-P
Ira Gessel and Gérard Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), no. 3, 300–321. MR 815360, DOI 10.1016/0001-8708(85)90121-5
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967), 410–414. MR 211432, DOI 10.1214/aoms/1177698956
Wassily Hoeffding and Herbert Robbins, The central limit theorem for dependent random variables, Duke Math. J. 15 (1948), 773–780. MR 26771
J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206–229. MR 2216966, DOI 10.1214/154957806000000078
J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Zeros of Gaussian analytic functions and determinantal point processes, University Lecture Series, vol. 51, American Mathematical Society, Providence, RI, 2009. MR 2552864, DOI 10.1090/ulect/051
Daniel C. Isaksen, A cohomological viewpoint on elementary school arithmetic, Amer. Math. Monthly 109 (2002), no. 9, 796–805. MR 1933702, DOI 10.2307/3072368
Svante Janson, Some pairwise independent sequences for which the central limit theorem fails, Stochastics 23 (1988), no. 4, 439–448. MR 943814, DOI 10.1080/17442508808833503
Johansson, K., Random matrices and determinantal processes, Mathematical Statistical Physics, 1–55, Elsevier B. V., Amsterdam 2006.
Kurt Johansson and Eric Nordenstam, Eigenvalues of GUE minors, Electron. J. Probab. 11 (2006), no. 50, 1342–1371. MR 2268547, DOI 10.1214/EJP.v11-370
Richard Kenyon, Lectures on dimers, Statistical mechanics, IAS/Park City Math. Ser., vol. 16, Amer. Math. Soc., Providence, RI, 2009, pp. 191–230. MR 2523460, DOI 10.1090/pcms/016/04
Alain Lascoux and Piotr Pragacz, Ribbon Schur functions, European J. Combin. 9 (1988), no. 6, 561–574. MR 970392, DOI 10.1016/S0195-6698(88)80053-2
Russell Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167–212. MR 2031202, DOI 10.1007/s10240-003-0016-0
Russell Lyons and Jeffrey E. Steif, Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120 (2003), no. 3, 515–575. MR 2030095, DOI 10.1215/S0012-7094-03-12032-3
Odile Macchi, The coincidence approach to stochastic point processes, Advances in Appl. Probability 7 (1975), 83–122. MR 380979, DOI 10.2307/1425855
I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
Percy A. MacMahon, Combinatory analysis. Vol. I, II (bound in one volume), Dover Phoenix Editions, Dover Publications, Inc., Mineola, NY, 2004. Reprint of An introduction to combinatory analysis (1920) and Combinatory analysis. Vol. I, II (1915, 1916). MR 2417935
C. L. Mallows, Non-null ranking models. I, Biometrika 44 (1957), 114–130. MR 87267, DOI 10.1093/biomet/44.1-2.114
John I. Marden, Analyzing and modeling rank data, Monographs on Statistics and Applied Probability, vol. 64, Chapman & Hall, London, 1995. MR 1346107
Madan Lal Mehta, Random matrices, 3rd ed., Pure and Applied Mathematics (Amsterdam), vol. 142, Elsevier/Academic Press, Amsterdam, 2004. MR 2129906
Yuval Peres and Bálint Virág, Zeros of the i.i.d. Gaussian power series: a conformally invariant determinantal process, Acta Math. 194 (2005), no. 1, 1–35. MR 2231337, DOI 10.1007/BF02392515
Jim Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), no. 2, 279–303. MR 1429082, DOI 10.1006/jcta.1997.2747
Alexander Polishchuk and Leonid Positselski, Quadratic algebras, University Lecture Series, vol. 37, American Mathematical Society, Providence, RI, 2005. MR 2177131, DOI 10.1090/ulect/037
Victor Reiner, Signed permutation statistics, European J. Combin. 14 (1993), no. 6, 553–567. MR 1248063, DOI 10.1006/eujc.1993.1058
Victor Reiner, Kristin M. Shaw, and Stephanie van Willigenburg, Coincidences among skew Schur functions, Adv. Math. 216 (2007), no. 1, 118–152. MR 2353252, DOI 10.1016/j.aim.2007.05.006
Christophe Reutenauer, Free Lie algebras, London Mathematical Society Monographs. New Series, vol. 7, The Clarendon Press, Oxford University Press, New York, 1993. Oxford Science Publications. MR 1231799
Tomoyuki Shirai and Yoichiro Takahashi, Random point fields associated with certain Fredholm determinants. I. Fermion, Poisson and boson point processes, J. Funct. Anal. 205 (2003), no. 2, 414–463. MR 2018415, DOI 10.1016/S0022-1236(03)00171-X
Tomoyuki Shirai and Yoichiro Takahashi, Random point fields associated with certain Fredholm determinants. II. Fermion shifts and their ergodic and Gibbs properties, Ann. Probab. 31 (2003), no. 3, 1533–1564. MR 1989442, DOI 10.1214/aop/1055425789
Louis Solomon, A Mackey formula in the group ring of a Coxeter group, J. Algebra 41 (1976), no. 2, 255–264. MR 444756, DOI 10.1016/0021-8693(76)90182-4
A. Soshnikov, Determinantal random point fields, Uspekhi Mat. Nauk 55 (2000), no. 5(335), 107–160 (Russian, with Russian summary); English transl., Russian Math. Surveys 55 (2000), no. 5, 923–975. MR 1799012, DOI 10.1070/rm2000v055n05ABEH000321
Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 336–356. MR 409206, DOI 10.1016/0097-3165(76)90028-5
Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
Stanley, R. P., Eulerian partitions of a unit hypercube, in: Higher Combinatorics, M. Aigner, editor, page 47. Reidel, Dordrecht/Boston, 1977.
Richard P. Stanley, Generalized riffle shuffles and quasisymmetric functions, Ann. Comb. 5 (2001), no. 3-4, 479–491. Dedicated to the memory of Gian-Carlo Rota (Tianjin, 1999). MR 1897637, DOI 10.1007/s00026-001-8023-7
Richard P. Stanley, The descent set and connectivity set of a permutation, J. Integer Seq. 8 (2005), no. 3, Article 05.3.8, 9. MR 2167418
John R. Stembridge, Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge, Trans. Amer. Math. Soc. 359 (2007), no. 3, 1115–1128. MR 2262844, DOI 10.1090/S0002-9947-06-04271-1
V. de Valk, One-dependent processes: two-block factors and non-two-block factors, CWI Tract, vol. 85, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1994. MR 1269540
Herbert S. Wilf, Algorithms and complexity, 2nd ed., A K Peters, Ltd., Natick, MA, 2002. MR 1942991, DOI 10.1201/b10621