(this thread is becoming something more for math than to security but only for curiosity ...) On Tue, 30 Dec 1997, Mark Whitis wrote: > I post this minor statistical correction to bugtraq because many of > the readers of this list have frequent occasion to calculate > probabilities for security related problems and I have found this > rule of thumb to be useful it mental calculations. > Right, nice rule of thumb. And useful. > limit as n approaches infinity of 1-( (1-1/n)^n ) is about 0.63. > To be more precise as n approaches infinity 1-( (1-1/n)^n ) approaches 1 - 1/e. > I am not an expert on statistics and I have not tried a symbolic > solution to this problem but I have found the general rule(s) of > thumb to be handy. If anyone cares to derive a proof for this, > by all means send me a copy. > After some hours and many scribblings I came to a analytical solution for your rule of thumb ... Let 1/n be the probability to happen the event (in our case the flaw) at any try. After we try m times. We have the probability: 1/n + (1 - 1/n).1/n + (1 - 1/n)^2.1/n + ... + (1 - 1/n)^m.1/n (easy) We can rearrange this to a more compact formula: m 1/n.sum((1-1/n)^i ) i=0 m It's well-know that sum(x^i) = (1 - x^m+1)/(1-x) and ... i=0 in our case n = m, so ... 1 1 - ( 1 - 1/n )^(n+1) -.--------------------- = 1 - ( 1 - 1/n )^(n+1) n 1 - ( 1 - 1/n) Problem is, calculatin the limit when n -> infinity. The hypotesys(better, the wild guess that worked ;-) is: lim[ 1 - ( 1 - 1/n )^(n+1) ] = 1 - 1/e, so ... n->inf lim[(1 - 1/n)^(n+1)] = 1/lim[(1+1/n)^(n)] n->inf n->inf we can say that: lim x^(n+1) = lim x^n (n -> inf) so we get: lim [(1 - 1/n).(1 + 1/n)]^(n) = 1 n -> inf lim ( 1 + 1/n - 1/n + n^(-2)) = 1 n -> inf (we dropped the exploen because 1^(-n) = 1 ) lim n^(-2) = 0 n -> -2 so 1 = 1 (right) As we like to show. (sorry about the english ... I hope it didn't harm the solution) Have a happy new year, Ranaur 72343909365914955820090853918127362974800311909501722 809321335 I'm not a number; I'm a free man! 193580963 224315487 ranaurat_private 7820 The prisoner 629962308 691192077 http://www.inf.puc-rio.br/~ranaur 491038436 4104925118618221315502224252800220835446429441594174
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:38:01 PDT