## 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