3
$\begingroup$

My question is the following.

An $M/M/1$ queue has arrival rate $\nu$ and service rate $\mu$, where $\rho = \nu/\mu < 1$. Show that the sojourn time (ie the queueing time plus the service time) of a typical customer is exponentially distributed with parameter $\mu - \nu$. (Call this time $T$.)

Now, we're looking at a 'typical' customer, so we consider the chain in equilibrium (eg justified by the PASTA property). Now, I am able to solve this question. For example, one simply observes that if a customer joins a queue of size $j$, then she waits $\Gamma(j+1,\mu)$. Plus in the numbers, including the cdf for $\Gamma(j+1,\mu)$, and bash out some algebraic manipulation.

I'm interested in a more refined approach, however. The cdf for $\Gamma(j+1,\mu)$ isn't so nice, I feel. Of course, since $j$ is an integer here, we can just see it as a sum of Poisson probabilities -- alternatively, one could derive the waiting time when the queue has size $j$ like this.

I'd like to prove this lemma by showing that the time $T$ has the memoryless property. We then need only calculate the expectation. The expectation of $\Gamma(\alpha,\beta) = \alpha/\beta$ for any $\alpha$ and $\beta$, so it's fairly straightforward to show that $E(T) = 1/(\mu - \nu)$. So my issue is the following.

Show directly that the time $T$ has the memoryless property.

$\endgroup$
2
$\begingroup$

The key to solving this problem painlessly is to observe that in equilibrium, the number of customers in the system is distributed as a geometric random variable with "success probability" $1-\rho$: $$\Pr[k \text{ customers}] = \rho^k (1-\rho).$$ So an equivalent way to state your problem is the following claim:

Let $\mathbf N \sim \text{Geometric}(p)$ and let $\mathbf X_1, \mathbf X_2, \mathbf X_3, \dots$ be i.i.d. $\text{Exponential}(\lambda)$ random variables. Let $$\mathbf S =\sum_{k=1}^{\mathbf N} \mathbf X_k.$$ Then $\mathbf S \sim \text{Exponential}(\lambda p).$

(In our case, $p = 1-\rho = 1 - \frac{\nu}{\mu}$ and $\lambda = \mu$, so $\lambda p = \mu - \nu$ as desired.)

In this formulation, even the direct algebraic approach to the problem is not too bad. There's also a fairly clean indirect algebraic approach: in general, when dealing with a random sum of random variables, the identity $$ \widetilde{\mathbf S}(s) = \widehat{\mathbf N}(\widetilde{\mathbf X}(s)) $$ holds, where $\widetilde{\mathbf S}$ and $\widetilde{\mathbf X}$ are Laplace transforms and $\widehat{\mathbf N}$ is a $z$-transform. In this particular case, once you plug in the relevant formulas, the result falls out.

But there's also a completely non-algebraic approach along the lines of the solution you want. Interpret $\mathbf X_1, \mathbf X_2, \mathbf X_3, \dots$ as waiting times in a Poisson process with rate $\lambda$. Then $\mathbf S$ can be interpreted as a waiting time in a process which filters each of the events in that Poisson process, keeping them only with probability $p$. By Poisson splitting, the filtered process is itself a Poisson process with rate $\lambda p$, and therefore $\mathbf S$ is exponential with rate $\lambda p$, as desired.

$\endgroup$
  • $\begingroup$ Ah, Poisson splitting is the exact interpretation that I wanted! That's excellent, thank you :) -- if only I could '+2'! $\endgroup$ – Sam T Nov 14 '17 at 14:01

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.