AN INFINITE QUEUE


Consider a queue that can hold infinitely many items, and there is a producer that puts items on the queue at a rate p, and a consumer that takes them off (one by one) at a rate q. That is there is a probability p that the number of items on the queue increases by one in the unit time, and a probability q that it decreases by one, provided it is positive of course.

In the steady state situation the probability that there are N items on the queue can be written

PN = p PN-1 + (1-p-q) PN + q PN+1
P0 = (1-p) P0 + q P1

From the second equation we have P1 = r P0 with r=p/q, while the first gives

PN = a PN-1 + b PN-2
where a=(p+q)/q and b=-p/q. Notice that a+b=1.
From this relation we can recursively solve for PN with N=2,3,...
P2 = (r a + b) P0
P3 = (r a2 + a b + r b) P0
P4 = (r a3 + a2 b + 2 r a b + b2) P0
. . .

The value P0 can be determined by requiring that the sum of all the probabilities gives 1.

We can arrange the coefficients in these relations in a table. On the row we put the powers of B=b/a2 and on the columns those of a. Furthermore each column has two entries: the first is multiplied by r, the second by a. 

                 B^0    B^1    B^2    B^3    B^4    ...
      P_1   a^0  1 0
      P_2   a^1  1 0    0 1
      P_3   a^2  1 0    1 1
      P_4   a^3  1 0    2 1    0 1
      P_5   a^4  1 0    3 1    1 2
      P_6   a^5  1 0    4 1    3 3    0 1
      P_7   a^6  1 0    5 1    6 4    1 3
      ...

It is easy to show that the coefficient in column j of row i is given by the sum of that just above it (column j row i-1) and that two rows above, one column to the left (column j-1 row i-2).

The sum on each row can be carried out and the PN could be expressed in close form as P0 times a function of r, a and b. However the expression is not very illuminating. Without doing this it is not hard to see that the coefficients are the binomial coefficients, arranged along the diagonal. For example, P4, P5, P6, and P7, have in columns 0, 1, 2, 3 the term r a3(1+aB)3 that is r (a+b)3, which is just r because a+b=1. The terms not containig r, also give rise to powers of a+b, this time multiplied by a.

Therefore, the sum of all the PN contains infinitely many constant terms r and a, and it diverges. But this is impossible as the sum (times P0) should be 1.

What is the mistake in the above reasoning ?


Hint.
The solution is PN = (1-r) rN.

Now consider a finite queue of length N. Again the producer has a rate p and the consumer a rate q. The equations that relate Pk to Pk-1 and Pk-2 remain the same up to K=N. The last equation changes because the queue cannot hold more than N items, and when it is full the producer cannot put any more item on it. Therefore the last equation becomes

PN = r PN-1

Working the way back, it's easy to find that Pk = r Pk-1. Finally requiring that the sum of the probabilities is 1, one gets
Pk = rk (1-r) / (1 - rN+1)
In the limit for N going to infinity, we recover the solution to the initial problem.

Marco Corvi - 2013