# Samples from a modified Bernoulli

Given i.i.d samples $$X_1, X_2, \cdots$$ from Bernoulli($$p$$) and $$1, 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 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?

• 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?) – Anthony Quas Aug 28 '19 at 6:05
• 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. – Matt F. Aug 28 '19 at 6:33

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.