[REBOL] Re: Question about checksum/secure
From: holger:rebol at: 19-Nov-2001 10:58
On Mon, Nov 19, 2001 at 05:38:15PM +0100, Ladislav Mecir wrote:
> Your second formula is incorrect for any n except for (n = 2 ** 160).
> Especially it is incorrect for (n = 2), where it yields twice as much as it
> should. OTOH for higher n, (2 < n) and (n < (2 ** 160)), the probability
> of a collision may be much higher than your formula yields. The correct
> formula should be:
>
> m: 2 ** 160
> q: 1 * (1 - (1 / m)) * (1 - (2 / m)) * ... * (1 - (n - 1 / m))
> p: 1 - q
>
> , where Q is the probability that no collision occurs.
Thanks, you are right. I was thinking about having m-i in the denominator, so
most parts would conveniently cancel out, but it is really m all the time...
So the chance for a collision among n elements seems to be
1 - (m! / ((m-n)! * m^n))
--
Holger Kruse
[holger--rebol--com]
