noc21-cs104-lec20

What do we do with these examples right where the transition probabilities were 0 1 1 0 and then it keeps switching in the evolution. So, there seems to be no limit of the powers of this matrix. So, what is the problem here? So, issue with M is that it has no way to go from the state space element 1 state 1 to itself and similarly from state 2 to 2. So, this probability is 0 right this is what M 1 1 0 means. So, since there is it is not the case that from any i you can go to any j with positive probability ok. So, because of that it is somehow not behaving in the most natural way ok. Similarly issue with M square is that M 2 1 is 0 right. So, 2 to 1 not possible not this 1 2 is 0. So, no way to move 1 to 2 right. So, it gets actually yeah the exploration in the evolution is not happening in the best way because of these problems because of these hurdles. So, the transition is not allowing you to go from every i to every j with some chance it makes the chance actually 0 exactly 0. So, let us exclude these examples. So, how do you exclude them? You look at processes where every i to j there is some chance of reaching. So, Markov chain given by mu and M is called regular ok regular or natural if there exists a time M let us call it just time. So, let there exist a time t at which point the transition probabilities are all positive such that for all i j in S M to the t i j is positive ok that is M to the t has all entries positive ok and M to the t has only positive entries. So, that is then a point after which the Markov chain will start behaving in a much better way and you can understand the evolution better ok because there is a fair chance well it may not be fair, but at least there is some chance that you can go from any i to any j ok. It is not that the evolution is excluding some option completely out. So, every transition is allowed that is the good thing about regular Markov chain after a point it becomes nice and let us then immediately prove a simple property of these. So, if M raise to t has all entries positive then so, does M raise to t plus 1 ok. So, once you reach this point where all transitions are allowed after that point of time that is always the case. How do you show this? So, first you note that each row of M has some entry positive why is that the case well because the otherwise the row will be the 0 and then the sum will not be 1 right. So, at least some entries positive it may be only one entry in which case it will be 1. So, each row in each row of M some entries positive. So, now, you look at M times M to the t right. So, you are multiplying a row of M with columns of M to the t now columns of M to the t every entry is positive. So, this has also every entry positive right because you pick this and let us say look at the first row of M the position the entry which is positive and just multiply that with if you multiply it with any column corresponding location of M to the t you will have a positive contribution. This here we are also using the fact that since negative entries are not there and others greater than equal to 0 that is also there right. So, some entry in every row is positive and the others are non negative. So, because of that that positive contribution will remain positive strictly positive ok. So, that is the proof right. So, this is why regularity is a very nice condition because once M to the t satisfies all positive entries it will remain true forever beyond that point. So, for regular M, M square has a nice physical interpretation which is that its i th row is the i th row of M times M. So, what is happening here is the i th row oh let me first correct this hm let me correct this for such M to the t M to the t plus 1 has a nice physical interpretation because if you look at the i th row then again it is just this. Now, in fact, I have to do differently. So, now, M to the t i th row times M right. So, M to the t has positive entries. So, this i th row is also positive every entry is positive. So, when you multiply with a column in M what is happening is you are taking an average ok in and you are not leaving anything out because M to the t has positive entries. So, the average actually gives some positive weight to every entry in the first column of M let us say. So, it is like averaging the rows of M without leaving any out. So, every time you are multiplying by M you are actually just keep taking the average that is the intuition. So, what happens if you take this average infinitely right for a long time again and again if you average out then you tend to get all things equal. So, you ask the question what happens if you do this many times many many times right. So, this is the guiding question and the guiding intuition which will lead you to a major theorem which describes the limit. So, this is a version of Perron Frobenius theorem it is very old in matrix analysis. So, it says that if M is the transition matrix of a regular Markov chain, then its limit limit of its powers is a matrix which is given by a product of the one column vector and some other row vector where 1 bar is all one column vector and w is some column vector w is some probability distribution ok. So, we are actually this theorem is saying things, but also defining things. So, assuming regularity it is saying that the limit actually exists right this is a it is you are multiplying a column with a row. So, you will get a matrix square matrix which will which will have rank 1. So, 1 is basically it has all ones and w is some probability distribution. So, let us interpret this. So, this w is called the topic that we started studying stationary distribution and this for any initial distribution mu what is now the limit of mu M to the M. So, that will be by the theorem it will be mu times 1 bar times w transpose now mu sorry this the row. So, mu transpose. So, mu transpose is a row multiplied with the column vector 1, but that you know is the value of mu right which is 1. So, this is just w transpose. So, what you see is that in the limit it does not matter what mu was this is independent is independent of mu. So, that is the amazing thing that no matter what the starting point is the end point is the same if you wait long enough ok. So, it is this stationary distribution is very fundamental it again tells you something about the memorylessness ok. So, this this kind of evolution is actually memoryless it does not remember what it started from it just remembers the transition probability. So, this w is only dependent on M not mu and another third thing is that this matrix 1 dot w transpose it has rank 1 ok. So, in the end you can start with any M of any rank stochastic matrix, but ultimately the rank in the limit becomes 1 right. So, this is a very important and highly unexpected theorem and this shows why Markov chains are structurally so important ok. So, how do you show this what is the proof? So, we will take a take an intuitive route ok. We will not go into the deep analysis of limit etcetera we will just give you a more intuitive sketch. So, that you can read the proof somewhere else formalize. Let us just first look at the idea of this. So, we will show that show that the action M on a vector let us call it let us call the result V 1. So, this matrix action the entries of V 1 get closer to each other compared to those in V 0 ok. So, you start with the I mean view matrix M as a linear transformation in other words you multiply M with a column vector you will get another column vector call it V 1. What we will show very soon is that whatever what the entries in V 0 what the difference between maximum and minimum that difference will shrink in this matrix action ok. So, in V 1 the difference will be smaller. So, if you continue doing this action infinitely many times ultimately the transformation M to the n will make all the entries equal ok. So, V n will have equal entries. So, it will become a scalar. So, in the end in the limit which it means that M to the n dot V 0 is a scalar that is the bulk of the proof ok and then based on this we will finish the theorem statement. So, let us attempt this let us implement this. So, define inside V 0 max is let us say m 0 and min is small m 0 in the vector V 1 max is m 1 min is small m ok and we are interested in the differences how has the difference changed. So, let the matrix M have minimum entry delta right can delta be 0 yes it can be 0, but since we are assuming it to be a regular Markov chain. So, at some point M to the t will have only positive entries. So, let us assume that. So, without loss of generality delta is positive else we work with M to the t of positive entries ok. So, let us assume that delta is positive that is the min entry in the matrix ok. The other thing is here that delta cannot exceed half ok minimum cannot be too large why because after all this matrix M is stochastic. So, the row sum has to be 1 at all times if delta is large then that will exceed it will go beyond 1. If delta is greater than half then it would mean that sum row sum a row sum in M is actually more than S by I mean it is at least S times delta which is then more than S by 2 now state space is at least 2 right. So, this is greater than 1 that is a contradiction right. So, delta cannot be greater than half it is between half and 0, but strictly positive ok. So, now let us look at the entries in V 1. So, consider the image vector V 1 M times V 0. So, observe that each entry in V 1 is at most what. So, you have to look at entries that you get when you multiply a row of M with the vector V 0. So, the entries of the row let us say the first row of M it has entries at least delta and V 0 the entries are in the range small m 0 to big M 0. So, an upper bound is big M 0 times 1 minus delta plus small m 0 times delta this is an upper bound why because this is greater than half right and this is less than equal to half. So, the larger entries essentially the larger entries in V 0 they can contribute at most M 0 times 1 minus delta and the smaller entries can contribute this much. So, this is the basic idea you have to prove this by using row sum to be 1 essentially. So, use that row sum in M is 1 ok. So, since the row sum is 1 and you know the minimum is delta. So, the range is delta to I mean the delta part and then the 1 minus delta part now the bigger part the maximum contribution you can get from that is if you multiply it with M 0 ok and then the rest delta part is will come from M 0. So, that is an upper bound what is a lower bound. So, each entry in V 1 is at least now the reverse. So, combine M 0 with the smaller part and the part with larger part ok. So, this will be the bound this again you show by similar arguments delta is less than equal to half and row sum in M is 1. So, based on this we will finish the proof next time.