Using only the toss of a fair coin, devise an experiment whose probability of success is 1/3.

probability/flips/arbitrary.probability New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Using only the toss of a fair coin, devise an experiment whose
probability of success is 1/3.  Can it be done for any probability q
with 0 <= q <= 1, even an irrational one?

Show solution

In article <CCtrxs.ArG@sci.kun.nl>, hoeij@sci.kun.nl (Mark van Hoeij)
writes:

>>Using only the toss of a fair coin devise an experiment whose
>>probabilty of success is 1/3.
>
>Someone asked me if this was possible for irrational probabilities
>0<=q<=1.  That is also a nice puzzle.  It is true for all 0<=q<=1.
>For instance: try to generate a probability of Pi^2/6.

[ Editor: Pi^2/6 = 1.645... is greater than 1; 6/Pi^2 = 0.608... was
presumably meant. ]

If q = 0 or q = 1 then we don't really have a problem do we.

The whole problem reduces to generating a random number of arbitrary
accuracy such that 0 <= r <= 1.  Try this, it should return TRUE with
probability q.

flipvalue = 0.5
sum = 0

while sum < q and sum + 2*flipvalue > q
  flip coin; if it's heads sum = sum + flipvalue
  flipvalue = .5 * flipvalue
end while

if sum < q return (TRUE) else return (FALSE)

-- Harri Haanpää [Editor: "Haanp{{" in the original, a 7-bit
   encoding of ä] <haha@vipunen.hut.fi>  (September 1993)