×

zbMATH — the first resource for mathematics

On adding a list of numbers (and other one-dependent determinantal processes). (English) Zbl 1230.05292
Summary: 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.

MSC:
05E15 Combinatorial aspects of groups and algebras (MSC2010)
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
Keywords:
random digits
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165 – 219. · Zbl 0613.15014 · doi:10.1016/0024-3795(87)90313-2 · doi.org
[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. · Zbl 0850.62008
[3] 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. · Zbl 1092.05071 · doi:10.1016/j.aim.2005.05.014 · doi.org
[4] 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). · Zbl 1186.60066 · doi:10.1214/07-AIHP115 · doi.org
[5] Borodin, A., Determinantal point processes, arXiv:0911.1153 (2009), to appear in Oxford Handbook of Random Matrix Theory. · Zbl 1238.60055
[6] Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481 – 515. · Zbl 0938.05061
[7] 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. · Zbl 1127.82017 · doi:10.1007/s10955-005-7583-z · doi.org
[8] 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. · Zbl 1136.60015 · doi:10.1216/rmjm/1181069318 · doi.org
[9] Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. · Zbl 0697.05011 · doi:10.1090/memo/0413 · doi.org
[10] Erik I. Broman, One-dependent trigonometric determinantal processes are two-block-factors, Ann. Probab. 33 (2005), no. 2, 601 – 609. · Zbl 1067.60010 · doi:10.1214/009117904000000595 · doi.org
[11] 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. · Zbl 0785.60007
[12] Chebikin, D., Polytopes, generating functions, and new statistics related to descents and inversions in permutations, Ph.D. thesis, Department of Mathematics, MIT, 2008. · Zbl 1179.05004
[13] Louis H. Y. Chen and Qi-Man Shao, Normal approximation under local dependence, Ann. Probab. 32 (2004), no. 3A, 1985 – 2028. · Zbl 1048.60020 · doi:10.1214/009117904000000450 · doi.org
[14] 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.
[15] Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. · Zbl 0283.05001
[16] Douglas E. Critchlow, Metric methods for analyzing partially ranked data, Lecture Notes in Statistics, vol. 34, Springer-Verlag, Berlin, 1985. · Zbl 0589.62041
[17] Ann Cutler and Rudolph McShane, The Trachtenberg speed system of basic mathematics, Doubleday& Co., Inc., Garden City, N.Y., 1960.
[18] D. J. Daley and D. Vere-Jones, An introduction to the theory of point processes, Springer Series in Statistics, Springer-Verlag, New York, 1988. · Zbl 0657.60069
[19] 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. · Zbl 0847.60015 · doi:10.1007/978-1-4612-0719-1_3 · doi.org
[20] 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. · Zbl 0695.60012
[21] Persi Diaconis and Jason Fulman, Carries, shuffling, and symmetric functions, Adv. in Appl. Math. 43 (2009), no. 2, 176 – 196. · Zbl 1172.60002 · doi:10.1016/j.aam.2009.02.002 · doi.org
[22] 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. · Zbl 0789.05091 · doi:10.1090/conm/138/1199122 · doi.org
[23] Persi Diaconis, Michael McGrath, and Jim Pitman, Riffle shuffles, cycles, and descents, Combinatorica 15 (1995), no. 1, 11 – 29. · Zbl 0828.05003 · doi:10.1007/BF01294457 · doi.org
[24] 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. · Zbl 0998.60069 · doi:10.1307/mmj/1030132713 · doi.org
[25] 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. · Zbl 0267.05002
[26] Freeman J. Dyson, Statistical theory of the energy levels of complex systems. I, J. Mathematical Phys. 3 (1962), 140 – 156. · Zbl 0105.41604 · doi:10.1063/1.1703773 · doi.org
[27] Freeman J. Dyson, Statistical theory of the energy levels of complex systems. II, J. Mathematical Phys. 3 (1962), 157 – 165. · Zbl 0105.41604 · doi:10.1063/1.1703774 · doi.org
[28] Freeman J. Dyson, Statistical theory of the energy levels of complex systems. III, J. Mathematical Phys. 3 (1962), 166 – 175. · Zbl 0105.41604 · doi:10.1063/1.1703775 · doi.org
[29] Albert Edrei, Proof of a conjecture of Schoenberg on the generating function of a totally positive sequence, Canadian J. Math. 5 (1953), 86 – 94. · Zbl 0053.23704
[30] 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. · Zbl 1241.62076 · doi:10.1287/ijoc.1040.0105 · doi.org
[31] William Feller, An introduction to probability theory and its applications. Vol. II., Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971. · Zbl 0077.12201
[32] Michael A. Fligner and Joseph S. Verducci , 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. · Zbl 0754.00011
[33] 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., Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 27 – 49 (French). With a comment by Richard P. Stanley.
[34] H. O. Foulkes, Enumeration of permutations with prescribed up-down and inversion sequences, Discrete Math. 15 (1976), no. 3, 235 – 252. · Zbl 0338.05002 · doi:10.1016/0012-365X(76)90028-5 · doi.org
[35] 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. · Zbl 0962.13009
[36] Jason Fulman, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, J. Algebraic Combin. 16 (2002), no. 2, 165 – 194. · Zbl 1012.05154 · doi:10.1023/A:1021177012548 · doi.org
[37] A. M. Garsia and C. Reutenauer, A decomposition of Solomon’s descent algebra, Adv. Math. 77 (1989), no. 2, 189 – 262. · Zbl 0716.20006 · doi:10.1016/0001-8708(89)90020-0 · doi.org
[38] 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. · Zbl 0793.05004 · doi:10.1016/0097-3165(93)90095-P · doi.org
[39] Ira Gessel and Gérard Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), no. 3, 300 – 321. · Zbl 0579.05004 · doi:10.1016/0001-8708(85)90121-5 · doi.org
[40] 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. · Zbl 0836.00001
[41] L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967), 410 – 414. · Zbl 0154.43703 · doi:10.1214/aoms/1177698956 · doi.org
[42] Wassily Hoeffding and Herbert Robbins, The central limit theorem for dependent random variables, Duke Math. J. 15 (1948), 773 – 780. · Zbl 0031.36701
[43] J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206 – 229. · Zbl 1189.60101 · doi:10.1214/154957806000000078 · doi.org
[44] 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. · Zbl 1190.60038
[45] Daniel C. Isaksen, A cohomological viewpoint on elementary school arithmetic, Amer. Math. Monthly 109 (2002), no. 9, 796 – 805. · Zbl 1026.20029 · doi:10.2307/3072368 · doi.org
[46] Svante Janson, Some pairwise independent sequences for which the central limit theorem fails, Stochastics 23 (1988), no. 4, 439 – 448. · Zbl 0645.60027 · doi:10.1080/17442508808833503 · doi.org
[47] Johansson, K., Random matrices and determinantal processes, Mathematical Statistical Physics, 1-55, Elsevier B. V., Amsterdam 2006. · Zbl 1411.60144
[48] Kurt Johansson and Eric Nordenstam, Eigenvalues of GUE minors, Electron. J. Probab. 11 (2006), no. 50, 1342 – 1371. , https://doi.org/10.1214/EJP.v11-370 Kurt Johansson and Eric Nordenstam, Erratum to: ”Eigenvalues of GUE minors” [Electron. J. Probab. 11 (2006), no. 50, 1342 – 1371; MR2268547], Electron. J. Probab. 12 (2007), 1048 – 1051. · Zbl 1134.60344 · doi:10.1214/EJP.v12-816 · doi.org
[49] Richard Kenyon, Lectures on dimers, Statistical mechanics, IAS/Park City Math. Ser., vol. 16, Amer. Math. Soc., Providence, RI, 2009, pp. 191 – 230. · Zbl 1180.82001
[50] Alain Lascoux and Piotr Pragacz, Ribbon Schur functions, European J. Combin. 9 (1988), no. 6, 561 – 574. · Zbl 0681.05001 · doi:10.1016/S0195-6698(88)80053-2 · doi.org
[51] Russell Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167 – 212. · Zbl 1055.60003 · doi:10.1007/s10240-003-0016-0 · doi.org
[52] Russell Lyons and Jeffrey E. Steif, Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120 (2003), no. 3, 515 – 575. · Zbl 1068.82010 · doi:10.1215/S0012-7094-03-12032-3 · doi.org
[53] Odile Macchi, The coincidence approach to stochastic point processes, Advances in Appl. Probability 7 (1975), 83 – 122. · Zbl 0366.60081 · doi:10.2307/1425855 · doi.org
[54] 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. · Zbl 0899.05068
[55] 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). · Zbl 1144.05300
[56] C. L. Mallows, Non-null ranking models. I, Biometrika 44 (1957), 114 – 130. · Zbl 0087.34001 · doi:10.1093/biomet/44.1-2.114 · doi.org
[57] John I. Marden, Analyzing and modeling rank data, Monographs on Statistics and Applied Probability, vol. 64, Chapman & Hall, London, 1995. · Zbl 0853.62006
[58] Madan Lal Mehta, Random matrices, 3rd ed., Pure and Applied Mathematics (Amsterdam), vol. 142, Elsevier/Academic Press, Amsterdam, 2004. · Zbl 1107.15019
[59] 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. · Zbl 1099.60037 · doi:10.1007/BF02392515 · doi.org
[60] Jim Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), no. 2, 279 – 303. · Zbl 0866.60016 · doi:10.1006/jcta.1997.2747 · doi.org
[61] Alexander Polishchuk and Leonid Positselski, Quadratic algebras, University Lecture Series, vol. 37, American Mathematical Society, Providence, RI, 2005. · Zbl 1145.16009
[62] Victor Reiner, Signed permutation statistics, European J. Combin. 14 (1993), no. 6, 553 – 567. · Zbl 0793.05005 · doi:10.1006/eujc.1993.1058 · doi.org
[63] Victor Reiner, Kristin M. Shaw, and Stephanie van Willigenburg, Coincidences among skew Schur functions, Adv. Math. 216 (2007), no. 1, 118 – 152. · Zbl 1128.05051 · doi:10.1016/j.aim.2007.05.006 · doi.org
[64] 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. · Zbl 0798.17001
[65] 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. · Zbl 1051.60052 · doi:10.1016/S0022-1236(03)00171-X · doi.org
[66] 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. · Zbl 1051.60053 · doi:10.1214/aop/1055425789 · doi.org
[67] Louis Solomon, A Mackey formula in the group ring of a Coxeter group, J. Algebra 41 (1976), no. 2, 255 – 264. · Zbl 0355.20007 · doi:10.1016/0021-8693(76)90182-4 · doi.org
[68] 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. · Zbl 0991.60038 · doi:10.1070/rm2000v055n05ABEH000321 · doi.org
[69] Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 336 – 356. · Zbl 0331.05004
[70] 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. · Zbl 0889.05001
[71] 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. · Zbl 0928.05001
[72] Stanley, R. P., Eulerian partitions of a unit hypercube, in: Higher Combinatorics, M. Aigner, editor, page 47. Reidel, Dordrecht/Boston, 1977. · Zbl 0359.05001
[73] 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). · Zbl 1010.05078 · doi:10.1007/s00026-001-8023-7 · doi.org
[74] Richard P. Stanley, The descent set and connectivity set of a permutation, J. Integer Seq. 8 (2005), no. 3, Article 05.3.8, 9. · Zbl 1101.05002
[75] John R. Stembridge, Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge, Trans. Amer. Math. Soc. 359 (2007), no. 3, 1115 – 1128. · Zbl 1110.06009
[76] 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. · Zbl 0834.60036
[77] Herbert S. Wilf, Algorithms and complexity, 2nd ed., A K Peters, Ltd., Natick, MA, 2002. · Zbl 1008.68057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.