A debiased Bernoulli factory and unbiased estimation of a probability

Abstract

Given a known function $f:[0,1]\to (0,1)$ and a random but almost surely finite number of independent, Ber$(x)$-distributed random variables with unknown $x\in [0,1]$, we prove the existence of an unbiased, $[0,1]$-valued estimator of the probability $f(x)\in (0,1)$. Our estimator is based on so-called debiasing, or randomly truncating a telescopic series of consistent estimators. Debiased estimators of a probability are not typically constrained to $[0,1]$, or even bounded, even when all consistent estimators used as inputs are. We show that constructing the series of consistent estimators from the coefficients of a particular Bernoulli factory yields provable boundedness provided $f\in C^{\rho }[0,1]$ for $\rho >3$. Our result can be thought of as a novel Bernoulli factory with the appealing property that the required number of Ber$(x)$-distributed random variates is independent of their outcomes.

10 pages