Sequential importance sampling for estimating expectations over the space of perfect matchings

DOI10.1214/22-AAP1834MaRDI QIDQ6103989zbMATH OpenOpenAlexFDO

Authors Persi Diaconis, Mohammad Roghani, Amin Saberi

Publication date 5 June 2023

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.00850

zbMATH Keywords

card guessing experimentdense bipartite graphKL-divergenceLatin squaresperfect matchingsequential importance samplingstochastic block model

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial probability (60C05) Sampling theory, sample surveys (62D05) Monte Carlo methods (65C05)

Abstract: This paper makes three contributions to estimating the number of perfect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm works in polynomial time for dense bipartite graphs. More carefully, our algorithm gives a $(1pmepsilon)$-approximation for the number of perfect matchings of a $lambda$-dense bipartite graph, using $O(n^{frac1-2lambdalambdaepsilo{n}^{-2}})$ samples. With size $n$ on each side and for $frac12>lambda>0$, a $lambda$-dense bipartite graph has all degrees greater than $(lambda+frac12)n$. Second, practical applications of the algorithm require many calls to matching algorithms. A novel preprocessing step is provided which makes significant improvements. Third, three applications are provided. The first is for counting Latin squares, the second is a practical way of computing the greedy algorithm for a card-guessing game with feedback, and the third is for stochastic block models. In all three examples, sequential importance sampling allows treating practical problems of reasonably large sizes.

Recommendations

• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• Exact sampling from perfect matchings of dense regular bipartite graphs
• scientific article; zbMATH DE number 1962833
• Permanental generating functions and sequential importance sampling

Cites work

• A Permanent Inequality
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A Sequential Importance Sampling Algorithm for Counting Linear Extensions
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• A Tight Analysis of Bethe Approximation for Permanent
• All-even Latin squares
• An asymptotic series for the number of three-line latin rectangles
• Approximating the Permanent
• Approximating the permanent via importance sampling with application to the dimer covering problem
• Approximating the permanent: A simple approach
• Approximating the  -permanent
• Asymptotic enumeration of Latin rectangles
• Asymptotic evaluation of the number of latin rectangles
• Asymptotics in Random (0, 1)-Matrices
• Balls and bins: A study in negative dependence
• Card guessing with partial feedback
• Combinatorics and complexity of partition functions
• Depth-First Search and Linear Graph Algorithms
• Design for the Control of Selection Bias
• Estimating the number of Latin rectangles by the fast simulation method
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
• Fast sequential importance sampling to estimate the graph reliability polynomial
• Finding all maximally-matchable edges in a bipartite graph
• Forcing a sequential experiment to be balanced
• Generating uniformly distributed random latin squares
• Guessing about guessing: practical strategies for card guessing with feedback
• scientific article; zbMATH DE number 5485444 (Why is no real title available?)
• scientific article; zbMATH DE number 5764789 (Why is no real title available?)
• scientific article; zbMATH DE number 1962833 (Why is no real title available?)
• scientific article; zbMATH DE number 205345 (Why is no real title available?)
• scientific article; zbMATH DE number 3069874 (Why is no real title available?)
• Importance sampling in the Monte Carlo study of sequential tests
• Latin squares of order 10
• Mappings of Latin squares
• Matching theory
• Negative association of random variables, with applications
• On permanents of random doubly stochastic matrices and asymptotic estimates of the nom hers of Latin rectangles and Latin squares
• On the fundamental theorem of card counting, with application to the game of trente et quarante
• On the number of Latin squares
• On the permanents of complements of the direct sum of identity matrices
• Permanents in probability and statistics
• Permanents, \(\alpha\)-permanents and Sinkhorn balancing
• Random generation of combinatorial structures from a uniform distribution
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• Safe and Effective Importance Sampling
• Scalings of matrices which have prespecified row sums and column sums via optimization
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• Statistical problems involving permutations with restricted positions
• The analysis of sequential experiments with feedback to subjects
• The Asymptotic Number of Latin Rectangles
• The complexity of computing the permanent
• The many formulae for the number of Latin rectangles
• The number of latin squares of order eight
• The sample size required in importance sampling
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices

Cited in

(8)

• Permanental generating functions and sequential importance sampling
• Sequential decision model for inference and prediction on nonuniform hypergraphs with application to knot matching from computational forestry
• Sequential Monte Carlo for counting vertex covers in general graphs
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• scientific article; zbMATH DE number 2124889 (Why is no real title available?)
• Semi-restricted rock, paper, scissors
• Sequential importance sampling of binary sequences
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs

This page was built for publication: Sequential importance sampling for estimating expectations over the space of perfect matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103989)