5

I'd like a design a circuit that, given a random bit with probability $p$ to be zero, it outputs a random bit with probability $\sqrt{p}$ to be zero. Actually, I am rather looking for $\sqrt{p(1-p)}$, in case it makes things easier.

Let's assume that we have an unlimited but finite stream of independent random bits and all the common logic gates (AND, OR, NOT, XOR...).

If an exact solution wouldn't be possible in a finite setting. I would also be happy with an approximation, preferably one that can be arbitrarily expanded to reduce the error.

I have already looked into a Taylor expansion around $p=1/2$, and it is a good option. The second degree expansion of $\sqrt{p(1-p)}$ is $\frac{1}{2} - (p - \frac{1}{2})^2 + O((p - \frac{1}{2}))^4$ which goes to $\frac{3}{4} + p(1-p)$ which is nice and easy to implement.

I am here to see if there is a better solution.

This question is highly related to the following question, but the answer is not general enough to satisfy my needs.

Understanding what $\sqrt{p}$ means for an event of probability $p$

Oersted
  • 53
  • If you can make $P(X=1)=\sqrt p$ bit you known how to make an independent $P(Y=1)=\sqrt{1-p}$ bit, and then $P(XY=1)=\sqrt{p(1-p)}$. And you might be able to use the fact that all the terms in the Taylor expansion for $1-\sqrt{1-p}$ are non-negative to build an algorithm (but possibly not circuit) to do the job. – kimchi lover Dec 28 '17 at 14:29
  • @kimchilover True, getting $p(1-p)$ having $p$ is rather trivial, I just mentioned it in case it simplifies things. For instance, the Taylor expansion of $\sqrt{p(1-p)}$ is much "nicer" than the one of $\sqrt{p}$.

    Could you elaborate on your comment about using the fact that the terms are non-negative. What do you have in mind? A more complex algorithm may also work if it's not too complex.

     – Oersted Dec 28 '17 at 14:38
  • After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. – Clement C. Jan 02 '18 at 16:45

1 Answers1

6

From (the abstract of) this paper [1] by Elchanan Mossel and Yuval Peres:

however, pushdown automata can simulate $f(p)$-coins for certain non-rational functions such as the square root of $p$. These results complement the work of Keane and O'Brien (1994), who determined the functions $f$ for which an $f(p)$-coin can be simulated when there are no computational restrictions on the simulation scheme.

You may want to look at Section 3.2 of the arXiv version linked above, which describes a pushdown automaton for simulating an $\sqrt{p}$-coin. Moreover, as they discuss in Section 1.1, their Theorem 2.2 implies that no finite automaton can simulate an $\sqrt{p}$-coin.

Also very relevant is this other paper, by Wästlund: as discussed in this blog post, the discussion after Theorem 2.1 (in Section 2) describes a procedure to simulate an $\sqrt{p}$-coin.

[1] New Coins From Old: Computing With Unknown Bias. Elchanan Mossel, Yuval Peres, Combinatorica 25(6): 707-724 (2005)

[2] Functions arising by coin flipping. Johan Wästlund, 1999.

Clement C.
  • 67,323