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

## Additional Information

**Alexander Barvinok**- Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1043
- MR Author ID: 237145
- Email: barvinok@umich.edu
**J. A. Hartigan**- Affiliation: Department of Statistics, Yale University, New Haven, Connecticut 06520-8290
- Email: john.hartigan@yale.edu
- Received by editor(s): April 5, 2010
- Received by editor(s) in revised form: March 11, 2011, and March 18, 2011
- Published electronically: March 20, 2012
- Additional Notes: The research of the first author was partially supported by NSF Grant DMS 0856640 and a United States–Israel BSF grant 2006377.
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**364**(2012), 4323-4368 - MSC (2010): Primary 05A16, 52B55, 52C07, 60F05
- DOI: https://doi.org/10.1090/S0002-9947-2012-05585-1
- MathSciNet review: 2912457