Bus Puzzler

Ramesh gave me a puzzler today. I'm standing at a bus stop. During any given minute, a bus has a 1/10 chance of being there. So my expected wait time is 10 minutes. But, if I looked into the past, I would find that I would expect to go back 10 minutes to find when the last bus was here.

But, that makes it sound like a bus came about 10 minutes ago, and the next one will come about 10 minutes from now, which suggests I'm in a 20 minute gap between busses, whereas we would expect buses to come 10 minutes apart. So shouldn't we expect to be 5 minutes from a bus?

My solution

Instead of waiting for a bus, imagine that we are standing in the middle of a row of peach trees, and each tree has a 1/10 chance of having a ripe peach. Now if we go to the left, we expect to examine 10 trees before finding a ripe peach. If we go to the right, we also expect to examine 10 trees before finding a ripe peach. So it still sounds like we're in a 20-tree gap between ripe peaches.

But, if we do a breadth first search to the left and right simultaneously, examining the tree immediately to our left, and then the one immediately to our right, and then the second tree on our left, and then the second tree on our right, and so on, then we still expect to examine 10 trees before finding a ripe peach, but this means that we'll probably find that tree within 5 trees of our current location.

In the bus example, if we looked into the past and future simultaneously, we would expect to find a bus 5 minutes away. So.. phew.

But, I'm wrong

We do expect to see a bus 5 minutes away, either in the past or in the future, but we don't expect to see a bus 5 minutes away in the past and in the future. That is to say, of the two buses we're between, the closer one is probably 5 minutes away, but the further one is probably 15 minutes away. So we really are in a 20 minute gap between buses, it seems. Or so says a simulation I ran...

function waitForBus() {
    var t = 1
    while (Math.random() < .9) t++
    return t
}

var sum = 0
var total = 100000
for (var i = 0; i < total; i++) {
    var a = waitForBus() // bus in the past
    var b = waitForBus() // bus in the future
    var c = a + b
    sum += c
}
sum / total

I ran this using my JavaScript utility, and it spits out 20. And if I replace c = a + b with c = Math.min(a, b) to simulate the nearest bus, it spits out about 5.25 (not quite 5, but close). And putting in c = Math.max(a, b) yields about 14.75 (not quite 15, but close). The fact that 5.25 + 14.75 = 20 makes me suspect that the .25 and .75 parts may be "real", but I don't understand them.

While discussing this with a friend, he looked up the answer online and read something about sampling bias toward longer gaps. This seems right. The average gap between buses is 10 minutes, but some gaps are much longer, and we're probably in one of those. For instance, if there were only two sizes of gap, 5 minutes and 15 minutes, then the average gap size would be 10 minutes, but the 15 minute sized gaps would consume 15/(5+15) = 75% of the time. So if we showed up to the bus stop at some random time, there would be a 75% chance that it was a 15 minutes gap, and a 25% chance that it was a 5 minute gap, meaning we expect to be in a 75%*15 + 25%*5 = 12.5 minute gap, which is longer than the "expected" 10 minute gap.