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
doi:10.1017/S0963548310000039

Paper

What Does a Random Contingency Table Look Like?


ALEXANDER BARVINOKa1

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

Abstract

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)

Footnotes

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