On a recent trip abroad, I had to choose whether to pack everything into one bag or take two. One factor: how much longer will I wait in baggage reclaim if I take two bags? Making the assumption (implausible for a couple of reasons, but never mind) that bags arrive independently at random times during some fixed interval, it turns out that if you have n bags then the expected (i.e., average) arrival time of bag k is k/(n+1) of the way through that interval. In particular, on average your last bag arrives n/(n+1) of the way through. So if you take two bags instead of one then you wait, on average, for 2/3 of the worst-case time instead of 1/2; you wait 4/3 times as long.
This isn't difficult to prove, but the simplest proof I can find still involves doing some integrals. Isn't there a one-line argument that makes it obvious?
Update, 2007-12-09: A friend emailed me with a nice intuitive proof for the case n=2. I haven't been able to make it work rigorously for arbitrary n, but reflecting on why not leads to this, which isn't a one-liner but at least involves few ideas and no integrals:
Suppose your bags (numbered in advance, rather than in order of eventual arrival) arrive at times t1...tn. They're independent and uniformly distributed. Now, suppose you learn that t1 lies in a certain interval; then the distribution of t1 conditional on this new discovery is uniform in that interval, and the distribution of all the other tj is what it was before.
Learning that t1=t for some particular t *and that t1 is the smallest of all the tj* is just a matter of learning that t1 is in [0,t] and that all the others are in [t,1]; therefore, all the other tj are now uniformly distributed in [t1,1], and this is true whatever the value of t was so it's always true.
At this point we've reduced the situation for n to the situation for n-1 and a simple application of induction finishes the job.
Um. Yes, I suppose I do need that. (Of course if one is true then the other is too, with a symmetrical proof, so that's OK.) In this kind of situation it pays to be careful about the "early" cases in the induction (remember the proof that all horses are the same colour); the case n=1 is easy, and then for n=2 we get that t1 is half-way between 0 and t2 and similarly for t2, which is enough. Phew.
I'm still not at all satisfied with any of this; surely there must be a much simpler and clearer proof.
Post a comment:
You silently but crucially invoked a symmetry condition too, right? Or I've missed something. I.e. it seems that for the result to follow as stated you need t(2) to t(n) uniform in [t(1), 1] and t(1) to t(n-1) uniform in [0, t(n-1)].