9
$\begingroup$

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!

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

1 Answer 1

Reset to default
8
+25
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Pedro A. Ortega
    Commented Feb 27, 2013 at 14:02
  • $\begingroup$ 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. $\endgroup$
    – cardinal
    Commented Feb 27, 2013 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.