|DATE:||Friday, May 16th|
|TIME:||2:00 PM - 2:45 PM|
|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.
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)