Multiparameter Bernoulli Factories

02/15/2022

∙

by   Renato Paes Leme, et al.

∙

0

∙

share

We consider the problem of computing with many coins of unknown bias. We are given samples access to n coins with unknown biases p_1,…, p_n and are asked to sample from a coin with bias f(p_1, …, p_n) for a given function f:[0,1]^n → [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.