Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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
1  
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
    
The probability of success in half a trial? –  Ross Millikan Aug 15 '12 at 14:17
1  
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.