🚀 go-pugleaf

Here's a little probability problem I thought on my way to work (yes, it's
a looooong drive! :-)

Given an unfair coin (with unknown probabilities for head/tail) how can you
approximate a given probability P ?
I.e. try to devise a sequence of tosses and a "winning" combination of
results, so that the probability of achieving this combination is P',
where
    abs(P'-P) < e
for any given error margin 'e'

a) For what values of P the simulation is exact, i.e. you can achieve P=P'
   with a finite number of tosses ?
b) In general, as e-->0, the number of tosses needed in the worst case
   goes to infinity. However the average number of tosses is finite. Find
   it!

Spyros Potamianos
potamian@hpl.hp.com

P.S. Here is a hint from the FAQ...... 


==> probability/unfair.p <==
Generate even odds from an unfair coin.  For example, if you
thought a coin was biased toward heads, how could you get the
equivalent of a fair coin with several tosses of the unfair coin?

Solution follows....


==> probability/unfair.s <==
Toss twice.  If both tosses give the same result, repeat this process
(throw out the two tosses and start again).  Otherwise, take the first
of the two results.