Unfair coin (CORRECTION)

Article View: rec.puzzles

Article #2527

#2527

From: Spyros Potamianos
Date: Wed, 06 Jan 1993 18:13

17 lines
1159 bytes

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.

Thanks to David Karr (karr@cs.cornell.edu) for pointing out my mistake!

Spyros Potamianos
potamian@hpl.hp.com

Technical Details

Message-ID: <C0G2Mv.4yq@hplntx.hpl.hp.com>

Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!hpscit.sc.hp.com!hplextra!hplntx!potamian

Show Full Headers

Complete Article Headers

Newsgroups: rec.puzzles
Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!hpscit.sc.hp.com!hplextra!hplntx!potamian
From: potamian@hpl.hp.com (Spyros Potamianos)
Subject: Unfair coin (CORRECTION)
Sender: news@hplntx.hpl.hp.com (HPL News Posting Service)
Message-ID: <C0G2Mv.4yq@hplntx.hpl.hp.com>
Date: Wed, 6 Jan 1993 18:13:41 GMT
Organization: Hewlett-Packard
Lines: 17