Phase transition in random contingency tables with non-uniform margins
HTML articles powered by AMS MathViewer
- by Samuel Dittmer, Hanbaek Lyu and Igor Pak PDF
- Trans. Amer. Math. Soc. 373 (2020), 8313-8338 Request permission
Abstract:
For parameters $n,\delta ,B,$ and $C$, let $X=(X_{k\ell })$ be the random uniform contingency table whose first $\lfloor n^{\delta } \rfloor$ rows and columns have margin $\lfloor BCn \rfloor$ and the last $n$ rows and columns have margin $\lfloor Cn \rfloor$. For every $0<\delta <1$, we establish a sharp phase transition of the limiting distribution of each entry of $X$ at the critical value $B_{c}=1+\sqrt {1+1/C}$. In particular, for $1/2<\delta <1$, we show that the distribution of each entry converges to a geometric distribution in total variation distance whose mean depends sensitively on whether $B<B_{c}$ or $B>B_{c}$. Our main result shows that $\mathbb {E}[X_{11}]$ is uniformly bounded for $B<B_{c}$ but has sharp asymptotic $C(B-B_{c}) n^{1-\delta }$ for $B>B_{c}$. We also establish a strong law of large numbers for the row sums in top right and top left blocks.References
- Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
- Alexander Barvinok, Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes, Int. Math. Res. Not. IMRN 2 (2009), 348–385. MR 2482118, DOI 10.1093/imrn/rnn133
- Alexander Barvinok, On the number of matrices and a random matrix with prescribed row and column sums and 0–1 entries, Adv. Math. 224 (2010), no. 1, 316–339. MR 2600999, DOI 10.1016/j.aim.2009.12.001
- Alexander Barvinok, What does a random contingency table look like?, Combin. Probab. Comput. 19 (2010), no. 4, 517–539. MR 2647491, DOI 10.1017/S0963548310000039
- Alexander Barvinok, Matrices with prescribed row and column sums, Linear Algebra Appl. 436 (2012), no. 4, 820–844. MR 2890890, DOI 10.1016/j.laa.2010.11.019
- Alexander Barvinok and J. A. Hartigan, Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes, Adv. in Appl. Math. 45 (2010), no. 2, 252–289. MR 2646125, DOI 10.1016/j.aam.2010.01.004
- Alexander Barvinok and J. A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures Algorithms 42 (2013), no. 3, 301–348. MR 3039682, DOI 10.1002/rsa.20409
- Alexander Barvinok, Zur Luria, Alex Samorodnitsky, and Alexander Yong, An approximation algorithm for counting contingency tables, Random Structures Algorithms 37 (2010), no. 1, 25–66. MR 2674620, DOI 10.1002/rsa.20301
- Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom. 30 (2003), no. 4, 623–637. MR 2013976, DOI 10.1007/s00454-003-2850-8
- A. Békéssy, P. Békéssy, and J. Komlós, Asymptotic enumeration of regular matrices, Studia Sci. Math. Hungar. 7 (1972), 343–353. MR 335342
- Edward A. Bender and E. Rodney Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 296–307. MR 505796, DOI 10.1016/0097-3165(78)90059-6
- Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
- E. Rodney Canfield and Brendan D. McKay, The asymptotic volume of the Birkhoff polytope, Online J. Anal. Comb. 4 (2009), 4. MR 2575172
- E. Rodney Canfield and Brendan D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, Combinatorica 30 (2010), no. 6, 655–680. MR 2789732, DOI 10.1007/s00493-010-2426-1
- S. Chatterjee, P. Diaconis, and A. Sly, Properties of uniform doubly stochastic matrices, preprint, 18 pp., arXiv:1010.6136, 2010.
- Ben Cousins and Santosh Vempala, A practical volume algorithm, Math. Program. Comput. 8 (2016), no. 2, 133–160. MR 3503293, DOI 10.1007/s12532-015-0097-z
- Jesús A. De Loera and Edward D. Kim, Combinatorics and geometry of transportation polytopes: an update, Discrete geometry and algebraic combinatorics, Contemp. Math., vol. 625, Amer. Math. Soc., Providence, RI, 2014, pp. 37–76. MR 3289405, DOI 10.1090/conm/625/12491
- Persi Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659–1664. MR 1374011, DOI 10.1073/pnas.93.4.1659
- Persi Diaconis and Bradley Efron, Testing for independence in a two-way table: new interpretations of the chi-square statistic, Ann. Statist. 13 (1985), no. 3, 845–913. With discussions and with a reply by the authors. MR 803747, DOI 10.1214/aos/1176349634
- Persi Diaconis and Anil Gangolli, Rectangular arrays with fixed margins, Discrete probability and algorithms (Minneapolis, MN, 1993) IMA Vol. Math. Appl., vol. 72, Springer, New York, 1995, pp. 15–41. MR 1380519, DOI 10.1007/978-1-4612-0801-3_{3}
- Persi Diaconis and Bernd Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), no. 1, 363–397. MR 1608156, DOI 10.1214/aos/1030563990
- S. Dittmer and I. Pak, Random sampling and approximate counting of sparse contingency tables, submitted (2018).
- S. Dittmer, H. Lyu, and I. Pak, Contingency tables have empirical bias, in preparation (2019).
- B. S. Everitt, The analysis of contingency tables, 2nd ed., Monographs on Statistics and Applied Probability, vol. 45, Chapman & Hall, London, 1992. MR 1214789
- Morten W. Fagerland, Stian Lydersen, and Petter Laake, Statistical analysis of contingency tables, CRC Press, Boca Raton, FL, 2017. MR 3753657
- I. J. Good, Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables, Ann. Math. Statist. 34 (1963), 911–934. MR 150880, DOI 10.1214/aoms/1177704014
- Catherine Greenhill and Brendan D. McKay, Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums, Adv. in Appl. Math. 41 (2008), no. 4, 459–481. MR 2459445, DOI 10.1016/j.aam.2008.01.002
- Maria Kateri, Contingency table analysis, Statistics for Industry and Technology, Birkhäuser/Springer, New York, 2014. Methods and implementation using R. MR 3290014, DOI 10.1007/978-0-8176-4811-4
- Igor Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (2000), no. 1, 83–90. MR 1763951, DOI 10.1007/PL00001277
- Nicholas Wormald, Asymptotic enumeration of graphs with given degree sequence, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3245–3264. MR 3966531
- J. M. Yeomans, Statistical Mechanics of Phase Transitions, Oxford Univ. Press, 1992.
Additional Information
- Samuel Dittmer
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
- MR Author ID: 1057891
- Email: samuel.dittmer@math.ucla.edu
- Hanbaek Lyu
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
- Email: hlyu@math.ucla.edu
- Igor Pak
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
- MR Author ID: 293184
- ORCID: 0000-0001-8579-7239
- Email: pak@math.ucla.edu
- Received by editor(s): April 11, 2019
- Received by editor(s) in revised form: July 16, 2019, and August 15, 2019
- Published electronically: October 5, 2020
- Additional Notes: The third author was partially supported by the NSF
- © Copyright 2020 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 373 (2020), 8313-8338
- MSC (2010): Primary 54C40, 14E20; Secondary 46E25, 20C20
- DOI: https://doi.org/10.1090/tran/8094
- MathSciNet review: 4177260