Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

solution: arrival-time puzzle



At 05:18 PM 7/8/00 -0400, I posted the following puzzle:

Suppose a lot of busses whiz past your window. The events are IID, that
is, Independent and Identically Distributed over time. The average rate is
6 busses per hour.

Fact: At any random time, if you ask how long it has been since the last
bus, the answer is 10 minutes, on average.

Fact: At any random time, if you ask how long it will be until the next
bus, the answer is 10 minutes, on average.

Therefore at any typical time, on average there is 20 minutes between the
last bus and the next bus.

Fact: The average interval between busses is 10 minutes.

Question: How do you reconcile those three facts?

=========================================================================

Answer:

1) Consider busses that are not random, but pass every ten minutes like
clockwork. A graph of the passage events looks like
X.........X.........X.........X.........X.........X.........

2) Consider busses that travel in pairs, one pair every twenty
minutes. The graph is
XX..................XX..................XX..................

3) Consider busses that travel in clusters of three, one cluster every
thirty minutes. The graph is:
XXX...........................XXX...........................

It is easy to see that in all cases the average number of busses is 6 per
hour. It is also easy to see that the average interval between busses is
always 10 minutes, PROVIDED the average includes the super-short intervals
within the clusters.

Finally, we see that if you ask at a random time how long it has been since
the last bus, the answer is proportional to cluster size. Ditto for the
next bus.

So to answer the puzzle: The IID events are not uniformly spread out, one
every ten minutes, but neither do they typically arrive in large
clusters. Roughly speaking an IID process is somewhat analogous to a
clockwork process with an "average" cluster size of _two_. (Actually of
course it's a mixture of loose clusters of all possible sizes, but big
clusters are very unlikely.)

==================

Here's another way of looking at the puzzle: Suppose you have a sack full
of sticks of random lengths.

1) We all know one method for calculating the average length: just add up
all the lengths and divide by the total number of sticks. That uses a
_measure_ where all sticks are counted equally.

2) There is another way to calculate the average length: Reach into the
sack and grab a stick at random. Record its length. Put it back in the
sack. Iterate. Calculate the average of the random numbers generated
thereby. This is the Monte Carlo method. In the limit, it converges to
the same answer as the previous method, provided all the sticks have an
equal _probability measure_, i.e. an equal chance of being chosen.

3) There is yet another way: Reach into the sack and pull out a stick at
random, but this time the probability of choosing a stick is proportional
to its length. This is a perfectly good probability measure, it is just a
_different_ probability measure from the one that was used in the two
previous methods. The average length you get using this measure will be
exactly twice the average you get from the previous methods, because the
longer sticks are more heavily weighted.

This is what's going on in the bus puzzle: If you show up at the window at
a random time and ask how long is the current inter-bus interval, it is
extra-likely that the question will be asked during a long interval. Hence
the factor of two discrepancy between the two notions of "average" or
"typical" interval.