[hashcash] Re: geometric vs poisson (Re: Statistics of hashcash collisions)

  • From: Hubert Chan <hubert@xxxxxxxxx>
  • To: hashcash@xxxxxxxxxxxxx
  • Date: Thu, 27 May 2004 13:25:34 -0400

>>>>> "Adam" == Adam Back <adam@xxxxxxxxxxxxxxx> writes:


Adam> with (discrete) geometric distribution:


Adam> I think poisson will approximate to q^n rather than q^n-1,
Adam> obviously as b and so n=2^b gets larger (recall p=1/n,q=1-p) they
Adam> get asymptotically close.

I think you misunderstood me.  To approximate a geometric distribution,
you use an exponential distribution, not Poisson.  Poisson approximates
a binomial distribution.  (And with the probabilities that we're
working with, the approximation should be fairly good.)

Poisson gives you the probability of a given number of hits after a
fixed time (P_v(n) -- v is supposed to be fixed, not variable, in a
Poisson distribution).  Exponential gives the probability that the first
hit occurs within a given time (P(X<=x) where X is the random variable,
and x is the time in question).

The analysis seems to be correct.  It's just the naming that Anonymous
uses is off.


Hubert Chan <hubert@xxxxxxxxx> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

Other related posts: