Algorithms for counting/sampling Cell-Bounded Contingency Tables

February 25, 2009

This is a survey talk about counting/sampling contingency
tables and cell-bounded contingency tables. In the
cell-bounded contingency tables problem, we are given a list
of positive integer row sums $r=(r_1, ..., r_m)$, a list of
positive integer column sums $c=(c_1, ..., c_n)$, and a
non-negative integer bound $b_{i,j}$, for every $1 \leq i \leq m$,
$1 \leq j \leq n$.

The problem is to count/sample the set of all $m$-by-$n$ tables $X \in Z^{mn}$ of non-negative integers which satisfy the given row and column sums, and for which $0 \leq X_{ij} \leq b_{ij}$ for all $i,j$. I will outline both a complicated (reduction to volume estimation) and a simple (dynamic programming) algorithm for approximately counting these tables in polynomial time, when the number of row is constant. The case for general m is still open.

The problem is to count/sample the set of all $m$-by-$n$ tables $X \in Z^{mn}$ of non-negative integers which satisfy the given row and column sums, and for which $0 \leq X_{ij} \leq b_{ij}$ for all $i,j$. I will outline both a complicated (reduction to volume estimation) and a simple (dynamic programming) algorithm for approximately counting these tables in polynomial time, when the number of row is constant. The case for general m is still open.