23
$\begingroup$

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!)

  • 0
    I was asked something very close to this question in a job interview and couldn't answer it. I came on here hoping for a proof that it was impossible. Great question and answers.2011-08-24

2 Answers 2

23

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.

  • 1
    +1 It seems that the expected number of coin flips is 2 (except when the target probability can be written as a rational with a denominator which is a power of 2, in which case a slightly lower expectation is possible).2011-06-12
9

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

  • 3
    How to prove this number is transcendental?2011-05-31