# An Introduction to Bernoulli Factories

Renato Paes Leme (renatoppl [at] google [dot] com)

(Last updated in September 2021)

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:

References: