论文标题
对一类完美匹配问题的顺序重要性采样算法的理论分析
Theoretical Analysis of Sequential Importance Sampling Algorithms for a Class of Perfect Matching Problems
论文作者
论文摘要
本文分析了顺序重要性采样算法的性能，以估计两部分图中完美匹配的数量。得出准确的估计值所需的样品数量的精确界限。在此过程中，使用生成函数计算排列统计的力矩，而非标准限制定理是通过将完美的匹配作为时间均匀的马尔可夫链来得出的。
This paper analyzes the performance of sequential importance sampling algorithms for estimating the number of perfect matchings in bipartite graphs. Precise bounds on the number of samples required to yield an accurate estimate are derived. In doing so, moments of permutation statistics are computed using generating functions and nonstandard limit theorems are derived by expressing perfect matchings as a time-inhomogeneous Markov chain.
