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

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: