Multiparameter Bernoulli Factories

Abstract

We consider the problem of computing with many coins of unknown bias. We are given samples access to $n$ coins with \emph{unknown} biases $p_1,\dots ,p_n$ and are asked to sample from a coin with bias $f(p_1,\dots ,p_n)$ for a given function $f:[0,1{]}^n\to [0,1]$. We give a complete characterization of the functions $f$ for which this is possible. As a consequence, we show how to extend various combinatorial sampling procedures (most notably, the classic Sampford Sampling for $k$-subsets) to the boundary of the hypercube.