Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
share
We introduce novel randomized sequential importance sampling algorithms for estimating the number of perfect matchings in bipartite graphs. In analyzing their performance, we prove various non-standard central limit theorems, via limit theory for random variables satisfying distributional recurrence relations of divide-and-conquer type. We expect that our methods will be useful for other applied problems, such as counting and testing for contingency tables or graphs with given degree sequence.
READ FULL TEXT