# Stability of discrete queue (new twist)

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.

-

## 1 Answer

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?)

-
Thanks for the suggestion, I’ll check it out. No, it’s not HW. I gather from your comment that this question is, as I suspected, rather basic. It’s just that I don’t work on this normally and stumbled on this question through something completely different. – Pradipta Nov 11 '10 at 15:25
Granted. Would you care to expand on this "something completely different"? – Did Nov 11 '10 at 15:59
Graph theory, with an eye on modeling networks. But not in a "stochastic" way my question suggests, this question suggested itself later. Sorry if this is vague, I am playing around with ideas and don’t have a explicit problem I can state. – Pradipta Nov 11 '10 at 16:33
Thanks again for the reference. In the edition of the book I found, it was actually example 1.5.5, but anyway, it was the right one. – Pradipta Nov 13 '10 at 0:38