Re: WG ACTION: 2 weeks to discuss [LL66] Additional statistical example

>Stuart - for my own understanding, can you explain the computation you made
>for your statistical example?
>
>- Ralph

Answering your question, I noticed I had a typo in the email I sent to 
Erik. I meant "better than 85% chance", not 75%.

When we join one network onto another, we can model this as a network 
with 100 hosts on it (the "existing hosts"), and 100 new hosts joining 
that network (the "new hosts"), with the additional constraint that the 
100 new hosts are already known not to conflict with each other.

What is the probability that this entire merge completes without a single 
conflict?

Notation:

p(sn) is the probability that new host n joins without conflict.

p(Sn) is the cumulative probability that n new hosts join without 
conflict.

p(sn|S(n-1)) is the probability that new host n joins without conflict, 
given that the previous hosts all joined without conflict.

p(S100) is the probability that the merge completes without conflict.

By induction

p(Sn) = p(sn|S(n-1)) * p(S(n-1))
[Probability of event Sn is probability of
event sn, given event S(n-1), times probability of event S(n-1)]

so p(S100) = p(s100|S99) * p(S99)

[The probability of complete success (p(S100)) is the probability that 
host 100 will join without conflict, given that the 99 previous ones also 
joined without conflict, times the probability that the 99 previous ones 
also joined without conflict.]

and

p(S0) = 1

[Base case: There can be no conflict when no hosts have joined.]

Therefore, what we want to calculate is the product of

   p(s1|S0) ... p(s100|S99)

What is p(s1|S0)?

The network has 65024 possible addresses. 100 are in use, so 64924 
addresses are available.

New host 1 could have any of the 65024 possible addresses. The 64924 of 
these that are free yield success; the 100 that are in use yield failure. 
p(s1) = 64924/65024 = 99.85% chance of finding a free address.

p(S1) = p(s1|S0) * p(S0) = 0.9985 * 1 = 0.9985.

What is p(s2|S1)?

We now know, given event S1, that the address of new host 1 is not in use 
by another host, on existing or new. That means that there are 65023 
possible other addresses that could be used by existing hosts and by new 
host 2. The probability that new host 2 does not conflict with any 
existing host, given that host 1 did not, is 64923/65023.

In general, 

p(s(n+1)|Sn) = (64924-n)/(65024-n)

For n in the range [0,99], this value ranges from 99.8462% to 99.8460% 
probability of success for each host, and the cumulative product of these 
values is 85.7250% chance of complete success.

C code is below:

#include <stdio.h>

int main(int argc, char **argv)
	{
	double p = 1.0;
	double existinghosts = 100.0;
	double newhosts = 0.0;
	int i;
	
	for (i=1; i<=100; i++)
		{
		double range = (256.0 * 254.0) - newhosts;
		double psuccess = (range - existinghosts) / range;
		p *= psuccess;
		newhosts += 1.0;
		printf("host %3d; newhosts %3.0f; psuccess = %f; p = %f\n",
			i, newhosts, psuccess, p);
		}
	}


Stuart Cheshire <[email protected]>
 * Wizard Without Portfolio, Apple Computer, Inc.
 * www.stuartcheshire.org