Stability of discrete queue (new twist) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T00:15:14Z http://mathoverflow.net/feeds/question/45683 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45683/stability-of-discrete-queue-new-twist Stability of discrete queue (new twist) Pradipta 2010-11-11T11:35:46Z 2010-11-12T15:52:18Z <p>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.</p> <p>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.</p> <p>I want to understand the conditions under which this system is stable. By stable, I mean $\sup_{n \geq 1} E(Q(n)) &lt; 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 &lt; p$ or something like that.</p> <p>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.</p> <p><strong>Edit:</strong> 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 <a href="http://portal.acm.org/citation.cfm?id=990738.990783" rel="nofollow">http://portal.acm.org/citation.cfm?id=990738.990783</a>). Asmussenâ€™s book talks about time dependent properties of Markov chains, but that appears to be quite different.</p> http://mathoverflow.net/questions/45683/stability-of-discrete-queue-new-twist/45701#45701 Answer by Didier Piau for Stability of discrete queue (new twist) Didier Piau 2010-11-11T14:38:03Z 2010-11-11T16:00:01Z <p>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)&lt;0$, i.e. $\mu &lt; p$. Integrability holds as soon as $Y$ (or, equivalently, $X$) is square integrable. </p> <p>Amongst many other places, you might want to check example I.5.7 of <i>Applied Probability and Queues</i> by Søren Asmussen. (Are you sure this is not HW?)</p>