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