Simulating bernoulli trials with unknown p Assume I have access to independent Bernoulli trials with bias $p$ where $p$ is unknown and $p < 0.01$ (or any other small positive number).
Is it possible to simulate Bernoulli trials with bias $cp$ for some $c > 1$ independent of $p$? Any single value of $c$ would be good, it is not necessary to solve it for all $c$. By simulation, I mean an algorithm that uses the Bernoulli trials as an oracle and returns a Bernoulli trial with the larger $p$. I have (unsuccessfully) tried the following:
Get two samples and take OR. This gives me probability of success of $2p - p^2$, so there is a $p^2$ that I do not want. Now, if I instead take AND, it gives me bias $p^2$. Flipping an unbiased coin and taking AND/OR depending on the outcome gives me average of those two success probabilities, thus removing the unwanted $p^2$. However, it also decreases the coefficient in front of $p$ to 1 so this does not work.
Edit: as noted in a comment, I am interested in an exact solution. As can be seen from my failed attemtp, it is easy to get a relatively good approximation for small $p$.
 A: This is possible in your scenario only if you know that p is such that cp is not more than 1 − ε. In three different papers, Huber has presented algorithms that simulate the probability cp in this particular case.
However, if p is totally unknown, this is impossible; once cp touches 1 somewhere in (0, 1), it's impossible to simulate the probability cp using coins of unknown probability p of heads (Keane and O'Brien 1994).
REFERENCES:

*

*Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.

*Huber, M., "Optimal linear Bernoulli factories for small mean problems", arXiv:1507.00843v2 [math.PR], 2016.

*Huber, M., "Designing perfect simulation algorithms using local correctness", arXiv:1907.06748v1 [cs.DS], 2019.

*Huber, M., "Nearly optimal Bernoulli factories for linear functions", arXiv:1308.1562v2 [math.PR], 2014.

A: I will take $c$ samples (or nearest integer to it) and use OR. This gives me bias $1-\left(1-p\right)^{c}=cp+\sum_{i=2}^{n}{a_{i}p^{i}}$
Assuming $p$ is very small, i can drop higher power terms and get $cp$ as bias
A: More generally, you may make $n$ trials of the given (unknown) distribution and for a certain subset of the $2^n$ outcomes accept this as a success of the simulated $cp$-Bernoulli.The probability of each such outcome is a polynomial in $p$, and as they are mutually exclusive, we can just add the polynomials to obtain the overall probability. This is again a polynomial in $p$, but can it be $cp$ without any higher terms? If so, this would work even when $p\approx 1$ and $cp>1$, which is absurd.
On the other hand, I can simulate a fair coin by making two trials and if they differ take the outcome of the first trial as result, otherwise repeat the process. And with a fair coin, I can readily simulate any probability $q$ by producing random "bits" and thereby a uniformly distributed number $\in[0,1)$. Note that in contrast to the method in the first paragraph,  this  uses an unbounded number of trials - but almost surely only finitely many.

So we may try to combine these methods.
Let $d=\lceil c\rceil$ so that $d$ is ane integer $\ge2$.
As seen above, we can simulate probability $\frac cd$. Hence if we can simulate $dp$ and and it with this, we arrive at the desired probability $cp$.
According to Convergence of a product of polynomials, theree is a non-decreasing sequence of exponents $k_i$ such that $$ \prod_{i=1} ^\infty(1-p^{k_i})=1-dp \quad\text{for }0\le p<\frac 1d.$$
So $1-dp$ is the probability of "AND"-ing infinitely many experiments with individual probability $1-p ^{k_i}$, or: $dp$ is the probability of "OR"-ing infinitely many experiments with individual probability $p^ {k_i}$.
Now we almost have a way to simulate proabability $dp$ for $0\le p\le \frac1d$:

*

*Let $i\leftarrow 1$

*Let $k\leftarrow k_i$

*Perform $k$ trials of the $p$-Bernoulli experiment. If they all succeed, return "SUCCESS" and stop.

*Otherwise, let $i\leftarrow i+1$ and go back to step 2.

While this will eventually return "SUCCESS" with probabity $dp$, it will never return "FAIL", but instead will continue endlessly with probability $1-dp$.
To improve on this, we need a two-way approximation to $dp$. (To be continued)
