WEBVTT
Kind: captions
Language: en
00:00:00.340 --> 00:00:06.180
This example talks about the communication
system in which whenever the transmission
00:00:06.180 --> 00:00:13.900
takes place with the digits 0 and 1 in the
several stages. Now we are going to define
00:00:13.900 --> 00:00:22.360
the random variable X0 be the digit transmitted
initially that is 0th step. Either the transmission
00:00:22.360 --> 00:00:29.230
digital be be 0 or 1 therefore only two possibilities
can be takes place at any nth step transmission
00:00:29.230 --> 00:00:34.770
either 0 or 1, like that we are making the
transmission over the different stages.
00:00:34.770 --> 00:00:43.350
Therefore, this Xn over the n will form a
stochastic process because we never know which
00:00:43.350 --> 00:00:49.399
digit is transmitted in the nth stage. So
nth stage is going to be one random variable
00:00:49.399 --> 00:00:55.989
and you have a collection of random variable
over the stages therefore it is a sequence
00:00:55.989 --> 00:01:01.030
of random variables so this going to form
a is Stochastic process. And this stochastic
00:01:01.030 --> 00:01:05.659
process is nothing but a discrete time discrete
stage stochastic process.
00:01:05.659 --> 00:01:10.909
Because the possible values of Xn is going
to be 0 or 1 therefore the state space is
00:01:10.909 --> 00:01:20.959
0 or 1 and it is a discrete state stochastic
process. The way the subsequent transmission
00:01:20.959 --> 00:01:27.609
takes place depends only on the last transmission
not the previous stages therefore you can
00:01:27.609 --> 00:01:33.889
assume that this follows Markov properly.
Therefore, this stochastic process is going
00:01:33.889 --> 00:01:38.710
to be call it as a Discrete-time Markov Chain.
00:01:38.710 --> 00:01:45.729
Now our interest is to find out-- so now I
will provide what is the one step transition
00:01:45.729 --> 00:01:56.239
probability for the Markov Chain or let me
give the transition diagram for that. So state
00:01:56.239 --> 00:02:04.130
transition diagram the possible states are
0 or 1 because the state space is 0 and 1.
00:02:04.130 --> 00:02:17.299
And the probability that in the next step
also the transmission is 0 with the probability
00:02:17.299 --> 00:02:28.260
1-a. This is a conditional probability of
the nth stage the transmission was 0 the (n+1)th
00:02:28.260 --> 00:02:34.180
stage is also the transmission 0 with the
probability 1-a.
00:02:34.180 --> 00:02:39.260
The one step transition probability of system
is moving from 0 to 1 that probabilities is
00:02:39.260 --> 00:02:50.310
a. That means the nth stage the transmission
was the digit 0 the (n+1)th stage the transmission
00:02:50.310 --> 00:02:59.989
will be digit 1 with the probability a. Similarly,
I am going to apply the one step transition
00:02:59.989 --> 00:03:11.010
probability of 1 to 1 that is 1-b and this
is a b that means this 1 to 0 that probability
00:03:11.010 --> 00:03:20.689
is a 1 to 0 is a b and 1 to 1 is 1-b.
00:03:20.689 --> 00:03:29.860
Obviously, this a is lies between 0 to 1 and
b is also lies between 1.
00:03:29.860 --> 00:03:38.000
So this is the a is the probability that the
system is transmitting from the nth stage
00:03:38.000 --> 00:03:47.670
with the digit 0 and the (n+1)th stage with
the digit 1 that probability is a therefore
00:03:47.670 --> 00:03:54.650
the negation is 1-a because there is the system
can transmit either 0 or 1. So once you say
00:03:54.650 --> 00:04:00.499
that one step transition probability of 0
to 1 is a then 0 to 0 will be 1-a. Similarly,
00:04:00.499 --> 00:04:08.439
1 to 0 is given as a probability b and the
other digit transmission will be one therefore
00:04:08.439 --> 00:04:15.180
it is going to be 1 to 1 will be 1-b. So this
is the state transition diagram.
00:04:15.180 --> 00:04:21.500
And this is the one step transition probability
for a given time homogenous discrete-time
00:04:21.500 --> 00:04:29.340
Markov Chain. Our interest is to find out
what is the distribution of Xn for n. For
00:04:29.340 --> 00:04:37.280
that you need what is the n-Step Transition
Probability matrix. Since the one step transition
00:04:37.280 --> 00:04:43.860
probability matrix is given you can find out
P square, P power 3 and so on. By induction
00:04:43.860 --> 00:04:50.530
method you can find out the P power m but
using the P power m you can find out the P
00:04:50.530 --> 00:04:51.530
power (m+n).
00:04:51.530 --> 00:04:55.520
Therefore, you can come to the conclusion
what is the n-Step Transition Probability
00:04:55.520 --> 00:05:03.979
of system is moving from 0 to 1 and 0 to 0
and so on. So this is nothing but I am just
00:05:03.979 --> 00:05:14.970
giving the only the result b + a times 1-a-
b power n divided by a + b and this is nothing
00:05:14.970 --> 00:05:26.580
but a-a times 1-a- b power n divided by a
+ b. Similarly, if you find out the n-Step
00:05:26.580 --> 00:05:37.729
transition probability of system moving from
1 to 0 that is b-b times 1-a-b power n divided
00:05:37.729 --> 00:05:40.590
by a + b.
00:05:40.590 --> 00:05:51.699
This is nothing but a + b times 1-a-b power
n divided by a + b. So here I am just giving
00:05:51.699 --> 00:06:00.550
the n-Step Transition Probability in matrix
form. By given P you should find out P square
00:06:00.550 --> 00:06:10.669
P power q by induction you can find out the
P power n. And this is valid provided 1-a-b
00:06:10.669 --> 00:06:20.970
which is less than 1. Because we are finding
the P power n matrix, so here it needs some
00:06:20.970 --> 00:06:29.590
determinant also unless otherwise the absolute
of 1-a-b which is less than 1, this result
00:06:29.590 --> 00:06:30.590
is not valid.
00:06:30.590 --> 00:06:38.300
So provided this condition, the P power (n)
that is the matrix. So that is same as P power
00:06:38.300 --> 00:06:45.199
n also. P power (n) is same as P power n.
00:06:45.199 --> 00:06:55.650
So as n tends to
to infinite you can come to the conclusion
00:06:55.650 --> 00:07:01.340
what is the probability that the system will
be in the state 0 that is same as b divided
00:07:01.340 --> 00:07:09.080
by a + b. And similarly, what is the probability
that the system will be in the state 1 as
00:07:09.080 --> 00:07:15.669
entrance to infinite that will be a divided
by a+ b. This can be visualized from the state
00:07:15.669 --> 00:07:24.550
transition diagram easily. Whenever the system
is keep moving into the state 0 or 1 with
00:07:24.550 --> 00:07:31.870
the probability a, b and with the self-loop
on 1-a and 1-b the subsequent stages the system
00:07:31.870 --> 00:07:35.439
will be any one of these two states.
00:07:35.439 --> 00:07:42.870
So with the proportion of b divided by a+b
the system will be in the state 1. Similarly,
00:07:42.870 --> 00:07:52.250
with the proportion a divided by a+b the system
will be in the state 1 with the proportion
00:07:52.250 --> 00:07:59.719
b divided by a+b the system will be in the
state 0 in a long run. The interpretation
00:07:59.719 --> 00:08:09.479
of as n tends to infinite this probability
is nothing but in a long run with this proportion
00:08:09.479 --> 00:08:15.479
the system will be in the state 0 or 1.
00:08:15.479 --> 00:08:25.830
So this state transition diagram will be useful
to study the long run distribution or where
00:08:25.830 --> 00:08:31.780
the system will be as n tends to infinity
to study those things the state transition
00:08:31.780 --> 00:08:36.460
diagram will be useful.
00:08:36.460 --> 00:08:53.650
Now we will moving to the next problem that
is Example 4. Let it is a sequence of random
00:08:53.650 --> 00:09:10.100
variable be a
sequence of
00:09:10.100 --> 00:09:26.470
independent random variables with condition
the probability of Yn takes the value 1 that
00:09:26.470 --> 00:09:37.980
probability is p that is same as 1- the probability
of Yn takes the value -1.
00:09:37.980 --> 00:09:45.900
We have a stochastic process and each random
variable is a independent random variable
00:09:45.900 --> 00:09:51.001
and the probability mass function is provided
with this situation the probability of Yn
00:09:51.001 --> 00:09:53.880
takes the value one is p.
00:09:53.880 --> 00:10:01.041
You can assume that p takes the value 0 to
1.That is same as 1- of probability of Yn
00:10:01.041 --> 00:10:13.400
takes the value -1 for all n. Now I am going
to define another random variable. Let Xn
00:10:13.400 --> 00:10:31.210
be defined by X0 is equal to 0 whereas a X(n+1)
onwards that is going to be Xn + Y(n+1) for
00:10:31.210 --> 00:10:43.370
n is equal to 1, 2 and so on. So we are defining
another random variable Xn with the X0 is
00:10:43.370 --> 00:11:04.640
equal to 0 and X(n+ 1) is equal to Xn+ Y(n+1).
Now the question is check Xn that stochastic
00:11:04.640 --> 00:11:09.010
process is the DTMC.
00:11:09.010 --> 00:11:24.440
If it is a DTMC also find out what is the
probability of Xn takes the value k. We started
00:11:24.440 --> 00:11:28.870
with one stochastic process and we defined
another stochastic process with the earlier
00:11:28.870 --> 00:11:36.930
stochastic process and check whether the given
the new stochastic process is a Discrete-time
00:11:36.930 --> 00:11:41.930
Markov Chain that is the default one that
is time homogenous Discrete-time Markov Chain.
00:11:41.930 --> 00:11:47.950
If so then what is the probability of Xn takes
the value k that is nothing but find out the
00:11:47.950 --> 00:11:51.520
distribution of Xn.
00:11:51.520 --> 00:12:02.530
So how to find out this the given or the Xn
is going to be the DTMC.
00:12:02.530 --> 00:12:12.980
Since Yn takes the value 1 with the probability
p and Yn takes the value -1 with the probability
00:12:12.980 --> 00:12:23.240
1-p you can make out the possible values of
Yn is going to be 0 or plus or minus one;
00:12:23.240 --> 00:12:34.800
plus or minus 2 and so on. Because the relation
is a X0 is equal to 0 and the Xn is Xn+Y(n+1)and
00:12:34.800 --> 00:13:04.070
the range of Yn is 1, -1 therefore the range
of Xn that inform a state space and X0 is
00:13:04.070 --> 00:13:09.080
equal to 0 therefore X(n+1) = Xn+ Y(n+1) so
n takes a value 1 and so on.
00:13:09.080 --> 00:13:15.500
Therefore, the possible values of Xn will
be 0 plus or minus 1 or plus or minus 2 and
00:13:15.500 --> 00:13:22.950
so on therefore that will form a state space.
Now the given clue is that probability of
00:13:22.950 --> 00:13:30.550
Yn takes the value 1 is probability p and
a probability of Yn takes the value -1 that
00:13:30.550 --> 00:13:38.620
is 1-p and the probability p is lies between
0 to 1. So using this information you can
00:13:38.620 --> 00:14:02.920
make a state space of the Xn that is going
to be 1, 2 and so on -1, -2 and so on.
00:14:02.920 --> 00:14:11.460
Now we can fill up what is the one step transition
of system is moving from 0 to 1 that means
00:14:11.460 --> 00:14:20.490
the X1 – 0 to 1 suppose you substitute 0
here then suppose it takes the value 1 then
00:14:20.490 --> 00:14:28.880
the system can move from the state 0 to 1
in one step. Suppose you put the value Xn
00:14:28.880 --> 00:14:37.310
is equal to 0 suppose you put Xn is equal
to 0 and Y(n+1) takes the value 1 with the
00:14:37.310 --> 00:14:52.010
probability p then the X(n+1) value will be
one with the probability p.
00:14:52.010 --> 00:14:59.510
Now you can go for what is the state transition
probability of 1to 0. Suppose the Xn value
00:14:59.510 --> 00:15:09.810
was 1; suppose the Y(n+1) value was -1 then
the X(n+1) value will be 0. So the one step
00:15:09.810 --> 00:15:16.760
transition of a system moving from 1 to 0
because of happening probability of Y(n+1)
00:15:16.760 --> 00:15:26.790
is equal to -1 that probability is 1-p. So
whenever the system is moving from one step
00:15:26.790 --> 00:15:35.930
forward that probability will be the probability
p and one step backward that probability will
00:15:35.930 --> 00:15:37.000
be 1-p.
00:15:37.000 --> 00:15:42.390
So this is the way it goes forward step and
this is the way it goes to the backward step
00:15:42.390 --> 00:15:48.390
so you can fill up all other probabilities
forward probability with the probability p
00:15:48.390 --> 00:16:02.811
and the backward probability with the 1-p.
Also, we can come to the conclusion, the way
00:16:02.811 --> 00:16:12.160
we have written X(n+1) is equal to Xn+ Y(n+1)
and all the Yi’s are independent random
00:16:12.160 --> 00:16:25.240
variable the X(n+1) going to take the value
depends only on Xn not the previous X(n-1)
00:16:25.240 --> 00:16:27.780
or X(n-2) and so on.
00:16:27.780 --> 00:16:36.700
Therefore, the conditional distribution of
X(n+1) given that Xn, X(n-1) till X0 that
00:16:36.700 --> 00:16:48.490
is same as the conditional distribution of
X(n+1) given Xn. That means the Xn is going
00:16:48.490 --> 00:17:00.370
to satisfy the Markov property
because of this relation because of X(n+1)
00:17:00.370 --> 00:17:08.720
is equal to Xn plus independent random variable.
Therefore, the Xn , n= 1, 2, 3 and so on.
00:17:08.720 --> 00:17:16.029
This Stochastic process is going to satisfy
the Markov property therefore this discrete
00:17:16.029 --> 00:17:21.870
time discrete state stochastic process is
going to be the Discrete-time Markov Chain
00:17:21.870 --> 00:17:25.839
because of the Markov property satisfied.
00:17:25.839 --> 00:17:31.629
Once it is Markov property satisfied by using
the Chapman-Kolmogorov Equation you can find
00:17:31.629 --> 00:17:39.760
out what is the distribution of Xn takes the
value k, that is nothing but where it started
00:17:39.760 --> 00:17:46.409
a time 0 and what is the conditional distribution
of n-Step Transition Probability and the n-Step
00:17:46.409 --> 00:17:52.740
Transition Probability is nothing but the
elemental from the P power n and From here
00:17:52.740 --> 00:17:59.259
you can find out the one step transition probability
matrix from the one step transition probability
00:17:59.259 --> 00:18:04.230
matrix you can find out a P, P square, P cube
and so on.
00:18:04.230 --> 00:18:09.810
And you can find out the P power n and that
element is going to be the n-Step Transition
00:18:09.810 --> 00:18:15.190
Probability using that you can find out the
distribution. And since we do not know the
00:18:15.190 --> 00:18:23.490
value of where p is lies between 0 to 1. I
am not going to discuss the computational
00:18:23.490 --> 00:18:26.519
aspect of finding out the distribution.
00:18:26.519 --> 00:18:34.540
This is left as an exercise and the final
answer is provided. The difference between
00:18:34.540 --> 00:18:41.220
the earlier example and this example is the
state space is going to be a countable infinite.
00:18:41.220 --> 00:18:47.320
Therefore, the P is not going to be a easy
matrix it is going to be a matrix with the
00:18:47.320 --> 00:18:53.450
many elements in it therefore finding out
P square and P power n is going to be little
00:18:53.450 --> 00:18:59.670
complicated than the usual square matrix.
00:18:59.670 --> 00:19:04.950
So hence the conclusion is a by knowing the
initial probability vector and the one step
00:19:04.950 --> 00:19:11.250
transition probability matrix or the state
transition diagram we can get the distribution
00:19:11.250 --> 00:19:19.009
of Xn for any n. There is a small mistake
the running index for X(n+1) value is equal
00:19:19.009 --> 00:19:28.590
to Xn+Y(n+1) that is you starting from 0,
1, 2 and similarly the previous slide X(n+1)
00:19:28.590 --> 00:19:37.559
is equal to Xn+Y(n+1) and the n is running
from 0, 1, 2 and so on.
00:19:37.559 --> 00:19:43.909
So in this lecture we have discussed Chapman-Kolmogorov
Equation and also we have discussed the n-Step
00:19:43.909 --> 00:19:49.450
Transition Probability Matrix. So the n-Step
Transition Probability Matrix can be computed
00:19:49.450 --> 00:19:55.919
from the one step transition probability matrix
with the power of that n. And also we have
00:19:55.919 --> 00:20:03.870
discussed four simple examples for explaining
the Chapman-Kolmogorov Equation and the n-Step
00:20:03.870 --> 00:20:06.440
Transition Probability Matrix.
00:20:06.440 --> 00:20:12.940
For the lecture 1 and 2, we have used these
three books for as a reference the first one
00:20:12.940 --> 00:20:18.200
is J Medhi, “Stochastic Processes” book.
The second one is a Kishor S Trivedi, “Probability
00:20:18.200 --> 00:20:24.850
and Statistics with the Reliability, Queuing
and Computer Science Applications.” The
00:20:24.850 --> 00:20:32.929
third one is a Shelton M Ross, “Introduction
to Probability Models.” So with this I complete
00:20:32.929 --> 00:20:54.090
the lecture 2 of Discrete time Makov Chain.
Thanks.