  A Bernoulli factory is an algorithmic procedure for exact sampling of certain
random variables having only Bernoulli access to their parameters. Bernoulli
access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but
has sample access to independent draws of a Bernoulli random variable with mean
equal to $p$. In this paper, we study the problem of Bernoulli factories for
polytopes: given Bernoulli access to a vector $x\in \mathcal{P}$ for a given
polytope $\mathcal{P}\subset [0,1]^n$, output a randomized vertex such that the
expected value of the $i$-th coordinate is \emph{exactly} equal to $x_i$. For
example, for the special case of the perfect matching polytope, one is given
Bernoulli access to the entries of a doubly stochastic matrix $[x_{ij}]$ and
asked to sample a matching such that the probability of each edge $(i,j)$ be
present in the matching is exactly equal to $x_{ij}$.
  We show that a polytope $\mathcal{P}$ admits a Bernoulli factory if and and
only if $\mathcal{P}$ is the intersection of $[0,1]^n$ with an affine subspace.
Our construction is based on an algebraic formulation of the problem, involving
identifying a family of Bernstein polynomials (one per vertex) that satisfy a
certain algebraic identity on $\mathcal{P}$. The main technical tool behind our
construction is a connection between these polynomials and the geometry of
zonotope tilings. We apply these results to construct an explicit factory for
the perfect matching polytope. The resulting factory is deeply connected to the
combinatorial enumeration of arborescences and may be of independent interest.
For the $k$-uniform matroid polytope, we recover a sampling procedure known in
statistics as Sampford sampling.
