1
$\begingroup$

Given i.i.d samples $X_1, X_2, \cdots$ from Bernoulli($p$) and $1<c<\frac{1}{p}$, is it possible to construct samples from Bernoulli($cp$) under the assumption that $p$ is unknown? If $c\leq1$ or $c=\frac{1}{p}$ it is trivial.

I am actually looking for an algorithm that given samples from a discrete probability distribution on the set $\{1,2,3,...,n\}$ with unknown probability mass function $\{p_{1},p_{2},\cdots,p_{n}\}$ and a constant c such that $1<c<\frac{1}{1-p_{1}}$ gives samples from the probability mass function $\{(1-c+cp_{1}),cp_{2},cp_{3},\cdots, cp_{n}\}$. Is it possible to solve this problem if it is possible to solve the above problem?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Maybe the article "New Coins from Old, Smoothly" by Holtz, Nazorov and Peres would help answer your question. You have not made it clear what you would allow in the construction process (for instance in the "trivial" case $c\le 1$, are you allowed to use further coins with probability $c$ of heads?) $\endgroup$
    – Anthony Quas
    Commented Aug 28, 2019 at 6:05
  • 1
    $\begingroup$ The Holtz-Nazorov-Peres paper is at arxiv.org/abs/0808.1936, and it seems to answer the question, but it could use some examples. $\endgroup$
    – user44143
    Commented Aug 28, 2019 at 6:33

1 Answer 1

Reset to default
3
$\begingroup$

Perhaps most relevant is [1] which discusses this construction and reduces the general case to $c=2$. See Theorem 1 and proposition 15 there. Note that $cp \le 1$ is not a sufficient condition; an inequality of the form $cp<1-\epsilon$ for some known $\epsilon>0$ is required. This follows from the criterion in the pioneering paper of Keane and O'Brien [2]. See also the interesting follow-up works [3], [4] that present some more efficient algorithms and implementations. In particular the introduction of [4] surveys the relevant literature up to 2016. In [5] it is shown that coins with success probability $cp$ for $c>1$ cannot be simulated in any interval of $p$ values via finite automata.

[1] Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old." The Annals of Applied Probability 15, no. 1A (2005): 93-115. https://projecteuclid.org/download/pdfview_1/euclid.aoap/1106922322

[2] Keane, M. S., and George L. O'Brien. "A Bernoulli factory." ACM Transactions on Modeling and Computer Simulation (TOMACS) 4, no. 2 (1994): 213-219.

[3] Łatuszyński, Krzysztof, Ioannis Kosmidis, Omiros Papaspiliopoulos, and Gareth O. Roberts. "Simulating events of unknown probabilities via reverse time martingales." Random Structures & Algorithms 38, no. 4 (2011): 441-452.

[4] Huber, Mark. "Nearly optimal Bernoulli factories for linear functions." Combinatorics, Probability and Computing 25, no. 4 (2016): 577-591.

[5] Mossel, Elchanan, and Yuval Peres. "New coins from old: computing with unknown bias." Combinatorica 25, no. 6 (2005): 707-724. https://arxiv.org/pdf/math/0304143.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .