Comment by dxbydt | Hacker News Reader

Comment by dxbydt | Hacker News Reader

scala> import org.apache.commons.math.distribution.{ExponentialDistributionImpl=>expo}

//pc = process customer, with a mean time mu per customer

scala> def pc(mu:Int):Double= new expo(mu).sample

// q = queue of n customers with mean process time mu

scala> def q(n:Int,mu:Int):Double=(1 to n).map(_=>pc(mu)).sum

scala> // put 3000 people in 1 queue with mean process time 50

scala> (1 to 1000).map(_=>q(3000,50)).sum/1000

res43: Double = 83107.37275937156

scala> //now put 1000 people each in 3 separate queues with the same mean process time as before

scala> (1 to 1000).map(_=>(1 to 3).par.map(_=>q(1000,50)).sum).sum/1000

res45: Double = 200010.29627921886

200010 = ~3x83107, so yeah, single line to 3 cashiers is ~3x faster than a separate line for each cashier.

// Now make 1 queue that feeds into shortest of the 3 queues

scala> def qq(n:Int,mu:Int)=(1 to 3).par.map(_=>{(1 to n/3).map(_=>pc(mu)).sum}).sum

scala> (1 to 10000).map(_=>qq(3000,50)).sum/10000

res70: Double = 141824.974765643

So our single queue feeding into 3 separate queues still beats 3 separate independent queues.

edited to address MaysonL's question.

Okay, someone with some Scala expertise needs to jump in here. The code as written is _clearly_ incorrect. q(n,mu) sums a distribution with mean mu n times. The expected value of this is mu * n. Then we run this 1000 times and average the results. If this is not extremely close to mu*n then I will eat my hat. In R, sum(replicate(1000,sum(rexp(3000,1/50)))) / 1000 returns ~150000 (using sum for clarity instead of mean). Maybe scala is caching the seed or something?

I don't know what the "par" function does, but assuming it doesn't do anything crazy, the answer for all three of those expressions should be exactly 150,000, because they just reorder the order of summation.

Ok, I realized that I wrote something like this without seeing your post first.

The poster is a quant working with Scala so I am certain I have just misunderstood something. Nevertheless, my humble bachelor's degree has led me to the same conclusion as you.

But of course this is BS, because the three queues are not independent. Try it with 1 queue which feeds into whichever of the three queues is currently shortest. And of course, in grocery stores, where one can unload one's cart while the person ahead is being processed, there's an advantage to multiple lines.

>Try it with 1 queue which feeds into whichever of the three queues is currently shortest

I have edited my original response to include that scenario as well. btw for M/M/1 vs M/M/3, here's a good reference: http://people.brunel.ac.uk/~mastjjb/jeb/or/queue.html

Isn't this essentially equivalent to having a single queue though... except now you have a kind of cache at each register holding a small number of customers?

Yes, and it is how real stores work, which is the point.

Right. I wonder what would happen if we try to include a measure of perceived fairness from the customer's point of view into this type of analysis. I always feel I'm picking the wrong queue at stores... single queues going to whatever cash is open seem fairer, if that makes sense.

Perceived fairness is very hard to quantify objectively. Is it fair if there are queues for people buying less than X items? If there are queues for people not paying cash? For frequent flyers? That you, by sheer misfortune, end up in the slow queue three times in a row? Should pensioners wait for people having work to do? Should fit people make room for the elderly? To what extent? Etc.

Instead, I think you should do the math; it will teach you that the probability that a given queue is slow is smaller than the probability that, given a person in a queue, that person is in a slow queue.

So, you spend more time in slow queues than in fast ones. Once you know that, train yourself to accept it.

That's because if there are 4 lines there is generally a 75% chance that one of the other lines was faster.

Except that the "primary" queue doesn't feed into the shortest register queue, it feeds into the register queue that the person at the front of the primary queue anticipates will empty the fastest. That's the premise that underlies the whole article: people get in the line they predict will move the fastest, and everyone uses different variables and judgment to make that prediction. Those variables and those predictions don't show up when your model is based on distributions.

The register queues are not independent, but they are not related as simply as you say.

>everyone uses different variables and judgment to make that prediction. Those variables and those predictions don't show up when your model is based on distributions.

Sorry but that's simply not true. everyone uses different variables and judgment to make a phone call, yet phone calls follow an exponential distribution! everyone uses different variables and judgment to hit the internet, yet network traffic follows a Lavalette distribution. everyone uses different variables and judgment to buy stocks, yet equity prices follow a lognormal distribution.

Individual behavior in aggregate will almost always follow some distribution, regardless of each individual using different variables and judgment for himself. The whole point of statistics is to uncover the underlying probability distribution given tons of (seemingly random) data. Math does the opposite ( ie. given the distribution, a mathematician can tell you how to derive nice things like the moment generating function & the first & second moments & density functions & related family of distributions & so on, & in general give you n sample variates that fit the distribution. By saying "everyone uses different variables and judgment" you are in essence saying its just too complicated, but even if that were true, that is just another distribution ( white noise )

Thanks for explaining it that way, I think I understand better now.

Would you agree, though, that customers wouldn't simply enter the shortest available line?

>Would you agree, though, that customers wouldn't simply enter the shortest available line?

I don't agree with that at all. In reality, some would and some wouldn't do what you suggest. If all of them did exactly what you are suggesting ( some sort of extreme rational agent), the distribution wouldn't be exponential. But then, all human beings don't buy low & sell high, nor do all of us withdraw money from the same ATM at the same time, nor do we make phone calls at the same time, or hit the internet at the same time. Aggregate behavior distributions modelling aggregate behavior of individual humans work well except in very extreme conditions such as 911 when everybody does indeed make the phone call at the same time thus jamming up the airwaves and killing the shape of the nice Erlang distribution at the telephone exchange.

"Phone calls follow an exponential distribution"

I'm confused as to the meaning there. What is it about phone calls that follow an exponential distribution? Their duration? Their quantity per capita per time of day?

>I'm confused as to the meaning there. What is it about phone calls that follow an exponential distribution?

Sorry for the confusion. Lemme clarify a bit. Say you work at an office. 9am to 5pm. 8 hours a day.

scala> 60x60x8

res45: Int = 28800

So a phone call can arrive in any one of those 28,800 seconds. Putting it another way, the probability p of getting a phone call at any particular second is very remote, but the number of seconds aka trials is n=28800 ie. very large. Anytime you have very small p and very large n, that's a nice candidate for a particular member of the exponential family of distributions. In this case, the arrival times of phone calls to your office will be Poisson.

Say you hire an office assistant to count the number of phone calls every day, and she tells you after a month that your office averages say 24 calls a day. That 24 is your mu, the mean of the Poison distribution.At that point you know everything you need to know about the distribution, because Poisson is a discrete distribution whose probability p is specified entirely by the mean mu!

So you can go off and compute the probability p like so:

scala> import scala.math.{exp,pow}

scala> def fact(n:Int):Int = { if( n>1) nfact(n-1) else 1}

scala> def p(mu:Int,n:Int) = {pow(mu,n)exp(-mu)/fact(n)}

The chances of your office getting 4 or fewer phone calls by noon is then easy to figure out. Since you average 24 calls in 8 hours, you should average 9 calls by noon. So the probability of getting 4 or fewer calls would be

scala> (0 to 4).map(p(9,_)).sum

res46: Double = 0.05496364149510491

So you have a 5% chance of getting 4 or fewer calls by noon. If someone offers to bet a million dollars that your office will get 4 or fewer calls by noon, the odds of winning that bet are 1 in 19.

edit:formatted for better readability.

I'm having a hard time following the scala.

Do you mind writing out what you're doing in pseudocode or in words? Intuitively, this result doesn't seem obvious to me.

Imagine where you have a one line scenario - you watch which register people go to. Label people who went to registers A,B,C with A, B and C respectively. Then, repeat the situation, but instead of one line, use 3, where everyone labeled A stands in one line, B in the other, and C in the third.

The transactions play out exactly like before. I realize we're dealing with probabilities and expected values, but it's definitely not obvious to me.

Sorry, here's some R code ( profusely commented ) http://www.stanford.edu/class/cs109l/code/week5/exponential....

>Intuitively, this result doesn't seem obvious It isn't obvious because human arrival times at checkout counters follow a Poisson distribution and their service times follow an Exponential distribution. The stated results follow immediately if you look at the cumulative density function for the exponential.

Stated another way, suppose service times followed a Uniform distribution. Then none of this would hold. But because they are Exponential, these results come into play. Intuitively, we think in terms of Uniform distribution. So your mind is saying, wait a minute, if there are 1000 people in a queue, they probably average a 10 to 15 service minute per person. But that's like saying if there are 1000 people in an office, they probably make 100k on average because that's about what you (might) make. In reality incomes follow a Pareto, so your janitors will take home 30k and your managers will pull in a couple mil. A similar sort of dynamic applies here with the exponential distribution. The key takeaway is: Service times are not uniform but exponential.

Can you elaborate on your code? Why are you summing the 3 parallel queues total time of processing together? Those processes occur in parallel, so I am uncertain what the sum of times is supposed to represent. Total time to clear all lines? That should be the nearly same number as one line with 3 people processing. So long as all 3 cashiers are constantly engaged, average wait time per customer for the entire system must remain unchanged independent of the queueing system used. Even a LIFO model for processing customers will have the same mean wait time per customer.

I am also very curious why the total time to process 3000 customers with mean time 50 is not closer to 3000*50. Perhaps I have missed something on the technical side.

You need whole distribution of process time, not just mean for simulation.

Reply on news.ycombinator.com