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):