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)

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer(at)cs(dot)mcgill(dot)ca.

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html