| DATE: | Friday, May 16th |
| TIME: | 2:00 PM - 2:45 PM |
| PLACE: | McConnell 103 |
| TITLE: | Polynomial Time Perfect Sampling Algorithm for Two-rowed Contingency Tables |
| SPEAKER: | Shuji Kijima (University of Tokyo) |
We propose a polynomial time perfect (or exact) sampling algorithm for two rowed contingency tables. The algorithm is a Las Vegas type randomized algorithm and the expected running time is bounded by O(n^3 ln N) where n is the number of columns and N is the total sum of whole esnries in a table. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm and new Markov chain for sampling two-rowed contingency tables uniformly. This is work with Tomomi Matsui.
Reference:
S. Kijima and T. Matsui, Polynomial Time Perfect Sampling Algorithm
for Two-rowed Contingency Tables, METR 2003-15,
Mathematical Engineering Technical Reports, University of Tokyo, 2003.
(available from http://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html)