(Originally published on September 18th, 2009)

Very frequently I’ve been in a fairly large group of people (5 or more) and we were all trying to go somewhere, say, a movie theater. I noticed that the amount of time it took us to actually get going increased pretty rapidly with the size of the group. This fact by itself should be no surprise to anybody; I have a feeling, though, that the amount of time is super-linear with the number of people, and perhaps it’s even super-polynomial. Let’s see if we can derive this relationship. We’ll make some simplifying assumptions but the gist of the problem should be captured.

Suppose you have \(n\) people in a group. Every person is mostly ready to leave, with the exception of a small number of tasks the person has to do (or can do, given enough time) — you know, the “If we’re not going to leave in the next five minutes, I’m just going to quickly go to the restroom” sort. Assume that each person experiences some distribution of such “events” which derail the effort of leaving. The duration of such events is also a random variable. The group can’t leave if at least one of its members is currently occupied with an event. Let’s say that the probability at any given time that a person is not occupied with an event is \(p\) (\(p\), therefore, is the measure of “readiness”; of course, if \(p=0\), the group will never leave; if \(p=1\), the group will leave at time \(t=0\)).

Assume it takes \(n\) people time \(t\) to leave. Now add a new person to the group. The group will leave at the expected time \(t\) only if the new person happens to be free at that time (with probability \(p\)). If not, the group will have to wait; assuming the events are independent, this will take another time \(t\) (at the end of which the new person may or may not be free). The expected time is therefore

\[tp + 2t(1-p)\cdot p + 3t(1-p)(1-p)\cdot p + 4t(1-p)(1-p)\cdot p + \cdots\\= tp\left(1 + 2(1-p) + 3(1-p)^2\right) + \cdots\]

Let

\[S=1+2a+3a^2+4a^3+\cdots\]

Then

\[S = (1+a+a^2+a^3+\cdots) + (a + 2a^2 + 3a^3+\cdots) = \frac{1}{1-a} + aS\]

Hence

\[S = \frac{1}{(1-a)^2}\]

So the above becomes

\[\frac{tp}{(1-(1-p))^2} = \frac{tp}{p^2} = \frac{t}{p}\]

Suppose \(p=0.5\). The expected time is \(2t\): an additional person doubles the amount of time it takes for the group to leave. The amount of time is therefore not only super-linear in the number of people, it’s actually exponential!