Some people attend a networking event, which is a fancy way of saying "a place where people shake hands." Oddly enough, each person initiates a handshake with exactly one other person over the course of the event; this other person is randomly chosen with uniform probability -- and of course can not be himself.

We consider two people to have shaken hands if either or both of them initiated a handshake with the other. Thus many people could have shaken hands with the same person, and two people may have shaken hands with each other twice. We consider two people A and B to belong to the same network if they have shaken hands, or if A has shaken hands with someone belonging to the same network as B.

For example, suppose 7 people attend. We denote each person using a number. The handshakes may be as follows:

1 shakes hands with 2

2 shakes hands with 1

3 shakes hands with 7

4 shakes hands with 5

5 shakes hands with 1

6 shakes hands with 5

7 shakes hands with 3

This results in the networks {1, 2, 4, 5, 6} and {3, 7}.

Suppose 100 people attend the event. To 6 decimal places, what is the expected number of people in the largest network?

## Network Effect

### Network Effect

Some time last year I thought of this problem and posted it on a wall at my workplace, but nobody wanted to solve it... and then I remembered this forum. So here I am with this problem. Enjoy! (Later I find out there are papers written about this problem, but I couldn't find one which gave an exact formula.)

### Re: Network Effect

I find 81.424033.

### Re: Network Effect

I get 81.4243077, but to save time and memory, my algorithm only considers 0.9999942 of all cases.

### Re: Network Effect

Wow, that was fast

I am solving this with a recurrence relation. Could there be a closed-form expression?

My answer for 200 people is 159.6319208462766, computed in about 12 seconds and using lots of memory with Java BigInteger. Maybe there is a way to compute without using BigInteger...

I am solving this with a recurrence relation. Could there be a closed-form expression?

My answer for 200 people is 159.6319208462766, computed in about 12 seconds and using lots of memory with Java BigInteger. Maybe there is a way to compute without using BigInteger...

### Re: Network Effect

I get the same answer for 200. My approach must be similar, using a recurrence and Java BigInteger, but only 25Mb and 0.13s for 200. I have not found a closed form formula.jer-bear wrote:...I am solving this with a recurrence relation. Could there be a closed-form expression?

My answer for 200 people is 159.6319208462766, computed in about 12 seconds and using lots of memory with Java BigInteger. Maybe there is a way to compute without using BigInteger...

### Re: Network Effect

More results, from an exact algorithm (which also uses Java and BigInteger).

E(100) = 81.4240329218325

E(200) = 159.63192084627659

E(300) = 237.27431487414844

E(400) = 314.62439473407545

E(500) = 391.7877747430619

E(600) = 468.8185771837519

E(700) = 545.7489380680325

E(800) = 622.5997897966862

E(900) = 699.3856692454125

E(1000) = 776.1171588474358

E(1100) = 852.8022465908942

E(1200) = 929.4471378503679

E(1300) = 1006.0567669823678

E(1400) = 1082.63513451001

E(1500) = 1159.1855373082542

E(1600) = 1235.7107304959954

E(1700) = 1312.213044479208

E(1800) = 1388.6944713453727

E(100) = 81.4240329218325

E(200) = 159.63192084627659

E(300) = 237.27431487414844

E(400) = 314.62439473407545

E(500) = 391.7877747430619

E(600) = 468.8185771837519

E(700) = 545.7489380680325

E(800) = 622.5997897966862

E(900) = 699.3856692454125

E(1000) = 776.1171588474358

E(1100) = 852.8022465908942

E(1200) = 929.4471378503679

E(1300) = 1006.0567669823678

E(1400) = 1082.63513451001

E(1500) = 1159.1855373082542

E(1600) = 1235.7107304959954

E(1700) = 1312.213044479208

E(1800) = 1388.6944713453727