1
$\begingroup$

The final theorem in Chapter 19 of Meyn and Tweedie's Markov Chains and Stochastic Stability tells us that if the mean inter-arrival time $\lambda$ of a GI/G/1 queue is greater than its mean service time $\mu$, then the queue is positive Harris recurrent.

Question: What stability results are known for a continuous-time GI/G/1 queue for which $\lambda=\mu$, and in which the variances of the inter-arrival time and service time random variables are positive? Is it known that such a queue cannot be positive Harris recurrent? Regular?

The Lyapunov function used in Meyn-Tweedie, which is an expected hitting time, is not going to work for $\lambda=\mu$.

I searched in Morozov and Delgado's survey paper, which claims that "stability conditions of the classical GI/G/m queue are well known", and in other surveys, but found no mention of the $\lambda=\mu$ case there.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hi, Daniel. Unfortunately, I don't have it at hand at the moment, but you might look in S. Asmussen, Applied Probability and Queues, 2nd ed., Springer Applications in Mathematics. If I recall, Chapter X discusses (steady state) properties of GI/G/1 and I believe Chapter XII has a brief section on GI/G/m. In both places, some results on $\lambda =\mu$ are provided ($\rho = 1$ in the book's notation). Sorry I can't provide a more precise pointer at the moment. $\endgroup$
    – cardinal
    Jun 10, 2014 at 18:53
  • $\begingroup$ Thanks. This seems to be it (although the proofs are tremendously condensed!). Do you want to post this as an answer and I can accept it? $\endgroup$
    – Daniel Moskovich
    Jun 11, 2014 at 11:18

1 Answer 1

Reset to default
1
$\begingroup$

After some research I found the answer; essentially contained in cardinal's comment. Please let me know if you have anything to add.

For the Lindley process $Z_{n+1} = \max(0, Z_n+ U_n)$ with $\rho=1$, two results seem to be known:

  1. $\frac{Z_n}{\sqrt{n}}$ converges to a normal random variable with mean $0$ and variance $\sigma^2=\mathrm{Var}(U_n)$, where $\sigma\in(0,\infty)$. This is in Billingsley, Chapter 2, cited slightly inaccurately in Asmussen (condition $\sigma>0$ omitted), Proposition X.1.2.
  2. The expected first hitting time is 1 if the interarrival time equals the service time with probability 1 (`deterministic case'), and is infinite otherwise. This is in Kalashnikov, Mathematical Methods in Queueing Theory Section 5.3.3. It is mentioned slightly inaccurately in Asmussen, Proposition X.1.3.
Improve this answer
$\endgroup$

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.