An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums

Barvinok, Alexander; Hartigan, J.

doi:10.1090/S0002-9947-2012-05585-1

An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
HTML articles powered by AMS MathViewer

by Alexander Barvinok and J. A. Hartigan PDF

Trans. Amer. Math. Soc. 364 (2012), 4323-4368 Request permission

Abstract:

We count $m \times n$ non-negative integer matrices (contingency tables) with prescribed row and column sums (margins). For a wide class of smooth margins we establish a computationally efficient asymptotic formula approximating the number of matrices within a relative error which approaches 0 as $m$ and $n$ grow.

References

Keith Ball, An elementary introduction to modern convex geometry, Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 1–58. MR 1491097, DOI 10.2977/prims/1195164788
A. Barvinok, Computing mixed discriminants, mixed volumes, and permanents, Discrete Comput. Geom. 18 (1997), no. 2, 205–237. MR 1455515, DOI 10.1007/PL00009316
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, 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 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
A. Barvinok and J.A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures & Algorithms, to appear.
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
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, The asymptotic number of non-negative integer matrices with given row and column sums, Discrete Math. 10 (1974), 217–223. MR 389621, DOI 10.1016/0012-365X(74)90118-6
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
Yuguo Chen, Persi Diaconis, Susan P. Holmes, and Jun S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, J. Amer. Statist. Assoc. 100 (2005), no. 469, 109–120. MR 2156822, DOI 10.1198/016214504000001303
Mary Cryan and Martin Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, J. Comput. System Sci. 67 (2003), no. 2, 291–310. Special issue on STOC2002 (Montreal, QC). MR 2022833, DOI 10.1016/S0022-0000(03)00014-X
J.A. De Loera, Counting and estimating lattice points: tools from algebra, analysis, convexity, and probability, Optima 81(2009), 1–9.
J.A. De Loera, Appendix: details on experiments (counting and estimating lattice points), Optima 81(2009), 17–22.
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}
Javier Duoandikoetxea, Reverse Hölder inequalities for spherical harmonics, Proc. Amer. Math. Soc. 101 (1987), no. 3, 487–491. MR 908654, DOI 10.1090/S0002-9939-1987-0908654-1
Martin Dyer, Ravi Kannan, and John Mount, Sampling contingency tables, Random Structures Algorithms 10 (1997), no. 4, 487–506. MR 1608222, DOI 10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q
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
I. J. Good and J. F. Crook, The enumeration of arrays and a generalization related to contingency tables, Discrete Math. 19 (1977), no. 1, 23–45. MR 541011, DOI 10.1016/0012-365X(77)90117-0
Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347, DOI 10.1090/surv/089
Z. Luria, Counting contingency tables with balanced margins, manuscript, 2008.
Ben J. Morris, Improved bounds for sampling contingency tables, Random Structures Algorithms 21 (2002), no. 2, 135–146. MR 1917354, DOI 10.1002/rsa.10049
Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086, DOI 10.1137/1.9781611970791
V. Zipunnikov, J.G. Booth and R. Yoshida, Counting tables using the double saddlepoint approximation, Journal of Computational and Graphical Statistics 18 (2009), 915–929.
A. Zvonkin, Matrix integrals and map enumeration: an accessible introduction, Math. Comput. Modelling 26 (1997), no. 8-10, 281–304. Combinatorics and physics (Marseilles, 1995). MR 1492512, DOI 10.1016/S0895-7177(97)00210-0