Constructing a Bernoulli random variable for ratio of Bernoulli weights

Question

$X$ and $Y$ are Bernoulli random variables with weights $0 < \alpha < 1$ and $0 < \beta < 1$. Is it possible to construct a sampler for the Bernoulli random variable with weight $\min(\frac{\alpha}{\beta}, 1)$ given access to samplers for $X$ and $Y$ — i.e., without access to the weights themselves?

If not, are there limit constructions, "up to $\epsilon$", conditions on $\alpha$ and $\beta$, or similar constraints/extensions of the setup that allow such a construction?

For example, a relatively uninteresting answer to this question is to (1) compute an estimate $\hat \gamma$ for the ratio $\frac{\alpha}{\beta}$ by taking $n$ samples each from $X$ and $Y$, (2) construct a uniform random variable $Z$ from $X$ or $Y$ using Neumann's procedure, and (3) use $Z$ to create a biased random variable with weight $\min(\hat \gamma, 1)$. Are there procedures that are more direct, elegant, or efficient?

Answer 1

The obstruction that Bjørn Kjos-Hanssen describes can be made even worse-- it applies to any algorithm (not just von Neumann's trick) and also applies to randomized algorithms (i.e. even if the number of samples is not limited in advance, only the expected number of samples is limited).

Suppose we fix $\epsilon>0$ and we let $Z$ be a Bernoulli random variable with weight $p=\min(\frac{\alpha}{\beta}+\delta,1)$, where $\delta<\epsilon$. It would be nice if we could sample $Z$ after drawing at most $B(\epsilon)$ samples of $X_i$ and $Y_i$, as opposed to $B(\epsilon,\alpha,\beta)$.

Unfortunately, we're out of luck. Suppose that $\alpha=(1/2)\beta>0$. As we let $\beta\rightarrow 0$, then the entropy produced per sample of $X_i$ or $Y_i$ goes to zero. However, the entropy necessary to sample $Z$ is finite (for $\epsilon<1$). So the expected number of samples required to generate even an approximate solution is unbounded.

And here's a tweak on the "uninteresting" approach mentioned by the original poster, specifically step (1). Let $\tau$ be the first time that $Y=1$, i.e. $Y_1=0,Y_2=0,...,Y_{\tau-1}=0,Y_\tau=1$. (Note that $\tau$ is a random variable.) Define $A$ as $$ A = \sum_{i=1}^\tau X_i $$ Then note that $$E[A]=\frac{\alpha}{\beta}$$ This gives us an estimator for $\frac{\alpha}{\beta}$ and is "self-calibrating", in the sense that you don't need to specify $n$ (it just falls out of $\tau$).

It might be tempting to try to use $A$ as a sampler directly. For example, suppose we generate $N$ copies of $A$, say $A_1,...,A_N$, and set $S=\sum_i A_i$. Then $E[S/N]=\alpha/\beta$, and we will converge to the mean as $N$ grows. Unfortunately, the variance of a weight $\alpha/\beta$ Bernoulli random variable is $$\frac{\alpha\beta-\alpha^2}{\beta^2}$$ whereas the variance of $A$ is $$var[A]=\frac{\alpha\beta-\alpha^2}{\beta^2} + \frac{2\alpha^2(1-\beta)}{\beta^2}$$ (note that the first term matches, so $var[A]$ is strictly greater than the target variance for $0<\alpha,\beta<1$). So, the distribution of $S$ and a real Bernoulli random variable will not match even asymptotically, only their means.

(In case it's helpful, here's a handy reference for the formulas for expectation and variance of random sums of random variables.)

Answer 2

There is a relevant result in Keane, M. S. and O’Brien, G. L. (1994). "A Bernoulli factory." ACM Trans. Modeling and Computer Simulation 4 213–219. I don't have that in front of me, but later works (Wästlund. Nacu and Peres) say the result is that given $S\subset (0,1)$ and a function $f:S \to (0,1)$ and a sampler for $Bernoulli(p)$ we can construct a sampler for $Bernoulli(f(p))$ iff $f$ is continuous and there is some $k > 0$ so that

$$ p^k(1-p)^k \lt f(p) \lt 1-p^k(1-p)^k.$$

This fails for $p \mapsto 2p$ on $(0,1/2)$, answering a question asked by Asmussen and Propp.

So, even if you were given the additional information that $\alpha \lt \beta = 1/2$ then there is no way to construct an observable event with probability $\alpha/\beta = 2\alpha$. You have to do some sort of approximation.

Answer 3

One limitation of the von Neumann trick is that you don't know in advance how many samples will be needed.

If you limit the number of samples in advance, we can get a negative answer. That is, suppose for a certain bit in your construction you want to use a Boolean function $f(\vec X,\vec Y)$ of $n$ many $X$-values and $m$ many $Y$-values. Then $p:=\mathbb P(f(\vec X,\vec Y)=1)$ is a polynomial in $\alpha$ and $\beta$.

For instance, if $n=m=1$ and $f(X,Y)=X\vee Y$ then $p=\alpha\beta+\alpha(1-\beta)+(1-\alpha)\beta$.

Thus such a construction (with $\alpha/\beta<1$ and $\epsilon=0$) cannot work unless $\alpha/\beta\in\mathbb Z[\alpha,\beta]$.