1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented May 19, 2014 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$
    – Federico Poloni
    Commented May 24, 2014 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$
    – Federico Poloni
    Commented May 24, 2014 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .