# The average time before a person find their group

Imagine there are $$N$$ people throwing a party. For any two of them, the time before they meet each other and stick together thereafter is independent, and obeys an exponential distribution whose $$\lambda = 1$$. After they stick together, the newly formed group acts as an individual, and can merge with other individuals/groups following the same rule.

In other words, the time before any two groups (consisting of 1 or more people) meet each other and stick together thereafter is independent, and obeys an exponential distribution whose $$\lambda = 1$$. Obviously, these $$N$$ people will (almost surely) form a group of size $$N$$ in the end.

The question is, what's the average time an individual finds their first group? Here "find their first group" includes (1) form a group with another individual, and (2) join an existing group.

I have tried considering all people except this individuals as an whole, but the later is having internal merges, so it becomes a "compound non-homogeneous Poisson process" (not sure if that's the correct term) which I cannot solve.

Before the first pair joins there are $$\frac 12N(N-1)$$ possible pairs, so the time distribution is exponential with $$\lambda=\frac {N(N-1)}2$$. This takes on average $$\frac 2{N(N-1)}$$ and our person is part of the group with probability $$\frac 2N$$. If the person is not part of the first group, we have the same situation with $$N-1$$ groups, so it takes on average $$\frac 2{(N-1)(N-2)}$$ and our person joins with probability $$\frac 2{N-1}$$

We can write a recurrence. Let $$T(n)$$ be the expected time for a given individual to join a group assuming there are $$n$$ groups. We have $$T(n)= \frac 2{n(n-1)}+\frac {n-2}nT(n-1)\\T(2)=1$$ A quick calculation shows $$T(n)=\frac 2n$$. I am sure this can be proved by induction, but I haven't done so.

• I would appreciate it very much if you can elaborate on $$T(n) = \frac{2}{n} \times \frac{1}{n-1}+\frac{n-2}{n} \times T(n-1)$$ I suppose you are using the law of total expectation, with $\frac{2}{n}$ being the probability the first pair formed among $n$ people containing the person, but in this case, shouldn't the expected time for they to join a group be equal to the expected time for the first pair to form, or $\frac{2}{N(N-1)}$ as you have stated before? – nalzok Mar 2 at 7:22
• I am using the law of total expectation. The first term, including the $\frac 2n$, is the time to form the first group. Everybody waits this long. $\frac {n-2}n$ is the chance they are not in the first group, so they also have to wait the time it would take in a party of $n-1$ people. – Ross Millikan Mar 2 at 15:31