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.

Suppose I have access to a fair coin. Is it possible to come up with a procedure that (1) returns TRUE with irrational probability (say $1/\sqrt{2}$) and FALSE otherwise, and (2) terminates in a finite amount of time?

I would think not, because at the end of the day I'm just assigning either TRUE or FALSE to sequences of coin flips, and any such assignment results in a rational probability. However, I don't think there's harm in asking: is there some extraordinarily clever way to extract irrational probabilities?

[Edit] Alternatively, what if we relax condition (2) to "terminates with probability 1"? (Thanks user6312!)

share|improve this question
    
@Elliott: One can do it by relaxing your condition to "with probability $1$ terminates." –  André Nicolas May 30 '11 at 23:13
    
Without knowing (or rembering) a lot about statistics, have you considered something like this: one might trow up a coin 10 x 10 times, count the number of heads for every 10 throws, calculate the average, variance, ... (or something like that) and test whether it is in some interval. I think I would find it more surprising if these probabilities were always rational. –  Myself May 30 '11 at 23:17
    
@Myself: These probabilities can only be multiples of $2^{-100}$, since they are the probabilities of some subset of the power set of the independent and equiprobable elementary events, the coin flips. –  joriki May 30 '11 at 23:23
    
@Joriki: Ah well indeed, thank you! –  Myself May 30 '11 at 23:24
1  
What if you are allowed to flip a needle? en.wikipedia.org/wiki/Buffon%27s_needle –  Per Alexandersson May 31 '11 at 4:19

2 Answers 2

up vote 20 down vote accepted

It depends on what you mean by "terminates in a finite amount of time". This could mean:

  1. Always terminates in a finite amount of time, or

  2. Terminates in a finite amount of time with probability 1.

If you mean the former, you are correct that any event that depends on finitely many coin flips will have rational probability.

However, if you allow processes that terminate with probability 1, then any irrational probability is possible. For example, if you want an event with probability $1/\sqrt{2}$, simply interpret the sequence of coin flips as the digits of a binary number between 0 and 1, and check whether the resulting number is less than $1/\sqrt{2}$. With probability 1, you will be able to tell after some finite number of flips whether or not your number is less than $1/\sqrt{2}$, so you will almost surely have to flip only a finite number of coints.

share|improve this answer
1  
Elliott, if the number of flips is bounded a priori, there are only a finite number of possibilities (no matter how they are defined), so the probability of any one of them is rational. –  Dan Brumleve May 30 '11 at 23:45
1  
indeed, any event that depends on finitely many coin flips will be a rational with denominator $2^n$. So, for example, probability 1/3 cannot be generated in that way. –  GEdgar May 31 '11 at 0:25
    
What I love about this technique is that it works for rational non-power of two probabilities too. And I think its more efficient than naive rejection sampling. Reminds me a lot of en.wikipedia.org/wiki/Arithmetic_coding too. –  Michael Anderson May 31 '11 at 6:33
    
GEdgar, to get 1/3, why can't you flip two, try again if HH happens, and return TRUE if TT happens? (Michael, is this what you mean by "naive rejection sampling"?) –  Elliott May 31 '11 at 9:40
    
@Elliott: This is a good method. But, because of the "try again" provision, it can exceed your allowed number of tosses. –  GEdgar May 31 '11 at 13:49

Flip the coin until you get a tail. If the number of heads is prime, return TRUE. Otherwise, return FALSE.

share|improve this answer
    
I'm not looking forward to working out the exact probability, but I definitely believe that it's irrational! –  Elliott May 30 '11 at 23:50
    
It is 0.00110101000101000101... The bits at prime indices are set (you may want to be more careful than me about off-by-one errors). It is irrational because primes are not periodic. –  Dan Brumleve May 30 '11 at 23:51
3  
How to prove this number is transcendental? –  Dan Brumleve May 31 '11 at 0:20

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.