Now I am explaining the transient solution of a finite birth-death process. So using
these, one can find out the transient solution of the birth-death process which I have discussed
today's class M/M/1/N, M/M/c/K and M/M/c/c also. So the logic is same, that means you
have a birth death process with a finite state space. Therefore, the queue matrix is going
to be a degree whatever be the number of states in the state space.
And it is going to be a tridiagonal matrix and you know the lambda n’s and mu n’s,
birth rates as well as the death rates. And the birth rates and death rates are going
to be different for these three models. There are many literatures over the transient solution
of finite birth-death process started with Murphy and O'Donohoe, he uses the polynomial
method. And in 1978 Rosenlund also found the transient solution for the finite BDP using
again the different polynomial methods.
And Chiang in 1980, he made a matrix method to this transient solution. Then later Van
Doorn gave the solution using spectral representation method. And Nikiforov et al 1991, he also
gave the transient solution using orthogonal polynomial. And later Kijima also gave the
solution using Eigenvalues method. So these are all the literatures for getting the transient
solution of a finite birth-death process.
And here I am going to explain how to get the transient behaviour of M/M/1/N queue in
a very simplest form, even though there are this many literature and many more literatures
for the finite birth-death process. But here I am explaining the overview of how to get
the transient behaviour of M/M/1/N queue and this is by O. P. Sharma and U. C. Gupta. It
appears in Stochastic processes and their applications, volume 13-1982.
So what this method work you start with the forward Kolmogorov equation.
That is pi t, pi dash t, that is started with pi dash of t, that is equal to pi of t into
Q matrix, where pi is the matrix and pi dash is the derivatives and Q is the infinitesimal
matrix. Take a forward Kolmogorov equation, then use the Laplace transform for each pi
n of t you take the, sorry here the pi dash of t is the vector, it is the distribution
of a X(t).
Therefore, this is a vector and this is a vector and Q is a matrix, not the matrix which
I said wrongly. So this is a vector and this is a vector and Q is a matrix. So take a Laplace
transform for each probability where the pi n of t, that is nothing but, so the pi of
t is a vector that started with pi 0 of t, pi one of t and so on, pi n of t, where pi
n of t is nothing but what is the probability?
That the same notation that I started when I discussed the continuous Markov chain, what
is the probability that n customers in the system at time t, it is a conditional probability
distribution. So pi n of t is the probability that n customers in the system at time t,
and pi n of t you get the vector and you make a forward Kolmogorov equation pi dash of t
is equal to pi of t times Q.
And take a Laplace transform, for each pi n of t that exist, because this is a probability
and the conditions for the Laplace transform of this function satisfies you can cross check.
Therefore, you are taking a Laplace transform, so this is going to be a function of theta.
Before taking a Laplace transform, you need an initial condition also. So at time zero,
you assume that no customer in the system, at time zero.
Now customer in the system, that means X(0) is equal to zero. Therefore, that probability
is going to be one and all other probabilities are going to be zero. That is the initial
probability vector. So use this initial probability vector and apply it over the forward Kolmogorov
equation taking a Laplace transform, you will get the system of algebraic equation.
Since you are using the pi 0 of zero is equal to one, you will get the first equation with
the term one and all other terms are going to be zero. And you know the Laplace transform
of derivative of the function. So you substitute, you take a Laplace transform over the forward
Kolmogorov equation with this initial condition as well as pi n of zero is equal to zero for
n not equal to zero. So you will have an algebraic equation that is n plus one algebraic equations
as a function of theta.
You have to solve this algebraic equation system of algebraic equation in terms of theta.
Once you are able to solve these and take an inverse Laplace transform and that is going
to be the system size at any time t. You can start saying that this is going to be of the
solution A times alpha n and B times beta power n, where alpha and beta are given in
this form, where alpha is equal to this plus something and beta is equal to minus something,
minus square root of this expression.
So you have a alpha as well as beta and now what do you want to find out, if you find
out the constant A and B you can get Laplace transform of pi n of t. Then you take an inverse
Laplace transform and you get the pi n of t.
So for that you need the determinant of matrix of this form and here this is nothing but
all these values are death rates, these are all the birth rates. And this is corresponding
to the M/M/1/N model. And the same logic goes for the transient solution for the M/M/c/K
as well as M/M/c/c. So instead of this lambda’s and mu’s you will have a corresponding birth
rates and death rates.
But ultimately you will have a N+1 matrix determinant as a function of theta. And since
these three models are going to be a irreducible, positive recurrent, the stationary probability
and the limiting probabilities exist. Therefore, this determinant going to be always of the
form theta times some other function as the degree, as a polynomial of degree N in the
function of theta. So this theta is corresponding to the stationary probabilities or the limiting
probabilities.
Therefore, always you can get the N +1 order matrix determine that is theta times the polynomial
of degree N is a function of theta. For the M/M/1/N model the birth rates are lambda and
the death rates are mu and you can get this polynomial also in the form of product. The
product of theta plus lambda plus mu times alpha of N comma k square root of lambda mu,
where alpha of N, k is nothing but the k roots of N-th degree Chebyshev’s polynomial of
second kind.
There is a relation between the birth-death process with the orthogonal polynomial. For
instant, the M/M/1/N model the finite capacity M/M/1/N model, the corresponding orthogonal
polynomial for this birth-death process is the Chebyshev’s polynomial of the second
kind. Similarly, you can say the orthogonal polynomial corresponding to the M/M/c/c model
that is a Charlier polynomial, like that we can discuss the corresponding orthogonal polynomial
for the finite capacity birth-death processes.
So here for the M/M/1/N model this is related to the Chebyshev’s polynomial of second
kind, that is U n of x. So once you are able to get the Chebyshev’s polynomial roots
and that roots is going to play a role in the product form and that is going to be the
polynomial. Note that this polynomial has a distinct real factor.
Therefore, you can use the partial fraction, then you can take the inverse Laplace transform
to finally you can get the pi n of t. I am skipping all the simplification part and main
logic is this N+1 th order matrix determinant and that determinants has the factors. And
those factors are related to the Chebyshev’s polynomial roots. So once you use all those
logics and use the partial fraction.
Then finally you take the inverse Laplace transform, for lambda is not equal to mu,
you will get steady state or stationary probabilities plus this expression and this is the function
of t, e power minus lambda plus mu times t plus two times square root of lambda mu times
t cos of r by pi n plus one and denominator this expression multiplied by this.
And here this result is related to the initial condition zero, that means at time zero the
system is empty. If the system is not empty, then you will have a one more expression here
sin of this minus another term. So that is, you will have a little bigger expression for
system size is not empty. And this theta times this, that will give the corresponding partial
fraction and so on inverse Laplace it will give the terms which is independent of t and
that is related to the steady state probability.
Because if you put t tends to infinity and these quantities are greater than zero. So
as t tends to infinity the whole terms will tends to zero. Therefore, as the t tends to
infinity, we will have pi n of t is equal to this expression and this is valid for rho
is less than one. With that condition rho is less than one, those terms will tend to
zero and you will have only this term and that is going to be the steady state or limiting
probabilities for M/M/1/N model.
If you make also n tends to infinity along with the t tends to infinity, you will have
pi n's that is the steady state probability for the M/M/1 infinity model. So even though
I have explained M/M/1/N transient solution in a brief way. But the same logic goes for
the M/M/c/c model also, the only difference is this determinant has the lambda’s and
instead of mu’s you will have mu2, mu3, and so on.
And instead of the Chebyshev’s polynomial, you will land up with the Charlier polynomial.
But there is a difference between this M/M/1/N model and M/M/c/c model transient solution.
Since the Chebyshev’s polynomial has a closed form roots, you can find out the factors.
So here these are all the factors and you know the factors as well as you can get the
closed form expression for the M/M/1/N transient solution where as Charlier polynomial does
not have a closed form roots.
Therefore, you will land up with the numerical result for the transient solution for M/M/1/N,
M/M/c/c model.
In the case of a continuous time Markov chain, that is a finite source Markovian Queuing
models. This model is also known as a machine repairman model and you can think of these
PCs are nothing but machines and this is nothing but the repairman. And here the scenario is
we have a K PCs and each PC can give a print job and the inter arrival of print jobs that
is exponentially distributed by the each PC.
Therefore, the print jobs that is follow a arrival process that is a Poisson process
with the parameter lambda from each PC. And once the print jobs come into the printer,
it will wait for the print. And the time taken for the each print that is also exponentially
distributed with the parameter mu.
And here there is another assumption before the first print is over by the same PC, it
cannot give another print command. Therefore, after the print is over by any one particular
print job of any PC, then these things will go back to the same thing, then with the inter
arrival of print jobs generated that is exponentially distributed, then the print job can come into
the printer. So with these assumptions you can think of the Stochastic process.
That means the number of print jobs at any time t in the printer that is going to form
a Stochastic process and with the assumption of inter arrival of print jobs, that is exponential
and actual printing job that is exponentially distributed and so on. Therefore, this is
going to be a birth-death process, with the birth rates or K times lambda or K minus one
times lambda and so on, where as the death rates that is mu, because we have only one
repair.
So this is nothing but system size number of jobs in the print job, printer. So therefore
that varies from zero to K, because we are making the assumption more than one print
job cannot be given by the same PC before the print is over. And from zero to one, the
arrival rate will be any one of the K PCs. Therefore, the arrival rate is K times lambda
and already one print job is there in the system printer.
Therefore, out of K minus one PCs one print job can come, therefore the inter arrival
time that is exponentially distributed with the parameter K minus one times lambda and
so on. So this is a way you can visualise the birth rates, where as the death rates
are mu. Once you know the birth rates and death rates you can apply the birth-death
process concept to get the steady state probabilities.
So here we are getting the pi i's in terms of pi 0, and using the summation of pi i is
equal to one, you are getting the pi 0 also. And once you know the steady state probability,
you can get the all other measures. So the difference is in this model it is a finite
source, therefore the birth rates are the function of, it is the state dependent birth
rates where as the death rates are mu’s only. Simulation of a Queuing model, I will
do it in the next lecture.
The summary of today's lecture, I have discussed the simple Markovian queueing models other
than M/M/1 infinity, that I have discussed in the previous lecture and stationary distribution
and all the other performance measures using the birth-death process we have discussed
for these queueing models and finally I discussed the finite source Markovian queueing model
also.
These are all the reference books. Thanks.