4
$\begingroup$

In an M/M/1 queue, we know that inter-arrival times are exponentially distributed, and that service times are the same. What is the distribution of to-server inter-arrival times (aka service start times)? Put another way, what is the distribution of times between when a server starts helping a customer?

Some intuition:

if $\lambda \ll \mu$, then there is rarely a wait, and the server just experiences arrivals at the same rate as arrivals to the queue.

if $\lambda \approx \mu$, then the server is almost always busy and experiences arrivals at the same rate of service/arrivals.

However, when $\lambda < \mu$, there will be cycles where customers arrive to both empty and occupied lines. So, the server will at times see the true arrival rate $\lambda$, and at other times, arrivals to them will be $\mu$

Burke's Theorem shows that the distribution of departure time from a server is the same as arrival times. One proof this theorem use weighted sums, and the probability that the server is busy. I think there may be a similar approach to solve this problem.

$\endgroup$
  • $\begingroup$ Welcome to the site. Could you spell out what an M M 1 queue is? $\endgroup$ – Peter Flom Dec 12 '12 at 11:24
  • 1
    $\begingroup$ @Peter Flom: Is a queuing system with one 1 server and 1 queue where services times are $exp(\lambda)$ and the interarrival times are $exp(\mu)$. $\endgroup$ – Orlando Mezquita Dec 12 '12 at 15:02
  • $\begingroup$ Yes, that's correct. That is an M/M/1 queue. $\endgroup$ – DG1 Dec 12 '12 at 15:38
4
$\begingroup$

It's a mixture of three distributions, and can be found pretty easily by brute force, if one allows oneself to handwave over some important details (e.g., "is $\lambda < \mu$").

Let $n$ be the number of customers in the system; $n=0$ means no-one is being served or waiting, $n=1$ means one customer is being served but no-one is waiting, etc. Let $p_n$ be the steady-state (assumed from here on) probability that $n$ customers are in the system.

Clearly, if $n=0$, the time $t$ to the next service start is distributed $f(t|n=0) = \text{Exp}\{\lambda\}$, and if $n \geq 2$, the time to the next service start is distributed $f(t|n \geq 2) = \text{Exp}\{\mu\}$, since the next service will start immediately upon completion of the current one. If $n=1$, the time to the next service start is the maximum of the time to the next arrival and the time to the next service completion. This latter distribution has the following easily-derived form:

$f(t|n=1) = \lambda e^{-\lambda t} + \mu e^{-\mu t} - (\lambda + \mu)e^{-(\lambda+\mu)t}$

The mixture probabilities correspond to $p_0$, $1-p_0-p_1$, and $p_1$ respectively. The probabilities $p_0$, $p_1$, and $1-p_0-p_1$ can be written as:

$$p_0 = \left[\sum_{k=0}^{\infty}\left({\lambda \over{\mu}}\right)^k\right]^{-1} = 1 - {\lambda\over{\mu}}$$ $$p_1 = \left({\lambda \over{\mu}}\right)p_0 = {\lambda\over{\mu}} - \left({\lambda\over{\mu}}\right)^2$$ $$1-p_0-p_1 = \left({\lambda\over{\mu}}\right)^2$$

Writing the whole thing out, with some rearranging of terms, gives:

$$f(t) = {\lambda(\mu-\lambda)\over{\mu}}\left(e^{-\lambda t} + e^{-\mu t}\right) + \left({\lambda\over{\mu}}\right)^2\left(\lambda e^{-\lambda t} + \mu e^{-\mu t} - (\lambda+\mu)e^{-(\lambda+\mu)t}\right)$$

My source for probability formulae was Kleinrock, Queuing Systems.

Edit: The derivation of $f(t|n=1)$ is below, written as the derivation of the maximum of two independent exponential variates $x \sim \text{Exp}\{\lambda\}$ and $y \sim \text{Exp}\{\mu\}$. The corresponding CDFs are $F_X(x) = 1-\exp{\{-\lambda x\}}$ and $F_Y(y) = 1-\exp{\{-\mu y\}}$.

We'll approach this using the "cumulative distribution function technique". Note first that the statement "$\max(x,y) \leq t$" is equivalent to "$x \leq t$ and $y \leq t$". The probability that $\max(x,y) \leq t$ is just the product of the probabilities that $x \leq t$ and $y \leq t$ (as $x$ and $y$ are independent.) Writing this out gives:

$$F_{\max(x,y)}(t) = \left(1-e^{-\lambda t}\right)\left(1-e^{-\mu t}\right) = 1 - e^{-\lambda t} - e^{-\mu t} + e^{-(\lambda+\mu) t}$$

and taking the derivative with respect to $t$ gets you to the density function.

$\endgroup$
  • $\begingroup$ This is really helpful! I was thinking the solution would look something like this... what I could not figure out however was the distribution f(t|n=1). I still don't really understand how you arrived at that. Could explain that bit a little more. $\endgroup$ – DG1 Dec 12 '12 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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