Obtaining irrational probabilities

Question

Let me start with a story.

Our mathematics teacher asked us this question:

Suppose I give you two balls, one black and the other white, then can you give me the white ball with $1/2$ probability?
The answer was easy, we just toss a fair coin and if it lands Heads, we give the black ball, else we give the white one.

Then, we were asked a second question:

Suppose I give you two balls, one black and the other white, then can you give me the white ball with any fractional probability that I tell you? The probability can be like $2/3$ or $7/10$ or $12/100$?
We can answer this question by making {denominator} number of equal pieces of paper and writing White on {numerator} number of pieces and Black on the remaining ones, and then mix all the papers together and take a piece of paper randomly from them. For example, if we want to give the White ball with a probability of $7/10$, we make 10 paper pieces and write White on 7 of them and Black on the remaining three. Now we randomly pick up a piece of paper and then give the ball which has the colour same as that of written on the paper.

Now, I have another question:
If I want to have the white ball with a (well-defined) irrational probability (like $1/\sqrt2$, $\sqrt{12}/\sqrt{33}$ or $1/\pi$), what should be the answer?

By well-defined, I mean that the number should be obtainable by fairly common mathematical methods and not man-made irrational numbers like $0.1234567891011121314151617181920...$, though, if any technique can obtain such a number, then better.

Answer 1

For certain probabilities, there are certain interesting algorithms to produce them without having to calculate their binary expansions, transcendental functions, or the like.

For instance, to produce the probability $1/\pi$, the following algorithm will do (Flajolet et al. 2010), which is based on a series expansion by Ramanujan:

1. Set $t$ to 0.
2. Flip two coins. If both show heads, add 1 to $t$ and repeat this step. Otherwise, go to step 3.
3. Flip two coins. If both show heads, add 1 to $t$ and repeat this step. Otherwise, go to step 4.
4. With probability 5/9, add 1 to $t$. (This is not so trivial but you can use the algorithm you gave to produce this rational probability.)
5. Flip a coin $2t$ times, and choose the BLACK ball if heads showed more often than tails or vice versa. Do this step two more times.
6. Choose the WHITE ball.

For the probability $1/\sqrt{2}$, there is a recursive algorithm as follows:

• Do the following steps repeatedly, until a ball is chosen:
  1. If this is not part of a recursive run: Flip a coin. If heads, choose the WHITE ball and stop.
  2. If this is part of a recursive run: With probability 2/3, flip a coin, choose the WHITE ball if heads or the BLACK ball if tails, and stop.
  3. Do a recursive run of this algorithm. If the recursive run chooses the WHITE ball, choose the BLACK ball and stop.

Note how this algorithm is recursive. Also, for $\sqrt{12}/\sqrt{33}$ there is a similar recursive algorithm based on that number's continued fraction expansion $[0; 1, \overline{1, 1, 1, 12, 1, 1, 1, 2}]$, as well as a more general algorithm for other continued fraction expansions.

Other examples include 1 divided by the golden ratio and $e^{-1}$.

REFERENCES:

• Flajolet, P., Pelletier, M., Soria, M., "On Buffon machines and numbers", arXiv:0906.5560 [math.PR], 2010.

Answer 2

You can of course take this approach, but I don't know whether it's a good answer (especially after the brilliant answer given by Peter O.)-

Decide upon any measure and draw a shape $S$ of area $1$ unit. Then shade an area $A$ of $p$ unit where $p<1$ is your required probability. Now, ask a computer (or something equivalent to it) to choose a random point inside $S$. If it falls in $A$, you give the white ball.

Is that okay?

Answer 3

Here is binary expansion method.

Case 1: The desired probability is rational and its denominator is a power of $2$. The binary expansion will terminate. If the probability is $\frac{m}{2^n}$ with $m$ odd then there will be $n$ bits after the point. I will call this the target. Toss a fair coin with heads representing $1$ and tails representing $0$ to get a random number in binary format with $n$ bits after the point. This random number will be strictly less than the target with the desired probability.

Sometimes you will not need to throw $n$ times since you may be able to see that the number must be above or below the target regardless of the following tosses. In this case, stopping early is just an optimization but it will be important in the following cases.

Example, $\frac{7}{8}$ is $0.101$ in binary. If the first toss is $0$ then the result must be below the target. If the first toss is $1$ then you don't know and will need to toss again. If the second toss is also $1$ then it will definitely be above the target and you can stop. Sometimes, all $n$ tosses will be required but the process is bound to end at that point.

Case 2: Rational but the denominator is not a power of $2$. The binary expansion will not terminate but it will repeat. (Similar to the more familiar decimal case.$\frac{1}{3}$ will not terminate in decimal or binary. $\frac{1}{5}$ will terminate in decimal but not binary.

Proceed as before but the stopping early strategy is essential otherwise you will never stop. It is still possible that you will never stop but the probability is $0$.

Example, $\frac{1}{3}$ is $0.01 01 01 ...$ in binary. If your first toss is $1$ then stop. If it is $0$ then toss again. If the second is also $0$ then stop. If it is $1$ repeat. So, the never stopping case will be a repeating pattern of tail then head; it is possible but has probability $0$.

Case 3: The probability is not rational. The binary expansion will neither terminate nor repeat. In theory, this is the same as the previous case. In practice, you will probably not have the full binary expansion available in advance but you might be able to calculate it to any desired accuracy. In which case, you can calculate in parallel to the tosses and only go as far as required. Again, the process might not ever stop but that has probability $0$.

Example $\frac{1}{\sqrt{2}}$ is $0.101101010000010011110…$ in binary. Keep tossing while you either get a head when the target has a bit of $1$ or a tail when the target has a bit of $0$. If you get to the end of the bits that I provided then you will need to calculate the next one.

Answer 4

Write out your fraction in binary and then flip coins, using $1$ for heads and $0$ for tails, until your fraction clearly is either less than or more than the probability you want. This will work with probability $1$ because it will work in no more than $n$ tosses of your coin with probability $1−\frac{1}{2^n}$.