Stability of discrete queue (new twist)

2010-11-11T11:35:46Z

Hi, I am new to queueing theory. I am interested in a question that I feel should be fairly basic, yet I haven’t really found a clear solution to it. Hopefully somebody here can help me.

We have a single server system, with an infinite queue, and with slotted time. At the beginning of every slot, a number of jobs arrive in the queue. The number of jobs $X$ is a random variable over the non-negative integers, with expectation $\mu$. After these jobs arrive, the server processes some jobs, which leave the queue. The number of jobs the server can process is a Bernoulli random variable $C$. That is, $C = 1$ with some probability $p$, and $0$ otherwise. To state what is probably obvious, if $C = 1$, the queue size is reduced by $1$ (if the queue was non-empty), and the queue remains unchanged if $C= 0$ or if the queue was empty. Both $C$ and $X$ are iid across time.

I want to understand the conditions under which this system is stable. By stable, I mean $\sup_{n \geq 1} E(Q(n)) < M$ for some finite $M$, where $Q(n)$ is the size of the queue at the beginning of time slot $n$, and $E(Q(n))$ is the expectation of $Q(n)$. I am not necessarily interested in a explicit value of $M$, just knowledge that it is finite is fine. I am hoping that the condition would be $\mu < p$ or something like that.

I realize that probably some sort of assumption on the distribution on $X$ is needed, which is fine. Assumptions like finite variance, strong law of large numbers, or even large deviation inequalities are OK with me.

Edit: Additionally, I am interested in what would happen if $E(C)$ was not a fixed $p$ but $p(t)$ (ie, a function of time). Here $p(t)$ itself is a random variable where $E(p(t)) = p$ for all $t$, and $p(t)$ converges to $p$ almost surely. This question appears to be related to "time dependent Markov chains". However, the references for time dependent Markov chains that I could find do not consider $p(t)$ to be a random variable it self (such as http://portal.acm.org/citation.cfm?id=990738.990783). Asmussen’s book talks about time dependent properties of Markov chains, but that appears to be quite different.

Answer by Didier Piau for Stability of discrete queue (new twist)

2010-11-11T14:38:03Z

You are asking the queue $Q\to (Q+Y)^+$ to be ergodic, where $Y$ is your $X-C$, and the stationary distribution of this queue to be integrable. Ergodicity requires that $E(Y)<0$, i.e. $\mu < p$. Integrability holds as soon as $Y$ (or, equivalently, $X$) is square integrable.

Amongst many other places, you might want to check example I.5.7 of Applied Probability and Queues by Søren Asmussen. (Are you sure this is not HW?)

Stability of discrete queue (new twist) - MathOverflow

Stability of discrete queue (new twist)

Answer by Didier Piau for Stability of discrete queue (new twist)