In my high school days, my daily commute consisted of: a 2 km bike ride, a 10 min train ride, 10 min walk, and finally 10 min by bus. For the final bus ride, there were a handful of coaches that all passed by my school. They would always come in a bunch and in the same order. I would always take the first and rarely got to ride on the other routes. This phenomenon didn’t strike me as odd back in the day, but it is more or less what the “waiting time paradox” is about.
The waiting time paradox is usually explained as follows. Assume that buses (always buses!) arrive at a bus stop at random times, then your expected waiting time is longer than if they came at identical intervals. Assume that bus i arrives at time ti, bus j at time tj, and you some random time t in between, ti < t < tj. Then your expected waiting time for bus j is (tj – ti)/2. However, the chance of arriving at a specific interval is proportional to the duration of it, so the contribution of longer intervals gets a higher weight when we calculate the total expected waiting time.
If you are used to thinking in pictures, the illustration above should make the waiting time paradox even more intuitive. If we plot the waiting time as a function of the arrival time (your arrival time, not the buses), we get a sawtooth pattern. The average waiting time is then proportional to the area under the curve. Panel A shows one example with equal times between the 13 buses, and one with unequal times. I leave it for you, dear reader, to convince yourself that the shaded area in the upper case is smaller than the one below. By playing around with triangles, one can show that the minimum area—i.e., the minimal expected waiting time—occurs when time is equally divided. I try to illustrate this in panel B—the white triangle in the rightmost picture corresponds to the excess time from making the inter-bus times unequal.
Is that a paradox? What is a paradox anyway? A “seemingly absurd statement that turns out to be true upon reflection,” says my dictionary, and I’ve always assumed the reflection bit needs more than just a little effort. Like the Banach-Tarski paradox—assuming the axiom of choice (see below), you’d be able to divide a solid ball into a finite number of pieces and reassemble them into two solid balls of the same size as the original one. I haven’t stopped reflecting yet, since I first heard about it.
With that “that’s not a knife” argument out of the way, I am not saying that the waiting time paradox is trivial, or unworthy of scientific studies. (I have papers about it, and I really like this introduction to young readers by Naoki Masuda and Mason Porter.) But calling it a paradox feels like mystifying something that is really quite intuitive. Maybe “[something] bus [something] effect” would have been better.
The waiting time paradox has a cousin—the “friendship paradox”—saying that, for most nodes in a network, its neighbors’ average degrees are larger than its own degree. This is perhaps slightly more paradoxical, but nevertheless a misnomer. In addition to its also-not-so-paradoxical nature, it is not about friendships but about friends. Finally, it does have a more restrained synonym—the ripple effect—that seems to have been forgotten.
The friendship and waiting time paradoxes are related because they both come from sampling a quantity (degrees or waiting times) with a probability proportional to the value itself. The chance of having a friend with k friends is proportional to k. The likelihood of reaching the bus stop during an inter-bus interval of T minutes is proportional to T.
However, beyond both being sampling biases appearing in similar types of data, the friendship and waiting time paradoxes are different. A high-degree node is essential in most dynamic situations, but a long interevent time (now, let’s stop thinking of buses) is inconsequential. Consider rumors spreading over a social network. The highest degree node will probably always hear a gossip early. The propensity of the highest degree node to relay the rumor could substantially impact the gossip cascade. A node in a lengthy hiatus, on the other hand, will have little bearing on the gossip propagation. Or, taking this argument to the extreme—an interevent time going to infinity could represent the absence of a node (or link), but not so for a node with a degree tending to infinity. Moreover, for disease spreading, it turns out that it is the left end of the (usually fat and right-skewed) interevent time distribution that affects epidemics most, but the right end (the tail) of the degree distribution.
To wrap up. The waiting-time and friendship paradoxes are, if not really paradoxes, at least important effects whose consequences for us, as networked people, are yet to be fully understood.
Petter Holme 