[UA] Re: Re: London (was American attitudes and things)

[Magnus Lie Hetland]

On Jan 19, 2007, at 14:20, Greg Stolze wrote:

> What's the horrible occult significance behind the way that you  
> always seem to pick the slowest line?

How odd -- I was just giving a lecture on this. Or, rather, how to do  
this The Right Way[tm]. In this fantasy-land version of things (also  
known as the Parallel Machine Scheduling Problem) you actually know  
how long each person will take at the register. Finding out in which  
queue to place people so that the last person through will finish as  
early as possible just isn't feasible (it's NP-hard), but if everyone  
gets into the shortest line (in terms of the total time of those in  
the queue) we're guaranteed to be no more than 50% worse than the  
optimal (assuming two queues; (1-1/m) in general, for m queues).

Then again -- this doesn't answer your question, now does it? (I'm  
sure queuing theory won't either, although it might be more relevant...)

While I'm at it (not answering the question), there's a funny little  
paradox related to yours. This one's mathematical (and not occult)  
but it can (somewhat strenuously) be used to argue that we're among  
the most advanced civilizations in the universe, and that's got to  
count for something... It's about waiting for the bus. Which is a  
*bit* like waiting in line. And it's all about Murphy's law. It goes  
like this:

Assume that buses leave the bus stop at random times (at least they  
seem random to you). Uniformly distributed throughout the day, say.  
You show up at the bus stop at a random time, too. Let's say the  
average time between two buses is 10 minutes. You will still, on  
average, have to wait *more* than 5 minutes for the next bus!

Why? Because it's more likely that you'll have ended up in a long  
lull between buses than in a short one.

Tragic, isn't it?

As for the queues: Surely, your observation can't be true for  
*everyone*, or there would only be one queue with people in it. So  
there has to be something special about some people, who always end  
up in the wrong queue. Still not sure whether that's all that  
helpful, though :-]

-- 
Magnus Lie Hetland
http://hetland.org