8

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 ;-)

Thanks in advance!

Pedro A. Ortega
  • 743
  • 4
  • 11

1 Answers1

7

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.

This paper by Łatuszyński et al. might also be useful for the implementation.

Robin Ryder
  • 1,787
  • 1
  • 11
  • 16
  • 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](http://stats.stackexchange.com/a/50299/2970). 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