[hashcash] geometric vs poisson (Re: Statistics of hashcash collisions)
- From: Adam Back <adam@xxxxxxxxxxxxxxx>
- To: hashcash@xxxxxxxxxxxxx
- Date: Thu, 27 May 2004 07:33:57 -0400
Hubert Chan wrote:
| I think you are mixing up your distributions. The *time* taken to
| find a collision follows a geometric distribution, which is a
| discrete distribution, and is approximated by the exponential
| distribution, which is a continuous distribution.
Yes I've been using geometric.
On Tue, May 25, 2004 at 07:01:40AM +0200, Anonymous wrote:
> Call v the product of the probability of a success on each trial times
> the number of trials. For a 20 bit hashcash collision, v of 1 would
> correspond to approximately 1 million trials. Then the chance of having
> exactly n hits in time v is:
>
> P_v(n) = v^n * exp(-v) / n!
>
> Now, with hashcash we don't run past our first hit. So for this analysis
> I will calculate the probability of 1 - P_v(0) for various values of v.
so P_{1/16} = 1 - exp(-1/16) = 0.0605
P_{1/8} - P_{1/16} = 0.0569
P_{1/4} - P_{1/8} = 0.103696
etc
with (discrete) geometric distribution:
P(i=n) = q^{n-1}.p
P(i>=n) = q^{n-1} or P(i<n) = 1-q^{n-1}
so take b=10, n = 2^b = 1024, p = 1/n, q = 1-p
v range probability
-----------------------
0 - 1/16 .05969735974105994696
1/16 - 1/8 .05699703132405127909
1/8 - 1/4 .10383875234535864133
1/4 - 1/2 .17249160475988258728
1/2 - 1 .23891607963302808331
1 - 2 .23272391049199429143
2 - 4 .11703751500437658655
4 - 8 .01796326612642484726
8 or over .00033448057382373679
I think poisson will approximate to q^n rather than q^n-1, obviously
as b and so n=2^b gets larger (recall p=1/n,q=1-p) they get
asymptotically close.
Adam
Other related posts:
