Bernoulli Factories for Flow-Based Polytopes

DOI10.1137/23M1558343MaRDI QIDQ6202751zbMATH OpenOpenAlexFDO

Authors Rad Niazadeh, Renato Paes Leme, Jon Schneider

Publication date 27 February 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Bernoulli factoriescirculationsexact samplingrandom flows

Mathematics Subject Classification ID

Algebraic combinatorics (05E99) Computational methods for problems pertaining to probability theory (60-08) General topics in the theory of algorithms (68W01)

Abstract: We construct explicit combinatorial Bernoulli factories for the class of emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and $k$-flows. In the process, we uncover new connections to algebraic combinatorics.

Recommendations

• Multiparameter Bernoulli factories
• Nearly optimal Bernoulli factories for linear functions
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• Optimal linear Bernoulli factories for small mean problems
• A Bernoulli factory

Cites work

• A Bernoulli factory
• Barker's algorithm for Bayesian inference with intractable likelihoods
• Bernoulli factories and black-box reductions in mechanism design
• Combinatorial Bernoulli factories
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fast simulation of new coins from old
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• New coins from old: Computing with unknown bias
• Stationarity detection in the initial transient problem

This page was built for publication: Bernoulli Factories for Flow-Based Polytopes

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