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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6850(online) ISSN 0002-9947(print)

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

Authors: Alexander Barvinok and J. A. Hartigan
Journal: Trans. Amer. Math. Soc. 364 (2012), 4323-4368
MSC (2010): Primary 05A16, 52B55, 52C07, 60F05
Posted: March 20, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 and grow.

1. 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 (99f:52002)
2. A. Barvinok, Computing mixed discriminants, mixed volumes, and permanents, Discrete Comput. Geom. 18 (1997), no. 2, 205–237. MR 1455515 (98m:52011), http://dx.doi.org/10.1007/PL00009316
3. 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 (2010c:52019), http://dx.doi.org/10.1093/imrn/rnn133
4. Alexander Barvinok, What does a random contingency table look like?, Combin. Probab. Comput. 19 (2010), no. 4, 517–539. MR 2647491 (2011g:62157), http://dx.doi.org/10.1017/S0963548310000039
5. 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 (2011d:52026), http://dx.doi.org/10.1016/j.aam.2010.01.004
6. A. Barvinok and J.A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures & Algorithms, to appear.
7. 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 (2011j:68174), http://dx.doi.org/10.1002/rsa.20301
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 0335342 (49 #124)
9. Edward A. Bender, The asymptotic number of non-negative integer matrices with given row and column sums, Discrete Math. 10 (1974), 217–223. MR 0389621 (52 #10452)
10. 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 (2012b:05029), http://dx.doi.org/10.1007/s00493-010-2426-1
11. 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 (2006f:62062), http://dx.doi.org/10.1198/016214504000001303
12. 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 (2005h:68177), http://dx.doi.org/10.1016/S0022-0000(03)00014-X
13. J.A. De Loera, Counting and estimating lattice points: tools from algebra, analysis, convexity, and probability, Optima 81(2009), 1-9.
14. J.A. De Loera, Appendix: details on experiments (counting and estimating lattice points), Optima 81(2009), 17-22.
15. 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 (87c:62106), http://dx.doi.org/10.1214/aos/1176349634
16. 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 (97e:05013), http://dx.doi.org/10.1007/978-1-4612-0801-3_3
17. Javier Duoandikoetxea, Reverse Hölder inequalities for spherical harmonics, Proc. Amer. Math. Soc. 101 (1987), no. 3, 487–491. MR 908654 (88m:42040), http://dx.doi.org/10.1090/S0002-9939-1987-0908654-1
18. Martin Dyer, Ravi Kannan, and John Mount, Sampling contingency tables, Random Structures Algorithms 10 (1997), no. 4, 487–506. MR 1608222 (98i:68124), http://dx.doi.org/10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q
19. 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 (2009i:05021), http://dx.doi.org/10.1016/j.aam.2008.01.002
20. 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 0541011 (58 #27527)
21. Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347 (2003k:28019)
22. Z. Luria, Counting contingency tables with balanced margins, manuscript, 2008.
23. Ben J. Morris, Improved bounds for sampling contingency tables, Random Structures Algorithms 21 (2002), no. 2, 135–146. MR 1917354 (2003d:62141), http://dx.doi.org/10.1002/rsa.10049
24. 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 (94m:90005)
25. 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.
26. 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 (98m:81037), http://dx.doi.org/10.1016/S0895-7177(97)00210-0

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|