1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Pradipta
    Commented Nov 11, 2010 at 15:25
  • $\begingroup$ Granted. Would you care to expand on this "something completely different"? $\endgroup$
    – Did
    Commented Nov 11, 2010 at 15:59
  • $\begingroup$ 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. $\endgroup$
    – Pradipta
    Commented Nov 11, 2010 at 16:33
  • $\begingroup$ 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. $\endgroup$
    – Pradipta
    Commented Nov 13, 2010 at 0:38

You must log in to answer this question.

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