EPISODE · Apr 21, 2009 · 1H 1M
Counting & Sampling Contingency Tables
from Hamilton Institute Seminars (HD / large) · host Hamilton Institute
Speaker: Dr. M. Cryan Abstract: Suppose we are given two lists r and c of positive integers, where r=(r[1],...., r[m]) represents a list of prescribed row sums and c=(c[1], ..., c[n]) is a list of prescribed column sums. We require that (r[1] + ... + r[m]) =(c[1] + ... + c[n]). In this setting, we say that a m-by-n matrix X of non-negative integers is a Contingency Table (for these given row/column values) if X simultaneously satisfies all of the given row and column sums. The problem of determining whether at least one contingency table exists can be solved in polynomial-time (in fact, this question is fairly trivial). In my talk, we are interested in the more-difficult problem of randomly sampling a table uniformly at random, from the entire set of contingency tables. This problem has some applications in practical statistics which I will mention. We study a very natural Markov chain on the set of contingency tables called the 2-by-2 heat bath: one step of this chain operates by selecting 2 rows and 2 columns uniformly at random, computing the induced row sums and column sums on this 2-by-2 window, then replacing the window with a table chosen randomly from all 2-by-2 tables with the induced row and column sums. This Markov chain converges to the uniform distribution on contingency tables - our goal is to show that it approaches uniformity within polynomial-time. We are able to achieve this result for the case when the number of rows m is some fixed constant. Our proof is by application of the canonical paths method of Jerrum and Sinclair. (Joint work with Martin Dyer, Leslie Goldberg, Mark Jerrum and Russell Martin)
What this episode covers
Speaker: Dr. M. Cryan Abstract: Suppose we are given two lists r and c of positive integers, where r=(r[1],...., r[m]) represents a list of prescribed row sums and c=(c[1], ..., c[n]) is a list of prescribed column sums. We require that (r[1] + ... + r[m]) =(c[1] + ... + c[n]). In this setting, we say that a m-by-n matrix X of non-negative integers is a Contingency Table (for these given row/column values) if X simultaneously satisfies all of the given row and column sums. The problem of determining whether at least one contingency table exists can be solved in polynomial-time (in fact, this question is fairly trivial). In my talk, we are interested in the more-difficult problem of randomly sampling a table uniformly at random, from the entire set of contingency tables. This problem has some applications in practical statistics which I will mention. We study a very natural Markov chain on the set of contingency tables called the 2-by-2 heat bath: one step of this chain operates by selecting 2 rows and 2 columns uniformly at random, computing the induced row sums and column sums on this 2-by-2 window, then replacing the window with a table chosen randomly from all 2-by-2 tables with the induced row and column sums. This Markov chain converges to the uniform distribution on contingency tables - our goal is to show that it approaches uniformity within polynomial-time. We are able to achieve this result for the case when the number of rows m is some fixed constant. Our proof is by application of the canonical paths method of Jerrum and Sinclair. (Joint work with Martin Dyer, Leslie Goldberg, Mark Jerrum and Russell Martin)
NOW PLAYING
Counting & Sampling Contingency Tables
No transcript for this episode yet
Similar Episodes
May 31, 2026 ·25m
May 31, 2026 ·30m
May 31, 2026 ·57m
May 31, 2026 ·32m
May 31, 2026 ·29m
May 31, 2026 ·37m