20

Say I have a random event $E$ with probability $p$. There is a natural interpretation in terms of $E$ for the probability $p^2$: it's the probability that $E$ occurs twice if I perform two independent trials.

Is there a similar interpretation for the probability $\sqrt{p}$? More generally, given $x \in ]0, 1[$, is there an interpretation of $p^x$?

a3nm
  • 653
  • 3
    As you are probably well aware, this is a surprisingly deep problem and the answer to most versions of the question is no. Googling Bernoulli factory provides a significant portion of the relevant literature, among which seminal papers by Keane and by Peres and co-authors. – Did Aug 15 '12 at 11:36
  • 2
    Perhaps this is not the best way to solve the problem, but let p=1/2. This means that for any combination of possible results from any number of tests, the probability of those results can be written as x/2^y, where x and y are whole numbers. However, sqrt(1/2) is irrational. – PhiNotPi Aug 15 '12 at 12:05
  • 1
    did: I'm not well aware that the problem is deep, I just thought about it and did not find useful references. Your Bernoulli factory reference is interesting, it would be frustrating if there is indeed no simpler interpretation for the simple case of the square root. PhiNotPi: Yes, this is a good argument against the existence of a simple interpretation... – a3nm Aug 15 '12 at 12:18
  • 1
    The probability of success in half a trial? – Ross Millikan Aug 15 '12 at 14:17
  • Ross Millikan: I thought of this, but I couldn't understand exactly what it should mean. – a3nm Aug 15 '12 at 14:23
  • 2
    I don't think that the rationality/irrationality argument is enough to dismiss a simple interpretation. After all, a square with area $2$ has side length $\sqrt{2}$, which no one finds terribly disturbing. (At least, not for the past two-and-a-half thousand years ...) – Théophile Aug 15 '12 at 14:52
  • Got something from the answer below? – Did Sep 02 '16 at 15:11
  • @Did: The answer is interesting and I upvoted it, but I am not accepting it because I don't feel like it fully answers my question. My understanding is that this is a simulation procedure to define a random Boolean variable with probability $1/\sqrt{2}$, but somehow I don't find it as natural as the obvious intuitive interpretation for $p^2$... – a3nm Sep 02 '16 at 21:37
  • 1
    Did you try to read some of the papers my very first comment is sending you to? If you had, you would know for a fact that what you are waiting for simply does not exist. – Did Sep 02 '16 at 21:52
  • @Did: Contrary to what your initial comment assumes, I am not familiar with the area, and it is not obvious for me to understand the connection. As far as I can tell, this article and that article are about the design of simulation procedures; I'm interested in what an event with probability $\sqrt{p}$ would mean (i.e., how could one interpret it intuitively), not in an effective simulation. – a3nm Sep 02 '16 at 22:33
  • @Did: However, if you think that these references are relevant (i.e., that an intuitive explanation would always imply the existence of a simulation procedure, or something like that), it would probably be helpful (to me and to other readers) if you edited your question to explain this in more detail than in your initial comment. :) – a3nm Sep 02 '16 at 22:36
  • 1
    My question? Which question? Anyway, seeing you hypothetize that references I pointed 4 years ago as relevant (and which are relevant, as every expert in the field would confirm) may or may not be relevant is very gratifying, to say the least. Oh, and by the way, your insistence on being given an event of probability $\sqrt{p}$ just shows you did not read the constructions in these papers, which, of course, provide one such event (as every simulation process does), using an unbounded but almost surely finite number of throws. – Did Sep 02 '16 at 23:01
  • @Did: Apologies, I meant your answer, rather than your question. I did not mean to hurt your feelings and I am not implying anything about your intents, but maybe it is the case that your understanding of my question does not match what I intended to ask. I did not read the above papers as I still fail to understand how they are relevant to what I want. If you think I am mistaken, feel free to edit your answer to explain how they relate. I still cannot understand the connection from your previous remarks. – a3nm Sep 02 '16 at 23:21
  • While this ws set as an open question in Nacu & Peres, Mendo shows that there indeed exists a Bernoulli factory for $f(p)=\sqrt{p}$. With an average number of draws of $\mathbb E[N] =1/√p$. See Thomas and Blanchet for improvements. – Xi'an ні війні Apr 20 '20 at 16:47
  • @Xi'an: Thanks for the references! The question is more about whether there is an "intuitive explanation" to an event of probability $\sqrt{p}$, the way there is for an event with probability $p^2$. Bernoulli factories don't seem very intuitive, though I agree they are related. – a3nm Apr 27 '20 at 14:43
  • As detailed in my answer to the related X validated question, there exists a constructive algorithm to draw $\sqrt{p}$ coins when handling a $p$ coin. Looking at the algorithm can give you an intuition of the meaning of generating an event of probability $\sqrt{p}$. A simpler intuition is being faced by an experiment where observations of an event with probability $q$ always come by pairs, the probability of both observations being simultaneously success being $q^2$ and otherwise $1-q^2$. Check the example Dorfman's group blood testing. – Xi'an ні війні Apr 27 '20 at 16:57
  • (...) I was running out of room, but I meant iid observations in the pair. And Dorfman's experiment usually applies to more than two individuals. – Xi'an ні війні Apr 27 '20 at 17:06
  • My answer to the related X validated question – Xi'an ні війні Apr 28 '20 at 11:43
  • Dorfman's group blood testing – Xi'an ні війні Apr 28 '20 at 11:44
  • Thanks for the pointers. I must admit I'm not able to extract much intuition out of the procedure to generate an event of probability $\sqrt{p}$ from an event of probability $p$, but I guess that's just intrinsically complicated. :/ – a3nm Apr 28 '20 at 15:38

1 Answers1

8

As already said in the comments, the answer depends very much on the simulation procedures one allows. Assume for example that $p=\frac12$ and that one wants to simulate a bit 0 or 1 with probability $\sqrt{p}=\frac1{\sqrt2}$ of being 1. Since $\frac1{\sqrt2}$ is not dyadic, this is impossible from a finite collection of unbiased independent bits, but, as soon as one allows a stream of independent unbiased bits with finite but unlimited length, basically everything becomes possible.

To see this in the example at hand, consider the series expansion $$ \frac1{\sqrt2}=\sum\limits_{n\geqslant0}{2n\choose n}\frac1{2^{3n+1}}. $$ This suggests the following procedure. First simulate some independent unbiased bits with values 0 or 1, and count the number N of 0s before the first 1. If N=0 (that is, if the first bit is 1), return B=1. Otherwise, simulate 2N other independent unbiased bits with values 0 or 1 and consider their sum S. If S=N, return B=1, otherwise, return B=0. Then, B has probability $\frac1{\sqrt2}$ to be 1.

The mean number of unbiased bits needed to generate N is 2, hence the mean number of unbiased bits needed to get each (biased) bit B is 2+4=6.

Did
  • 279,727
  • This is great! Though I think it could be formulated a bit more concisely, how about "$\sqrt{1/2}$ is the probability that of two infinite sequences $a$ and $b$ of unbiased random bits, the exact number $n$ of leading zeroes in $a$ appears in $2n$ leading bits from $b$". – leftaroundabout Jan 22 '13 at 15:38