  We study the existence of algorithms generating almost surely nonnegative
unbiased estimators. We show that given a nonconstant real-valued function $f$
and a sequence of unbiased estimators of $\lambda\in\mathbb{R}$, there is no
algorithm yielding almost surely nonnegative unbiased estimators of
$f(\lambda)\in\mathbb{R}^+$. The study is motivated by pseudo-marginal Monte
Carlo algorithms that rely on such nonnegative unbiased estimators. These
methods allow "exact inference" in intractable models, in the sense that
integrals with respect to a target distribution can be estimated without any
systematic error, even though the associated probability density function
cannot be evaluated pointwise. We discuss the consequences of our results on
the applicability of pseudo-marginal algorithms and thus on the possibility of
exact inference in intractable models. We illustrate our study with particular
choices of functions $f$ corresponding to known challenges in statistics, such
as exact simulation of diffusions, inference in large datasets and doubly
intractable distributions.
