I "believe" that generator, $\bf W$, of the waiting time distribution for the M/M/1 queue is given by the following (I'm not sure if this is even correct):

${\bf W} =\left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0\\ \mu & -\mu & 0 & 0 & 0\\ 0 & \mu & -\mu & 0 & 0 \\ 0 & 0 & \mu & -\mu & \dots \end{array} \right)$

But the question I have is that I am unclear how to solve this Markov chain. That is, I'm looking for an analytic solution to

$\bf pW=0$

I think $\bf p$ should look something like

${\bf p} = [1−ρ,…],$

but again, I am unclear how to solve these problems.

Thanks for help in these matters.


Almost. The generator is ${\bf Q} =\left( \begin{array}{ccccc} -\lambda & \lambda & 0 & 0 & 0\\ \mu & -(\lambda+\mu) & \lambda & 0 & 0\\ 0 & \mu & -(\lambda+\mu) & \lambda & 0 \\ 0 & 0 & \mu & -(\lambda+\mu) & \dots \end{array} \right), $ where $\lambda$ is the arrival rate and $\mu$ the departure. If $\mu>\lambda$ (more people leave the queue than arrive), the chain is recurrent and the invariant distribution is an exponential distribution, i.e., $p_k=(1-\rho)\rho^k$, and $\rho=\frac{\mu}{\lambda}$. If $\rho> 1$ (resp. $=1$), the queue is transient (resp. null recurrent) and there is no stationary distribution.

I mostly know these topics from their block-matrix case, which is treated for instance in Latouche, Ramaswami, Introduction to matrix analytic methods in stochastic modeling. Give it a look, but the book might be overkill if you only care about the scalar case.

  • $\begingroup$ Maybe I'm not understanding something, but this looks like the infinitesimal generator for the M/M/1 queue. I found this paper here: dspace.mit.edu/bitstream/handle/1721.1/2292/… - On pages 11-12, they give the infinitesimal generating function for the waiting time of the ∑Ph/Ph/1 queue. What are your thoughts? $\endgroup$
    – PiE
    May 19 '14 at 8:48
  • $\begingroup$ @PMF You are right, I totally missed the "waiting time" part. I must admit I am not familiar with this definition: the waiting time is a random variable, not a stochastic process, and it is not immediately clear to me what is meant by "generator" here. Does it mean that its distribution is a matrix exponential one with that matrix as the exponent? $\endgroup$ May 24 '14 at 9:02
  • $\begingroup$ @PMF In any case, it seems to me that the solution you are looking for is $[1,0,0,0,\dots]$: from the equation corresponding to the first column of $W$ you get $p_2=0$, then from the second column $p_3=0$, and so on. $p_1$ remains indeterminate, and for the usual normalization $p\underline{\mathbf{1}}$ to hold we need $p_1=1$. $\endgroup$ May 24 '14 at 9:04

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.