This page contains the materials for the tutorial given in the European Summer School on Learning in Games, Markets, and Online Decision Making (ALGADIMAR) 2021. Please tell me if you find any errors in either the slides or the lecture notes.

Abstract: We will discuss a tool from applied probability called a "Bernoulli factory". In the Bernoulli factory problem you are given a coin (coin = Bernoulli variable) with unknown bias $p$ and you are asked to sample another variable with bias $f(p)$. Here is an example, given in the form of a puzzle: say that you have a coin with bias $p$ but you don't know what $p$ is. Now you are asked to sample $\{0,1\}$ with probability $f(p)=\exp(p-1)$. You can flip your $p$-coin as many times as you want.

We plan to cover the following topics (we will see how far we can get):

• Examples of Bernoulli factories: Bernstein monomials, moment generating functions, ...
• Von Neumann's Problem: how to sample an unbiased coin from a biased one?
• Characterize the set of functions $f(p)$ that admit a Bernoulli factory
• Coins to Dice: the Bernoulli Race
• Bernoulli Factories for Rational Functions
• Combinatorial Bernoulli Factories
• Factory for $k$-subset (Sampford Sampling)
• Factories for co-dimension $1$
• Factories for any affine subspace
• Factory for Matching
• Applications to Mechanism Design
• Some open Problems

Materials:

• Slides: version-0, version-1
• Lecture Notes: version-1

References:

• A Bernoulli Factory (Keane and O'Brien)
• New coins from old: computing with unknown bias (Mossel and Peres)
• Fast simulation of new coins from old (Nacu and Peres)
• From the Bernoulli Factory to a Dice Enterprise via Perfect Sampling of Markov Chains (Morina, Latuszynski, Nayar, Wendland)
• Extending the Bernoulli Factory to a dice enterprise (Morina)
• Multiparameter Bernoulli Factories (Paes Leme and Schneider)
• Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes (Niazadeh, Paes Leme and Schneider)
• Bernoulli Factories and Black-Box Reductions in Mechanism Design (Dughmi, Hartline, Kleinberg and Niazadeh)