[MUSIC] Now, let us speak about graphic representation of a Markov chain. An example is given here, actually we represent a Markov chain with a graph and graph such that each node in this graph corresponds to one state from the space or states. So 1 node is 1 state. And we connect nodes number i and j with an arc. If and only if the probability to get the state j, if on the previous steps this history wasn't in the state i is not equal to 0. In other words, if pij is not equal to 0. If otherwise pij is equal to 0, then the corresponding arc is emitted. So for instance, this Markov chain corresponds to the full link transition metrics. So its metrics has six columns and six rows. And in the first row, you have only two nonzero elements. Element number one and element number two, all others are zeroes. As for the second row, we have only one nonzero element. It's element number p to 3 so this element ll others are 0s. Also for the third role, we can say that also only one element is on zero is this element. All other are zeros and so on, and so forth. So there is a correspondence between transition matrices and graphic representation, but this is not one by one correspondence. Because from this graph, we can say nothing about these x values of this unknown values stars. In the graph series, there is a notion of a walk. A walk is just a sequence of nodes says that any two sequential elements from this sequence are connected to each other with an arc. For instance, if there is a walk from one to three, you can go from one to two and from two to three. In the context of Markov chain, this notion gives us the following definition. We'll say that estate j is accessible. From estate i, if there is a walk from i to j. For instance here, you see that there is a walk from 1 to 3. But there is no walk from 1 to 4. We use this notation just i, then take an arrow j. So this means that j is accessible from i. With one more definition was says that states i and j communicate, If j is accessible from i and i is accessible from j. In this case, we just annotation i, j related to it arose in both directions. For instance, if you look at our picture, definitely states number 2 and 3 communicate. So look after relation between nodes as graph or it's the same as relation between states in the Markov chain. And actually, we can somehow cluster all nodes in this graph according to this operation. And to do this, we need one genuine mathematical concept, namely the concept of equivalence classes and I would like to recall what does it mean now. Let me first defines a notion of equivalence relation. Well, let epsilon be a set of any nature and we have some operator between, some relation between elements from y. I will note this relation by tilde and let me assume that this relation has the following three properties. First of all, for any element a from epsilon, a is related to itself. This is what is called reflectivity. Secondly, let me assume that if a and b are related then b and a are also related for a and two elements a and b from this epsilon. This is symmetry, of course. And certainly let me use it if a and b are related by this operator, and b. And c are related and a and c are also related for any a, b, and c from Y. This is transitivity. If all of these three operators, three properties are fulfilled, then this relation is called equivalence relation. An example of this relation can be the following one, if we can see it as a set of all people in the world and we can see there is in relation. The relation is they are sisters or brothers if we assume that somebody is a sister, or brother of himself or herself then definitely all of these three properties are fulfilled. Of course, if somebody is a brother for another people, then your separation is also true and also transitivity is fulfilled. And if you have an equivalence relation, then the set Y can be decomposed into non-intersectable unit of various subsets and these subsets are known as equivalence classes. It's very natural to define this class as follows to say, the two elements are in this class if they are related to each other by this operator. Of course, if you have division to some null is unacceptable equivalence classes, then you have also this equivalence relation. Because you can say that two elements are related by this operator if and only if they belong to one equivalence class. So equivalence classes and equivalence relations are the same. So it's the same to define either this object or this one. Let me return to Markov chain. Here, we have a natural candidate for this operator. I mean, that our operator which tells that two nodes communicate with each other. It's a very natural candidate. But nevertheless, some, let me say, degenerate situations can appear. For instance, it can be that one node in our graph has only outgoing arrows and no incoming arrow. This case corresponds to the situation when a column is in a transition matrix consist only in 0s. Of course, this is possible. Some matters can be and this situation is also possible. If you look at our picture, node number 4 is exactly the node of this type. And in this case, it's a bit unclear whether this not will constitute one equivalent class or not. So let me divide equivalents class in this situation. The finish in the falling one. So we will say that B1, B2 and so on are equivalent classes. If the following property's fulfilled. So for any element j from Bi and for any state key if k and j communicate, then k also belongs to Bi. And if k and j do not communicate, then k doesn't belong to Bi. And according to this definition of equivalent classes, we do not have any problems with states of this type. In fact, here on our example, we have four classes of equivalents. First class are the nodes number two and three. Second class on nodes number five and six, and also nodes number one, and four form a separate class. So in this situation, we have four classes of equivalents and it turns out that many characteristics of Markov chain are the same inside a class and let me discuss this more precisely in the next subsection. [MUSIC]