WEBVTT
Kind: captions
Language: en
00:00:00.149 --> 00:00:08.849
Now I am explaining the transient solution
of a finite birth-death process. So using
00:00:08.849 --> 00:00:15.259
these, one can find out the transient solution
of the birth-death process which I have discussed
00:00:15.259 --> 00:00:23.759
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
00:00:23.759 --> 00:00:28.460
have a birth death process with a finite state
space. Therefore, the queue matrix is going
00:00:28.460 --> 00:00:35.650
to be a degree whatever be the number of states
in the state space.
00:00:35.650 --> 00:00:40.360
And it is going to be a tridiagonal matrix
and you know the lambda n’s and mu n’s,
00:00:40.360 --> 00:00:45.460
birth rates as well as the death rates. And
the birth rates and death rates are going
00:00:45.460 --> 00:00:54.820
to be different for these three models. There
are many literatures over the transient solution
00:00:54.820 --> 00:01:03.020
of finite birth-death process started with
Murphy and O'Donohoe, he uses the polynomial
00:01:03.020 --> 00:01:11.830
method. And in 1978 Rosenlund also found the
transient solution for the finite BDP using
00:01:11.830 --> 00:01:15.390
again the different polynomial methods.
00:01:15.390 --> 00:01:22.280
And Chiang in 1980, he made a matrix method
to this transient solution. Then later Van
00:01:22.280 --> 00:01:34.229
Doorn gave the solution using spectral representation
method. And Nikiforov et al 1991, he also
00:01:34.229 --> 00:01:42.750
gave the transient solution using orthogonal
polynomial. And later Kijima also gave the
00:01:42.750 --> 00:01:50.440
solution using Eigenvalues method. So these
are all the literatures for getting the transient
00:01:50.440 --> 00:01:54.100
solution of a finite birth-death process.
00:01:54.100 --> 00:02:00.290
And here I am going to explain how to get
the transient behaviour of M/M/1/N queue in
00:02:00.290 --> 00:02:06.450
a very simplest form, even though there are
this many literature and many more literatures
00:02:06.450 --> 00:02:12.989
for the finite birth-death process. But here
I am explaining the overview of how to get
00:02:12.989 --> 00:02:19.041
the transient behaviour of M/M/1/N queue and
this is by O. P. Sharma and U. C. Gupta. It
00:02:19.041 --> 00:02:26.230
appears in Stochastic processes and their
applications, volume 13-1982.
00:02:26.230 --> 00:02:36.280
So what this method work you start with the
forward Kolmogorov equation.
00:02:36.280 --> 00:02:53.430
That is pi t, pi dash t, that is started with
pi dash of t, that is equal to pi of t into
00:02:53.430 --> 00:03:03.400
Q matrix, where pi is the matrix and pi dash
is the derivatives and Q is the infinitesimal
00:03:03.400 --> 00:03:11.219
matrix. Take a forward Kolmogorov equation,
then use the Laplace transform for each pi
00:03:11.219 --> 00:03:17.239
n of t you take the, sorry here the pi dash
of t is the vector, it is the distribution
00:03:17.239 --> 00:03:18.639
of a X(t).
00:03:18.639 --> 00:03:25.120
Therefore, this is a vector and this is a
vector and Q is a matrix, not the matrix which
00:03:25.120 --> 00:03:30.580
I said wrongly. So this is a vector and this
is a vector and Q is a matrix. So take a Laplace
00:03:30.580 --> 00:03:38.719
transform for each probability where the pi
n of t, that is nothing but, so the pi of
00:03:38.719 --> 00:03:51.409
t is a vector that started with pi 0 of t,
pi one of t and so on, pi n of t, where pi
00:03:51.409 --> 00:03:54.919
n of t is nothing but what is the probability?
00:03:54.919 --> 00:04:01.280
That the same notation that I started when
I discussed the continuous Markov chain, what
00:04:01.280 --> 00:04:10.260
is the probability that n customers in the
system at time t, it is a conditional probability
00:04:10.260 --> 00:04:16.889
distribution. So pi n of t is the probability
that n customers in the system at time t,
00:04:16.889 --> 00:04:22.140
and pi n of t you get the vector and you make
a forward Kolmogorov equation pi dash of t
00:04:22.140 --> 00:04:24.770
is equal to pi of t times Q.
00:04:24.770 --> 00:04:33.860
And take a Laplace transform, for each pi
n of t that exist, because this is a probability
00:04:33.860 --> 00:04:39.440
and the conditions for the Laplace transform
of this function satisfies you can cross check.
00:04:39.440 --> 00:04:45.639
Therefore, you are taking a Laplace transform,
so this is going to be a function of theta.
00:04:45.639 --> 00:04:51.259
Before taking a Laplace transform, you need
an initial condition also. So at time zero,
00:04:51.259 --> 00:04:55.240
you assume that no customer in the system,
at time zero.
00:04:55.240 --> 00:05:01.419
Now customer in the system, that means X(0)
is equal to zero. Therefore, that probability
00:05:01.419 --> 00:05:07.300
is going to be one and all other probabilities
are going to be zero. That is the initial
00:05:07.300 --> 00:05:15.810
probability vector. So use this initial probability
vector and apply it over the forward Kolmogorov
00:05:15.810 --> 00:05:22.180
equation taking a Laplace transform, you will
get the system of algebraic equation.
00:05:22.180 --> 00:05:26.550
Since you are using the pi 0 of zero is equal
to one, you will get the first equation with
00:05:26.550 --> 00:05:32.840
the term one and all other terms are going
to be zero. And you know the Laplace transform
00:05:32.840 --> 00:05:39.909
of derivative of the function. So you substitute,
you take a Laplace transform over the forward
00:05:39.909 --> 00:05:47.479
Kolmogorov equation with this initial condition
as well as pi n of zero is equal to zero for
00:05:47.479 --> 00:05:55.500
n not equal to zero. So you will have an algebraic
equation that is n plus one algebraic equations
00:05:55.500 --> 00:05:58.130
as a function of theta.
00:05:58.130 --> 00:06:04.980
You have to solve this algebraic equation
system of algebraic equation in terms of theta.
00:06:04.980 --> 00:06:10.599
Once you are able to solve these and take
an inverse Laplace transform and that is going
00:06:10.599 --> 00:06:19.680
to be the system size at any time t. You can
start saying that this is going to be of the
00:06:19.680 --> 00:06:26.509
solution A times alpha n and B times beta
power n, where alpha and beta are given in
00:06:26.509 --> 00:06:32.759
this form, where alpha is equal to this plus
something and beta is equal to minus something,
00:06:32.759 --> 00:06:35.129
minus square root of this expression.
00:06:35.129 --> 00:06:42.699
So you have a alpha as well as beta and now
what do you want to find out, if you find
00:06:42.699 --> 00:06:52.030
out the constant A and B you can get Laplace
transform of pi n of t. Then you take an inverse
00:06:52.030 --> 00:06:57.479
Laplace transform and you get the pi n of
t.
00:06:57.479 --> 00:07:08.680
So for that you need the determinant of matrix
of this form and here this is nothing but
00:07:08.680 --> 00:07:13.639
all these values are death rates, these are
all the birth rates. And this is corresponding
00:07:13.639 --> 00:07:19.750
to the M/M/1/N model. And the same logic goes
for the transient solution for the M/M/c/K
00:07:19.750 --> 00:07:25.860
as well as M/M/c/c. So instead of this lambda’s
and mu’s you will have a corresponding birth
00:07:25.860 --> 00:07:27.240
rates and death rates.
00:07:27.240 --> 00:07:39.020
But ultimately you will have a N+1 matrix
determinant as a function of theta. And since
00:07:39.020 --> 00:07:46.689
these three models are going to be a irreducible,
positive recurrent, the stationary probability
00:07:46.689 --> 00:07:52.770
and the limiting probabilities exist. Therefore,
this determinant going to be always of the
00:07:52.770 --> 00:08:02.930
form theta times some other function as the
degree, as a polynomial of degree N in the
00:08:02.930 --> 00:08:12.610
function of theta. So this theta is corresponding
to the stationary probabilities or the limiting
00:08:12.610 --> 00:08:13.610
probabilities.
00:08:13.610 --> 00:08:23.229
Therefore, always you can get the N +1 order
matrix determine that is theta times the polynomial
00:08:23.229 --> 00:08:32.050
of degree N is a function of theta. For the
M/M/1/N model the birth rates are lambda and
00:08:32.050 --> 00:08:41.730
the death rates are mu and you can get this
polynomial also in the form of product. The
00:08:41.730 --> 00:08:49.580
product of theta plus lambda plus mu times
alpha of N comma k square root of lambda mu,
00:08:49.580 --> 00:08:57.140
where alpha of N, k is nothing but the k roots
of N-th degree Chebyshev’s polynomial of
00:08:57.140 --> 00:08:58.410
second kind.
00:08:58.410 --> 00:09:05.540
There is a relation between the birth-death
process with the orthogonal polynomial. For
00:09:05.540 --> 00:09:14.080
instant, the M/M/1/N model the finite capacity
M/M/1/N model, the corresponding orthogonal
00:09:14.080 --> 00:09:19.130
polynomial for this birth-death process is
the Chebyshev’s polynomial of the second
00:09:19.130 --> 00:09:28.190
kind. Similarly, you can say the orthogonal
polynomial corresponding to the M/M/c/c model
00:09:28.190 --> 00:09:36.820
that is a Charlier polynomial, like that we
can discuss the corresponding orthogonal polynomial
00:09:36.820 --> 00:09:40.770
for the finite capacity birth-death processes.
00:09:40.770 --> 00:09:46.980
So here for the M/M/1/N model this is related
to the Chebyshev’s polynomial of second
00:09:46.980 --> 00:09:53.030
kind, that is U n of x. So once you are able
to get the Chebyshev’s polynomial roots
00:09:53.030 --> 00:09:58.130
and that roots is going to play a role in
the product form and that is going to be the
00:09:58.130 --> 00:10:08.200
polynomial. Note that this polynomial has
a distinct real factor.
00:10:08.200 --> 00:10:16.150
Therefore, you can use the partial fraction,
then you can take the inverse Laplace transform
00:10:16.150 --> 00:10:23.140
to finally you can get the pi n of t. I am
skipping all the simplification part and main
00:10:23.140 --> 00:10:32.730
logic is this N+1 th order matrix determinant
and that determinants has the factors. And
00:10:32.730 --> 00:10:38.640
those factors are related to the Chebyshev’s
polynomial roots. So once you use all those
00:10:38.640 --> 00:10:42.400
logics and use the partial fraction.
00:10:42.400 --> 00:10:47.590
Then finally you take the inverse Laplace
transform, for lambda is not equal to mu,
00:10:47.590 --> 00:10:58.330
you will get steady state or stationary probabilities
plus this expression and this is the function
00:10:58.330 --> 00:11:06.570
of t, e power minus lambda plus mu times t
plus two times square root of lambda mu times
00:11:06.570 --> 00:11:12.550
t cos of r by pi n plus one and denominator
this expression multiplied by this.
00:11:12.550 --> 00:11:20.390
And here this result is related to the initial
condition zero, that means at time zero the
00:11:20.390 --> 00:11:25.880
system is empty. If the system is not empty,
then you will have a one more expression here
00:11:25.880 --> 00:11:32.770
sin of this minus another term. So that is,
you will have a little bigger expression for
00:11:32.770 --> 00:11:42.880
system size is not empty. And this theta times
this, that will give the corresponding partial
00:11:42.880 --> 00:11:48.430
fraction and so on inverse Laplace it will
give the terms which is independent of t and
00:11:48.430 --> 00:11:50.940
that is related to the steady state probability.
00:11:50.940 --> 00:11:55.820
Because if you put t tends to infinity and
these quantities are greater than zero. So
00:11:55.820 --> 00:12:02.730
as t tends to infinity the whole terms will
tends to zero. Therefore, as the t tends to
00:12:02.730 --> 00:12:09.850
infinity, we will have pi n of t is equal
to this expression and this is valid for rho
00:12:09.850 --> 00:12:18.550
is less than one. With that condition rho
is less than one, those terms will tend to
00:12:18.550 --> 00:12:23.430
zero and you will have only this term and
that is going to be the steady state or limiting
00:12:23.430 --> 00:12:27.490
probabilities for M/M/1/N model.
00:12:27.490 --> 00:12:32.810
If you make also n tends to infinity along
with the t tends to infinity, you will have
00:12:32.810 --> 00:12:44.910
pi n's that is the steady state probability
for the M/M/1 infinity model. So even though
00:12:44.910 --> 00:12:52.740
I have explained M/M/1/N transient solution
in a brief way. But the same logic goes for
00:12:52.740 --> 00:12:58.700
the M/M/c/c model also, the only difference
is this determinant has the lambda’s and
00:12:58.700 --> 00:13:04.050
instead of mu’s you will have mu2, mu3,
and so on.
00:13:04.050 --> 00:13:08.970
And instead of the Chebyshev’s polynomial,
you will land up with the Charlier polynomial.
00:13:08.970 --> 00:13:17.610
But there is a difference between this M/M/1/N
model and M/M/c/c model transient solution.
00:13:17.610 --> 00:13:23.810
Since the Chebyshev’s polynomial has a closed
form roots, you can find out the factors.
00:13:23.810 --> 00:13:28.250
So here these are all the factors and you
know the factors as well as you can get the
00:13:28.250 --> 00:13:35.250
closed form expression for the M/M/1/N transient
solution where as Charlier polynomial does
00:13:35.250 --> 00:13:36.850
not have a closed form roots.
00:13:36.850 --> 00:13:42.790
Therefore, you will land up with the numerical
result for the transient solution for M/M/1/N,
00:13:42.790 --> 00:13:43.920
M/M/c/c model.
00:13:43.920 --> 00:13:49.860
In the case of a continuous time Markov chain,
that is a finite source Markovian Queuing
00:13:49.860 --> 00:13:57.070
models. This model is also known as a machine
repairman model and you can think of these
00:13:57.070 --> 00:14:05.610
PCs are nothing but machines and this is nothing
but the repairman. And here the scenario is
00:14:05.610 --> 00:14:15.620
we have a K PCs and each PC can give a print
job and the inter arrival of print jobs that
00:14:15.620 --> 00:14:18.800
is exponentially distributed by the each PC.
00:14:18.800 --> 00:14:28.450
Therefore, the print jobs that is follow a
arrival process that is a Poisson process
00:14:28.450 --> 00:14:37.580
with the parameter lambda from each PC. And
once the print jobs come into the printer,
00:14:37.580 --> 00:14:47.880
it will wait for the print. And the time taken
for the each print that is also exponentially
00:14:47.880 --> 00:14:51.470
distributed with the parameter mu.
00:14:51.470 --> 00:14:57.780
And here there is another assumption before
the first print is over by the same PC, it
00:14:57.780 --> 00:15:05.920
cannot give another print command. Therefore,
after the print is over by any one particular
00:15:05.920 --> 00:15:13.000
print job of any PC, then these things will
go back to the same thing, then with the inter
00:15:13.000 --> 00:15:18.380
arrival of print jobs generated that is exponentially
distributed, then the print job can come into
00:15:18.380 --> 00:15:29.020
the printer. So with these assumptions you
can think of the Stochastic process.
00:15:29.020 --> 00:15:34.260
That means the number of print jobs at any
time t in the printer that is going to form
00:15:34.260 --> 00:15:41.130
a Stochastic process and with the assumption
of inter arrival of print jobs, that is exponential
00:15:41.130 --> 00:15:48.350
and actual printing job that is exponentially
distributed and so on. Therefore, this is
00:15:48.350 --> 00:15:54.260
going to be a birth-death process, with the
birth rates or K times lambda or K minus one
00:15:54.260 --> 00:15:59.140
times lambda and so on, where as the death
rates that is mu, because we have only one
00:15:59.140 --> 00:16:00.610
repair.
00:16:00.610 --> 00:16:06.600
So this is nothing but system size number
of jobs in the print job, printer. So therefore
00:16:06.600 --> 00:16:12.190
that varies from zero to K, because we are
making the assumption more than one print
00:16:12.190 --> 00:16:18.450
job cannot be given by the same PC before
the print is over. And from zero to one, the
00:16:18.450 --> 00:16:25.410
arrival rate will be any one of the K PCs.
Therefore, the arrival rate is K times lambda
00:16:25.410 --> 00:16:29.440
and already one print job is there in the
system printer.
00:16:29.440 --> 00:16:35.850
Therefore, out of K minus one PCs one print
job can come, therefore the inter arrival
00:16:35.850 --> 00:16:41.240
time that is exponentially distributed with
the parameter K minus one times lambda and
00:16:41.240 --> 00:16:45.670
so on. So this is a way you can visualise
the birth rates, where as the death rates
00:16:45.670 --> 00:16:51.410
are mu. Once you know the birth rates and
death rates you can apply the birth-death
00:16:51.410 --> 00:16:54.780
process concept to get the steady state probabilities.
00:16:54.780 --> 00:17:00.530
So here we are getting the pi i's in terms
of pi 0, and using the summation of pi i is
00:17:00.530 --> 00:17:05.930
equal to one, you are getting the pi 0 also.
And once you know the steady state probability,
00:17:05.930 --> 00:17:11.130
you can get the all other measures. So the
difference is in this model it is a finite
00:17:11.130 --> 00:17:15.760
source, therefore the birth rates are the
function of, it is the state dependent birth
00:17:15.760 --> 00:17:23.120
rates where as the death rates are mu’s
only. Simulation of a Queuing model, I will
00:17:23.120 --> 00:17:26.589
do it in the next lecture.
00:17:26.589 --> 00:17:31.110
The summary of today's lecture, I have discussed
the simple Markovian queueing models other
00:17:31.110 --> 00:17:38.260
than M/M/1 infinity, that I have discussed
in the previous lecture and stationary distribution
00:17:38.260 --> 00:17:42.660
and all the other performance measures using
the birth-death process we have discussed
00:17:42.660 --> 00:17:48.200
for these queueing models and finally I discussed
the finite source Markovian queueing model
00:17:48.200 --> 00:17:50.850
also.
00:17:50.850 --> 00:18:05.250
These are all the reference books. Thanks.