Re: Odds of Recurrence for Hash Function

On Mon, Dec 08, 2008 at 09:19:21AM -0500, Bill Yerazunis wrote:
>    >
>    > The 2nd message has 1 chance in 2^32 of colliding.
>    > The 3rd message has 2 chances in 2^32 of colliding
>    > The 4th message has 3 chances in 2^32 of colliding
>    >
>    > so you want N such that SUM (1 to N) = 10% of 2^32
> 
>    You can't sum up the probabilities because the events are not
>    disjoint. 
> 
> Disagree.  The events _are_ disjoint because we're looking for the
> first such event.  

I think Fidelis is right, the _non collision_ events are disjoint, so you'd
use those P (PNC) 
 
>  The 2nd message has 1 in 2^32-1 of not colliding
>  The 3nd message has 2 in 2^32-2 of not colliding
>  ...

hm, shouldn't that be

  2nd message has 2^32-1 in 2^32 of _not_ colliding
  ...
  
which agrees with Fidelis' formula

> and we keep adding up these disjoint, mutually exclusive
> chances until we hit a 10% chance.

again the other way 'round, multiply PNC till PNC(N) < 0.9, ie PC >= 0.1

>    PNC(N) = (H-1)/H * (H-2)/H * (H-3)/H * ... * (H-N+1)/H

which yields Fidelis' PNC(30085) = .899996 ie PC(30085) >= 10%.


-- 
paolo

------------------------------------------------------------------------------
SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada.
The future of the web can't happen without you.  Join us at MIX09 to help
pave the way to the Next Web now. Learn more and register at
http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/