🚀 go-pugleaf

In article <C0G2Mv.4yq@hplntx.hpl.hp.com> potamian@hpl.hp.com (Spyros Potamianos) writes:
>Oooooooooops! I made a mistake in my previous posting about approximating
>an arbitrary probability with an unfair coin. The number of tosses you
>need is always unbounded (not finite).
>You see, what happened is that in my mind I broke the problem in two
>subproblems:
>    a) simulate a fair coin using an unfair coin
>    b) generate P (or an approximation to it) from a fair coin
>
>For some values of P (b) only needs a finite number of tosses (e.g.
>P=0.25). However when combining both (a) and (b) to form the problem I
>posted then the number of tosses is obviously unbounded....
>However the average number of tosses you need is still finite.

It is not necessary to simulate a fair coin if you know the probability
of heads and tails for the unfair coin.  And since the original problem
description (which has expired on our machine) contained a tolerance,
you can quit after a finite number of steps.

For example, if the unfair coin comes up tails 10% of the time and heads
90% of the time, and you want to approximate a probability of 0.2 to within
a tolerance of one part in a million, use the following rules in order, one
for each flip of the coin.

If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, keep rolling;   if heads, report failure
If tails, report success; if heads, keep rolling
If tails, keep rolling;   if heads, report failure
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, keep rolling;   if heads, report failure
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, keep rolling;   if heads, report failure
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, keep rolling
If tails, report success; if heads, report failure

Reporting success or failure means that you stop the process.

As another example with the same coin, to approximate 0.19

If tails, report success; if heads, keep rolling
If tails, report success; if heads, report failure

----------------------------------------------------------------------

Dave Dodson		                             dodson@convex.COM
Convex Computer Corporation      Richardson, Texas      (214) 497-4234