Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-23T11:23:55.763Z Has data issue: false hasContentIssue false
  • English
  • Français

What Does a Random Contingency Table Look Like?

Published online by Cambridge University Press:  12 February 2010

ALEXANDER BARVINOK
ALEXANDER BARVINOK*
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1043, USA (e-mail: barvinok@umich.edu)
Get access Rights & Permissions [Opens in a new window]

Abstract

Let R = (r1, . . ., rm) and C = (c1, . . ., cn) be positive integer vectors such that r1 + ⋯ + rm = c1 + ⋯ + cn. We consider the set Σ(R, C) of non-negative m × n integer matrices (contingency tables) with row sums R and column sums C as a finite probability space with the uniform measure. We prove that a random table D ∈ Σ(R, C) is close with high probability to a particular matrix (‘typical table’) Z defined as follows. We let g(x) = (x + 1)ln(x + 1) − x ln x for x ≥ 0 and let g(X) = ∑i,jg(xij) for a non-negative matrix X = (xij). Then g(X) is strictly concave and attains its maximum on the polytope of non-negative m × n matrices X with row sums R and column sums C at a unique point, which we call the typical table Z.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 4 , July 2010 , pp. 517 - 539
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Barvinok, A. (2002) A Course in Convexity, Vol. 54 of Graduate Studies in Mathematics, AMS, Providence, RI.CrossRefGoogle Scholar
[2]Barvinok, A. (2009) On the number of matrices and a random matrix with prescribed row and column sums and 0–1 entries. Adv. Math., doi:10.1016/j.aim.2009.12.001.CrossRefGoogle Scholar
[3]Barvinok, A. (2009) Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes. Internat. Math. Research Notices 2009 348–385.CrossRefGoogle Scholar
[4]Barvinok, A. and Hartigan, J. A. (2009) Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes. Preprint arXiv:0903.5223. Adv. in Appl. Math., to appear.CrossRefGoogle Scholar
[5]Barvinok, A., Luria, Z., Samorodnitsky, A. and Yong, A. (2010) An approximation algorithm for counting contingency tables. Random Struct. Algorithms, doi:10.1002/rsa.20301.CrossRefGoogle Scholar
[6]Cryan, M., Dyer, M., Goldberg, L. A., Jerrum, M. and Martin, R. (2006) Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. SIAM J. Comput. 36 247–278.CrossRefGoogle Scholar
[7]Diaconis, P. and Efron, B. (1985) Testing for independence in a two-way table: New interpretations of the chi-square statistic. With discussions and with a reply by the authors. Ann. Statist. 13 845–913.Google Scholar
[8]Diaconis, P. and Gangolli, A. (1995) Rectangular arrays with fixed margins. In Discrete Probability and Algorithms: Minneapolis 1993, Vol. 72 of The IMA Volumes in Mathematics and its Applications, Springer, New York, pp. 15–41.CrossRefGoogle Scholar
[9]Dyer, M., Kannan, R. and Mount, J. (1997) Sampling contingency tables. Random Struct. Algorithms 10 487–506.3.0.CO;2-Q>CrossRefGoogle Scholar
[10]Good, I. J. (1963) Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables. Ann. Math. Statist. 34 911–934.CrossRefGoogle Scholar
[11]Greenhill, C. and McKay, B. D. (2008) Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums. Adv. Appl. Math. 41 459–481.CrossRefGoogle Scholar
[12]Ledoux, M. (2001) The Concentration of Measure Phenomenon, Vol. 89 of Mathematical Surveys and Monographs, AMS, Providence, RI.Google Scholar
[13]O'Neil, P. E. (1969) Asymptotics and random matrices with row-sum and column-sum restrictions. Bull. Amer. Math. Soc. 75 1276–1282.CrossRefGoogle Scholar
[14]Nesterov, Y. and Nemirovskii, A. (1994) Interior-Point Polynomial Algorithms in Convex Programming, Vol. 13 of SIAM Studies in Applied Mathematics, SIAM, Philadelphia, PA.CrossRefGoogle Scholar