This example talks about the communication system in which whenever the transmission
takes place with the digits 0 and 1 in the several stages. Now we are going to define
the random variable X0 be the digit transmitted initially that is 0th step. Either the transmission
digital be be 0 or 1 therefore only two possibilities can be takes place at any nth step transmission
either 0 or 1, like that we are making the transmission over the different stages.
Therefore, this Xn over the n will form a stochastic process because we never know which
digit is transmitted in the nth stage. So nth stage is going to be one random variable
and you have a collection of random variable over the stages therefore it is a sequence
of random variables so this going to form a is Stochastic process. And this stochastic
process is nothing but a discrete time discrete stage stochastic process.
Because the possible values of Xn is going to be 0 or 1 therefore the state space is
0 or 1 and it is a discrete state stochastic process. The way the subsequent transmission
takes place depends only on the last transmission not the previous stages therefore you can
assume that this follows Markov properly. Therefore, this stochastic process is going
to be call it as a Discrete-time Markov Chain.
Now our interest is to find out-- so now I will provide what is the one step transition
probability for the Markov Chain or let me give the transition diagram for that. So state
transition diagram the possible states are 0 or 1 because the state space is 0 and 1.
And the probability that in the next step also the transmission is 0 with the probability
1-a. This is a conditional probability of the nth stage the transmission was 0 the (n+1)th
stage is also the transmission 0 with the probability 1-a.
The one step transition probability of system is moving from 0 to 1 that probabilities is
a. That means the nth stage the transmission was the digit 0 the (n+1)th stage the transmission
will be digit 1 with the probability a. Similarly, I am going to apply the one step transition
probability of 1 to 1 that is 1-b and this is a b that means this 1 to 0 that probability
is a 1 to 0 is a b and 1 to 1 is 1-b.
Obviously, this a is lies between 0 to 1 and b is also lies between 1.
So this is the a is the probability that the system is transmitting from the nth stage
with the digit 0 and the (n+1)th stage with the digit 1 that probability is a therefore
the negation is 1-a because there is the system can transmit either 0 or 1. So once you say
that one step transition probability of 0 to 1 is a then 0 to 0 will be 1-a. Similarly,
1 to 0 is given as a probability b and the other digit transmission will be one therefore
it is going to be 1 to 1 will be 1-b. So this is the state transition diagram.
And this is the one step transition probability for a given time homogenous discrete-time
Markov Chain. Our interest is to find out what is the distribution of Xn for n. For
that you need what is the n-Step Transition Probability matrix. Since the one step transition
probability matrix is given you can find out P square, P power 3 and so on. By induction
method you can find out the P power m but using the P power m you can find out the P
power (m+n).
Therefore, you can come to the conclusion what is the n-Step Transition Probability
of system is moving from 0 to 1 and 0 to 0 and so on. So this is nothing but I am just
giving the only the result b + a times 1-a- b power n divided by a + b and this is nothing
but a-a times 1-a- b power n divided by a + b. Similarly, if you find out the n-Step
transition probability of system moving from 1 to 0 that is b-b times 1-a-b power n divided
by a + b.
This is nothing but a + b times 1-a-b power n divided by a + b. So here I am just giving
the n-Step Transition Probability in matrix form. By given P you should find out P square
P power q by induction you can find out the P power n. And this is valid provided 1-a-b
which is less than 1. Because we are finding the P power n matrix, so here it needs some
determinant also unless otherwise the absolute of 1-a-b which is less than 1, this result
is not valid.
So provided this condition, the P power (n) that is the matrix. So that is same as P power
n also. P power (n) is same as P power n.
So as n tends to to infinite you can come to the conclusion
what is the probability that the system will be in the state 0 that is same as b divided
by a + b. And similarly, what is the probability that the system will be in the state 1 as
entrance to infinite that will be a divided by a+ b. This can be visualized from the state
transition diagram easily. Whenever the system is keep moving into the state 0 or 1 with
the probability a, b and with the self-loop on 1-a and 1-b the subsequent stages the system
will be any one of these two states.
So with the proportion of b divided by a+b the system will be in the state 1. Similarly,
with the proportion a divided by a+b the system will be in the state 1 with the proportion
b divided by a+b the system will be in the state 0 in a long run. The interpretation
of as n tends to infinite this probability is nothing but in a long run with this proportion
the system will be in the state 0 or 1.
So this state transition diagram will be useful to study the long run distribution or where
the system will be as n tends to infinity to study those things the state transition
diagram will be useful.
Now we will moving to the next problem that is Example 4. Let it is a sequence of random
variable be a sequence of
independent random variables with condition the probability of Yn takes the value 1 that
probability is p that is same as 1- the probability of Yn takes the value -1.
We have a stochastic process and each random variable is a independent random variable
and the probability mass function is provided with this situation the probability of Yn
takes the value one is p.
You can assume that p takes the value 0 to 1.That is same as 1- of probability of Yn
takes the value -1 for all n. Now I am going to define another random variable. Let Xn
be defined by X0 is equal to 0 whereas a X(n+1) onwards that is going to be Xn + Y(n+1) for
n is equal to 1, 2 and so on. So we are defining another random variable Xn with the X0 is
equal to 0 and X(n+ 1) is equal to Xn+ Y(n+1). Now the question is check Xn that stochastic
process is the DTMC.
If it is a DTMC also find out what is the probability of Xn takes the value k. We started
with one stochastic process and we defined another stochastic process with the earlier
stochastic process and check whether the given the new stochastic process is a Discrete-time
Markov Chain that is the default one that is time homogenous Discrete-time Markov Chain.
If so then what is the probability of Xn takes the value k that is nothing but find out the
distribution of Xn.
So how to find out this the given or the Xn is going to be the DTMC.
Since Yn takes the value 1 with the probability p and Yn takes the value -1 with the probability
1-p you can make out the possible values of Yn is going to be 0 or plus or minus one;
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
the range of Yn is 1, -1 therefore the range of Xn that inform a state space and X0 is
equal to 0 therefore X(n+1) = Xn+ Y(n+1) so n takes a value 1 and so on.
Therefore, the possible values of Xn will be 0 plus or minus 1 or plus or minus 2 and
so on therefore that will form a state space. Now the given clue is that probability of
Yn takes the value 1 is probability p and a probability of Yn takes the value -1 that
is 1-p and the probability p is lies between 0 to 1. So using this information you can
make a state space of the Xn that is going to be 1, 2 and so on -1, -2 and so on.
Now we can fill up what is the one step transition of system is moving from 0 to 1 that means
the X1 – 0 to 1 suppose you substitute 0 here then suppose it takes the value 1 then
the system can move from the state 0 to 1 in one step. Suppose you put the value Xn
is equal to 0 suppose you put Xn is equal to 0 and Y(n+1) takes the value 1 with the
probability p then the X(n+1) value will be one with the probability p.
Now you can go for what is the state transition probability of 1to 0. Suppose the Xn value
was 1; suppose the Y(n+1) value was -1 then the X(n+1) value will be 0. So the one step
transition of a system moving from 1 to 0 because of happening probability of Y(n+1)
is equal to -1 that probability is 1-p. So whenever the system is moving from one step
forward that probability will be the probability p and one step backward that probability will
be 1-p.
So this is the way it goes forward step and this is the way it goes to the backward step
so you can fill up all other probabilities forward probability with the probability p
and the backward probability with the 1-p. Also, we can come to the conclusion, the way
we have written X(n+1) is equal to Xn+ Y(n+1) and all the Yi’s are independent random
variable the X(n+1) going to take the value depends only on Xn not the previous X(n-1)
or X(n-2) and so on.
Therefore, the conditional distribution of X(n+1) given that Xn, X(n-1) till X0 that
is same as the conditional distribution of X(n+1) given Xn. That means the Xn is going
to satisfy the Markov property because of this relation because of X(n+1)
is equal to Xn plus independent random variable. Therefore, the Xn , n= 1, 2, 3 and so on.
This Stochastic process is going to satisfy the Markov property therefore this discrete
time discrete state stochastic process is going to be the Discrete-time Markov Chain
because of the Markov property satisfied.
Once it is Markov property satisfied by using the Chapman-Kolmogorov Equation you can find
out what is the distribution of Xn takes the value k, that is nothing but where it started
a time 0 and what is the conditional distribution of n-Step Transition Probability and the n-Step
Transition Probability is nothing but the elemental from the P power n and From here
you can find out the one step transition probability matrix from the one step transition probability
matrix you can find out a P, P square, P cube and so on.
And you can find out the P power n and that element is going to be the n-Step Transition
Probability using that you can find out the distribution. And since we do not know the
value of where p is lies between 0 to 1. I am not going to discuss the computational
aspect of finding out the distribution.
This is left as an exercise and the final answer is provided. The difference between
the earlier example and this example is the state space is going to be a countable infinite.
Therefore, the P is not going to be a easy matrix it is going to be a matrix with the
many elements in it therefore finding out P square and P power n is going to be little
complicated than the usual square matrix.
So hence the conclusion is a by knowing the initial probability vector and the one step
transition probability matrix or the state transition diagram we can get the distribution
of Xn for any n. There is a small mistake the running index for X(n+1) value is equal
to Xn+Y(n+1) that is you starting from 0, 1, 2 and similarly the previous slide X(n+1)
is equal to Xn+Y(n+1) and the n is running from 0, 1, 2 and so on.
So in this lecture we have discussed Chapman-Kolmogorov Equation and also we have discussed the n-Step
Transition Probability Matrix. So the n-Step Transition Probability Matrix can be computed
from the one step transition probability matrix with the power of that n. And also we have
discussed four simple examples for explaining the Chapman-Kolmogorov Equation and the n-Step
Transition Probability Matrix.
For the lecture 1 and 2, we have used these three books for as a reference the first one
is J Medhi, “Stochastic Processes” book. The second one is a Kishor S Trivedi, “Probability
and Statistics with the Reliability, Queuing and Computer Science Applications.” The
third one is a Shelton M Ross, “Introduction to Probability Models.” So with this I complete
the lecture 2 of Discrete time Makov Chain. Thanks.