Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a simple queue model like the one described in http://en.wikipedia.org/wiki/M/M/1_model. The article states what the expected waiting time is before a request enters the queue.

Assuming that the actual queue length is unknown, does the expected value of "time left to wait" for a given request change over time while the request is in the queue?

Clarification: is it true that the expected time until a request is served stays constant, regardless of how long it has already spent in the queue?

share|improve this question
    
R. Pandharipande has frequently expressed the view that, after a wait of x minutes to be served in a restaurant, the expected time f(x) remaining before actually being served is nonconstant, and indeed -f(x) is a unimodal function... –  Michael Thaddeus Jun 3 '10 at 15:22

2 Answers 2

up vote 2 down vote accepted

I am not entirely sure what you are asking but ...

The model you reference in the wiki article has a memory-less distribution for waiting time and inter-arrival time. Thus, the total time for a request to get processed is not dependent on time.

share|improve this answer
    
What I was really trying to ask is whether a request "loses out" by leaving the queue and joining it later, assuming that being in the queue has a cost. The way I interpret your answer is that it doesn't matter how long a request has already spent in the queue; the expected time until it's served stays constant. Correct? –  romkyns Jun 2 '10 at 12:41
    
Well the cost associated with waiting in the queue before leaving is sunk. So, from an economic standpoint, the only relevant cost to consider in order to decide whether to leave or not is the expected time to be served if the request chooses to leave the queue and re-join later vis-a-vis the expected time to be served if the request chooses not to leave the queue. For an M/M/1 model, the expected time in both situations is the same and hence the request does not lose by leaving the queue. –  Anon Jun 2 '10 at 13:12
    
The memoryless distribution is the waiting time for one customer to be served. If one knows, e.g. the average queue length, but one does not know the current queue length, what is the distribution of the waiting time until one gets served? I wouldn't think that would be the same as the distribution of the waiting time for just one customer. My guess is it's not memoryless. –  Michael Hardy Jun 2 '10 at 17:43
    
The easiest way to check this is to do a small simulation. See also the wiki article for stationary behavior of an M/M/1 queue which suggests that distribution of waiting time is not dependent on queue length. I am too lazy right now to lay out rigorous arguments. :-) –  Anon Jun 2 '10 at 19:23

M/M/1 model assumes Poisson arrivals + exponentially distributed service times. Confirming previous answer - if you're waiting in the queue and there is a person (product) being served right now, the expected finishing time for that person from now on $E(X|X>t)=E(X)+t$.

Overall the formula for expected waiting time in any queue model (1 server, infinite buffer...) is:

$EW_q = \rho * ES * (c(A)^2 + c(S)^2) / ( 2*(1-\rho) )$

$\rho = ES/EA$, Expected Service time / Expected Arrivals in 1 time unit.

$c(S)^2 = E(S^2) / (ES)^2$ - variation of S (service time), the same for A (Arrival rate).

$\rho<1$ otherwise the queue will grow -> infty.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.