Combinatorics, Probability and Computing

Cambridge Journals Online - CUP Full-Text Page
Combinatorics, Probability and Computing (2010), 19:517-539 Cambridge University Press
Copyright © Cambridge University Press 2010


What Does a Random Contingency Table Look Like?


a1 Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1043, USA (e-mail:
Article author query
barvinok a [Google Scholar]


Let R = (r1, . . ., rm) and C = (c1, . . ., cn) be positive integer vectors such that r1 + xs22EF + rm = c1 + xs22EF + 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 xs2208 Σ(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.

(Received September 01 2008)

(Revised December 10 2009)

(Online publication February 12 2010)


Partially supported by NSF grants DMS 0400617 and DMS 0856640, and US–Israel BSF grant 2006377.