# How to generate a Bernoulli variate with bias $a/\mathbb{E}[X]$ given a sampler of $X$ and uniform variates?

Given:

1. A loaded "die" with unknown probabilities generating a discrete, positive random variable $X$ taking on values in $\mathcal{X}$.
2. A real number $a$, such that $0 \leq a \leq \mathbb{E}[X]$.
3. Uniform random variates.

Problem:

Generate a Bernoulli random variate with bias $\frac{a}{\mathbb{E}[X]}$.

Note:

• The idea is to avoid estimating $\mathbb{E}[X]$.
• A solution would in a sense be the "inverse" of the Monte Carlo trick. To obtain a Bernoulli variate with bias $\frac{\mathbb{E}[X]}{b}$, you can first sample an $x$ using the die and then draw a Bernoulli with bias $\frac{x}{b}$, assuming $\mathbb{E}[X] \leq b$. However, when the expectation is in the denominator, generating the correct probabilities seems to become non-trivial.
• Even a negative answer (justified) is appreciated ;-)

• Just a point of clarification: Is $\mathcal X$ assumed known? – cardinal Mar 2 '13 at 1:05
• no - you can find out about $\mathcal{X}$ by rolling the die. – Pedro A. Ortega Mar 2 '13 at 8:38

This is similar to a "Bernoulli factory" problem. This paper by Nacu and Peres shows that given a way to simulate from a $Bernoulli(p)$, it is possible to simulate from a $Bernoulli(f(p))$ iff $∃n,∀p, \min(f(p),1-f(p))≥min(p,1-p)^n$.
With your notations, depending on the values of $a$ and $b$, you may or may not be able to get this inequality.
• I believe this result is inapplicable to the question posed. The die can be thought of as generating a vector of $|\mathcal{X}|$ Bernoulli random variates with biases $p(x), x \in \mathcal{X}$. Then, given any of these random variates, the function $f_x(p(x))$ is equal to $f_x(p(x)) = \frac{a}{\mathbb{E}[X]} = \frac{a}{p(x)x + \sum_{x' \neq x} p(x') x'}$, which depends on the probabilities $p(x'), x' \in \mathcal{X} \setminus \{x\}$. However, these are unknown in the problem statement, and therefore any of the $f_x$ functions are unknown too. – Pedro A. Ortega Feb 27 '13 at 14:02
• Dear Robin, welcome to the site and thank you for the links, especially the first one, which I had not seen. Incidentally, I recently rediscovered a similar technique for the special case $f(p) = 1 - p^a$ (though, how to generalize is clear) that I posted in an answer to a related question here. Nacu and Peres' algorithm, specifically Proposition 16 on pg. 15 appears similar, but not quite the same. Theirs may be better; I'll have to read the paper more thoroughly to know. Thank you, again and I hope to see you continue to contribute! Cheers. – cardinal Feb 27 '13 at 15:16