This subsection will be about matrix representation for Markov chains. Starting from now, we will consider all the Markov chains which have a finite number of elements in the state space. That is S, consists only some finite amount of elements and let me just count these elements, numbering them by one, two, and so on capital M. One more assumption we should introduce now is the probability that X_n is equal to j given that X_n-1 is equal to i is equal to P_ij. And we will assume that this P_ij does not depend on n at all. Markov chains with this property are known as homogeneous Markov chains. Starting from now we will consider only Markov chains of this type. And since we have this to our assumptions, we can substitute the various P_ij into one matrix. This matrix will be denoted by capital P, so it consists of the elements P_ij where i and j are from 1 to capital M. And this matrix is known as transition matrix. What are the main properties of this matrix? First of all, if we just sum of elements of this matrix by one for all. We get one. This follows directly from the definition of the various P_ij. So if for sum by j from 1 to capital M, then we get one for any i. And another property which is very three will that all those elements P_ij are not negative. So, matrices of this type are known in this matrix as stochastic matrices. So, according to this definition there is a transition matrix or this type and this metric characterizes all of conditional probabilities of this type. On the other hand, we can introduce M-step transition matrix. So, let me denote P_ij of m is a probability that X_n+m is equal to j given that X_n is equal to i. The matrix which consists of the elements, I will denote by P_(m). Once more, this is M-Step Transition Matrix. An interesting question is how to calculate M-step Transition Matrix from Transition matrix. And the answer is given by the following theorem. This is theorem stands that P_(m) is equal to the P_m. So, you should multiply the matrix P by itself m times and you will get exactly the Transition Matrix. This is a rather beautiful mathematical result and let me show why this result is true. Let me provide a proof of it. So, let me consider the elements number ij of this matrix. So, it is written actually here. And let me apply for this probability, the Law of Total Probability. So, this, I will rewrite it as the sum, the probability is that X_n+m is equal to j given that X_n+m-1 is equal to some value of k. And X_n and is equal to i. Multiplied by the probability that X_n+m-1 is equal to k given that X_n is equal to i. And we shall sum of all k from one to M. Now, let me apply the Markov property to the first conditional probability. We know that if we consider the conditional probability here of the whole history that is completed the term mines by is the most recent past event. So, actually this conditional probability is equal to conditional probability X_n+m is equal to j given that X_n+m-1 is equal thia and this. I can simply cross the last event. And this term, I will leave it as it is and now I would like to write all those objects in terms of matrices P, M, P. So, actually what is the first probability. This does not seem more than a transition, probability of transition from the state number k to the state number j. So is P_kj and as for the second probability, this is nothing more than P_(m-1)_ik. So, we get the matrix P(m) is equal to P multiplied by P_(m-1). Now, according to this same logic it is equal to P-squared P and minus two and so on. Finally, we get P in the power m. So, this observation completes the proof. So, once more in the matrix of presentation, we have a transition matrix and in M step transition matrix which are related to each other according to the following rather beautiful formula, let me now continue. You know that in any time moment, the system is in one of the states forms the state space. Let me now consider the probability with a stake number k, the system is a state number j. Let me denote this probability by Pi_j_(k). This is of course probability distribution. So, for now consider Pi_1_(k) and so on, Pi_M_(k). This is exactly discrete probability distribution, the sum of numbers is equal to one and all of them are negative and let me denote this by Pi vector Pi_(k). Major question is to ask whether it is possible to compute Pi_(k) from Pi_(k-1). This is of course possible, and here we should employ nothing more than the law of total probability. In fact, if you take Pi_j_(k), this is the probability that X_k is equal to j, you can rewrite this as a probability that X_k is equal to j given said X_k-1 is equal to some specific value. I multiplied by the probability that X_k-1 is equal to i. And then we sum these products by i from 1 to M. Okay let me continue. This is of course the sum from 1 to M. Here is a transition from a state number i to state number j, that is Pi_ij. And here we have vector, element of the vector Pi_(k-1) and element number i. So, this is from here we conclude, that actually vector Pi_k is equal to the product of the vector of Pi_(k-1) and the matrix P. Also we can, apply this argument many times and finally get the this is vector Pi_0 multiplied by the matrix P n times. We say that vector Pi* gives a stationary distribution for a given Markov chain. If product of Pi* and matrix P is equal to Pi*. This is a very point notion and a little bit later I will show why it is so important. But, the moment let me mention that if Pi_0 is equal to Pi* then Pi_k is also equal to Pi* for any k. So, this is a system it starts from the station of distribution. It has a station distribution any time moment. This is all that you should know at this stage about matrix presentation. And in the next subsection we will consider graphical representation. This is another very useful tool for describing a Markov Chain.
