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

P

From the second equation we have P_{1} = r P_{0} with
*r=p/q*, while the first gives

From this relation we can recursively solve for P

P

P

. . .

The value *P _{0}* 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/a ^{2}*
and on the columns those of

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 *P _{N}* could
be expressed in close form as

Therefore, the sum of all the *P _{N}* contains infinitely
many constant terms

What is the mistake in the above reasoning ?

Hint.

The solution is *P _{N} = (1-r) r^{N}*.

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
*P _{k}* to

Working the way back, it's easy to find that

Marco Corvi - 2013