Sequential importance sampling for estimating expectations over the space of perfect matchings
From MaRDI portal
Publication:6103989
DOI10.1214/22-aap1834zbMath1515.60035arXiv2107.00850OpenAlexW3182153411MaRDI QIDQ6103989
Amin Saberi, Unnamed Author, Mohammad Roghani, Persi Diaconis
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
Latin squaresperfect matchingstochastic block modelsequential importance samplingKL-divergencedense bipartite graphcard guessing experiment
Sampling theory, sample surveys (62D05) Monte Carlo methods (65C05) Combinatorial probability (60C05) Orthogonal arrays, Latin squares, Room squares (05B15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding all maximally-matchable edges in a bipartite graph
- Fast sequential importance sampling to estimate the graph reliability polynomial
- Combinatorics and complexity of partition functions
- The complexity of computing the permanent
- Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
- Permanents in probability and statistics
- The many formulae for the number of Latin rectangles
- Estimating the number of Latin rectangles by the fast simulation method
- Random generation of combinatorial structures from a uniform distribution
- Matching theory
- Scalings of matrices which have prespecified row sums and column sums via optimization
- Asymptotic evaluation of the number of latin rectangles
- On the permanents of complements of the direct sum of identity matrices
- The analysis of sequential experiments with feedback to subjects
- Importance sampling in the Monte Carlo study of sequential tests
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Mappings of Latin squares
- The sample size required in importance sampling
- Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
- Negative association of random variables, with applications
- Latin squares of order 10
- All-even Latin squares
- Permanents, \(\alpha\)-permanents and Sinkhorn balancing
- On the number of Latin squares
- An asymptotic series for the number of three-line latin rectangles
- A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Approximating the Permanent
- Design for the Control of Selection Bias
- Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci
- Approximating the -permanent
- A Permanent Inequality
- Generating uniformly distributed random latin squares
- Approximating the permanent: A simple approach
- Safe and Effective Importance Sampling
- On the fundamental theorem of card counting, with application to the game of trente et quarante
- Balls and bins: A study in negative dependence
- On permanents of random doubly stochastic matrices and asymptotic estimates of the nom hers of Latin rectangles and Latin squares
- A Tight Analysis of Bethe Approximation for Permanent
- Guessing about Guessing: Practical Strategies for Card Guessing with Feedback
- Statistical problems involving permutations with restricted positions
- The number of latin squares of order eight
- Asymptotics in Random (0, 1)-Matrices
- Forcing a sequential experiment to be balanced
- Depth-First Search and Linear Graph Algorithms
- Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
- The Asymptotic Number of Latin Rectangles
- Card guessing with partial feedback
- Asymptotic enumeration of Latin rectangles
- A Sequential Importance Sampling Algorithm for Counting Linear Extensions
