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

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

http://mathworld.wolfram.com/GeometricDistribution.html
http://mathworld.wolfram.com/ExponentialDistribution.html
http://mathworld.wolfram.com/BinomialDistribution.html
http://mathworld.wolfram.com/PoissonDistribution.html

-- 
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: