🚀 go-pugleaf

In article <C0EF1I.n50@hplntx.hpl.hp.com> potamian@hpl.hp.com writes:
>Given an unfair coin (with unknown probabilities for head/tail) how can you
>approximate a given probability P ?

<SPOILER> ahead...






>a) For what values of P the simulation is exact, i.e. you can achieve P=P'
>   with a finite number of tosses ?

I assume the probability of heads on the unfair coin is truly unknown,
i.e. you cannot say, "If I get heads with probability p I can simulate
P = p^2 exactly."

Then you can still simulate any rational P exactly.  Suppose P = p/q,
p, q both integers.  The simplest (but not generally the fastest) way
to simulate this is to flip a coin q times.  If you get exactly one
head, record "success" if it was among the first p flips.  If you
don't get exactly one head, try again!

This procedure will terminate with probability 1, so it can generate
the p/q probability in a finite (but unbounded) 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!

The average number of tosses will depend on the probability of heads
on the unfair coin, by varying which you can make the average time
as long as you want.  For example, take the FAQ protocol for P=1/2:

>==> 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.

If H = 1 - 10^10 is the probability of heads on the unfair coin, it
will be an awful lot of tosses on average before you get an unequal
pair, in fact before you get a tail at all.  I claim you're unlikely
to generate *any* given probability in a given number of tosses unless
you can expect at least one head in that time frame AND you can expect
at least one tail (note I am not saying you have to expect to get
both!).  By making H arbitrarily close to 1 I can therefore make it
take an arbitrarily long time to generate P regardless of your
protocol.

But let's consider an almost-fair (e.g. real) coin, H ~= 1/2.  Then my
simple-minded procedure is still horrible for large q, because the
odds of exactly one head in the first q tosses are "approximately" (on
a log scale) 1/2^q.

You can improve on this a lot by considering other combinations other
than exactly one head.  For example, suppose q is prime, and let (q k)
designate the number of ways to arrange k identical objects in q slots
("q choose k"); then (q k) is divisible by q whenever 0 < k < q.
So for each such k, designate exactly p*(q k)/q of the possible
arrangements as "success" and the rest as "failure," and you need
try another round of tosses only if you get all heads or all tails.
For large q and an almost-fair coin, the average number of tosses
should then be extremely close to q.

For composite q the picture is more complicated because q does not
always divide (q k) for 0 < k < q, but only for some values of k.  For
other values you can sometimes (always?) generate p'/q' for p' a
divisor of p and q' a divisor of q, and generate the remaining factors
of p/q using a shorter protocol for the "retry."  I'm not sure if
there's a clean analysis of this.

-- David Karr (karr@cs.cornell.edu)