1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – nalzok Mar 2 at 7:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Mar 2 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.