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 ranaur@usa.net 7820 The prisoner 629962308
691192077 http://www.inf.puc-rio.br/~ranaur 491038436
4104925118618221315502224252800220835446429441594174