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
Additional Information
- Alexei Borodin
- Affiliation: Department of Mathematics, Caltech, Pasadena, California, 91125
- MR Author ID: 604024
- Persi Diaconis
- Affiliation: Departments of Mathematics and Statistics, Stanford, Palo Alto, California, 94305
- MR Author ID: 57595
- Jason Fulman
- Affiliation: Department of Mathematics, University of Southern California, Los Angeles, California, 90089
- MR Author ID: 332245
- Received by editor(s): May 1, 2009
- Published electronically: August 3, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Bull. Amer. Math. Soc. 47 (2010), 639-670
- MSC (2010): Primary 05E15, 60B15
- DOI: https://doi.org/10.1090/S0273-0979-2010-01306-9
- MathSciNet review: 2721041