Fast sampling of sparse contingency tables

Series: 
Combinatorics Seminar
Friday, January 18, 2019 - 3:05pm
1 hour (actually 50 minutes)
Location: 
Skiles 169 (*Unusual room*)
,  
Mathematics, UCLA
,  
Organizer: 
We present a new algorithm for sampling contingency tables with fixed margins. This algorithm runs in polynomial time for certain broad classes of sparse tables. We compare the performance of our algorithm theoretically and experimentally to existing methods, including the Diaconis-Gangolli Markov chain and sequential importance sampling. Joint work with Igor Pak.