$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](http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin), 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?



Constructing a Bernoulli random variable for ratio of Bernoulli weights
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](http://www.math.unl.edu/~sdunbar1/ProbabilityTheory/Lessons/Conditionals/RandomSums/randsum.shtml) for the formulas for expectation and variance of random sums of random variables.)


