Now we discuss information diagrams for Markov Chains. If random variables X_1, X_2, up to X_n form a Markov Chain, then the structure of mu^* is much simpler and hence the information diagram can be simplified. For n equals 3, for example, X_1, X_2, X_3 forms a Markov chain if, and only if, I(X_1;X_3|X_2), is equal to 0. Or mu^* tilde{X_1}, intersects tilde{X_3} minus tilde{X_2}, is equal to 0. Therefore, the atom tilde{X_1} intersect tilde{X_3} minus tilde{X_2} can be suppressed in the information diagram. Suppose I(X_1;X_3|X_2) is equal to 0. Then, mu^*, tilde{X_1} intersect tilde{X_3} minus tilde{X_2} is equal to 0. This is indicated in the information diagram. Now, suppress the atom of tilde{X_1} intersect tilde{X_3} minus tilde{X_2} by setting it to the empty set. This can be achieved by displaying only the upper part of the information diagram. By redrawing the upper part of the information diagram, we obtain the information diagram at the bottom, which consists of three consecutive mountains representing X_1, X_2 and X_3. We now further discuss the structure of mu^* , for a Markov Chain X_1, X_2, X_3. In this information diagram, I(X_1;X_3|X_2), which is equal to mu^* tilde{X_1} intersect tilde{X_3}, this is given by the red dot in the diagram, minus tilde{X_2}, which is given by the four blue dots. So what we get is the empty set. And mu^* on the empty set is equal to 0. And therefore, I(X_1;X_3|X_2) is equal to 0. Also, consider the atom, tilde{X_1}, intersect tilde{X_2}, intersect tilde{X_3}, which is the atom shown here, is seen to be the intersection of X_1 and X_3. Therefore, the value of mu^* on tilde{X_1} intersect tilde{X_3} is equal to I(X_1;X_3) which is non-negative. Thus we have shown that mu^* tilde{X_1} intersect tilde{X_2} intersect tilde{X_3} is non-negative. Since the values of mu^* on all the remaining atoms correspond to Shannon's information measures and hence are non-negative, we conclude that mu^* is a measure. We have shown that for three random variables forming a Markov chain, the structure of mu^* can be simplified. And hence the information diagram can also be simplified. This theme can extended to four random variables forming a Markov chain. For the Markov Chain X_1, X_2, X_3 and X_4 it turns out that mu^* vanishes on the following five atoms. Because of this, the information diagram can be displayed in two dimensions. The values of mu^* on the remaining atoms correspond to Shannon's information measures and hence are non-negative. Thus, mu^* is a measure. This is the information diagram for four random variables X_1, X_2, X_3 and X_4 forming a Markov Chain. We now further discuss the structure of mu^* for the Markov Chain X_1, X_2, X_3 and X_4. We start with the generic information diagram for four random variables, X_1, X_2, X_3 and X_4, shown on the lower right corner. First we consider the Markov subchain, X_1, X_2, X_3, which implies that the mutual information between X_1 and X_3, given X_2, is equal to 0. Now, this mutual information can be written as a sum of two terms. The first being I(X_1;X_3;X_4|X_2), and I(X_1;X_3|X_2,X_4). You should try to verify this identity on information diagram. Notice that in this identity, X_1 and X_3 are unconditioned in all the terms, and X_2 is conditioned in all the terms. X_4 is unconditioned in the first term on the right hand side which in set theoretic representation correspond to taking the intersection with tilde{X_4}. And X_4 is conditioned on the second term on the right hand side, which in set theoretic representation, correspond to minus tilde{X_4}. Now, let the second term on the right hand side, which is a conditional mutual information, be equal to a, which is non-negative. Then, the value of the first term on the right hand side must be equal to minus a, because they add up to 0. This is shown in the information diagram. Next we consider the Markov subchain X_1, X_2, X_4, which implies the mutual information between X_1 and X_4, given X_2 is equal to 0. Again, we write this mutual information into two terms on the right hand side. The first term on the right hand side, namely I(X_1;X_3;X_4|X_2) is seen to be minus a. And so the second term must be equal to a, because the two terms add up to 0. This is shown in the information diagram. Now we consider the Markov Subchain X_1, X_3, X_4, which implies I(X_1;X_4|X_3) is equal to 0. Again we write this as the sum of two information measures. The second information measure is seen to be equal to a. And so the first information measure must be equal to minus a. This is indicated in the information diagram. We now consider the Markov subchain X_2, X_3 and X_4, which implies I(X_2;X_4|X_3) is equal to 0, and again this is written as the sum of two information measures, where the first information measure is seen to be minus a, and so the second one must be a. This is indicated in the information diagram. Finally, we consider the Markov subchain X_1, X_2 together X_3 and X_4, which implies I(X_1,X_2;X_4|X_3) is equal to 0. Now, this conditional mutual information can be written as the sum of three information measures. The first one is equal to a, the second is equal to minus a. And the third one is equal to a. This is indicated in blue in the information diagram, and therefore, we have, 0 equals a minus a plus a, which is equal to a. Therefore a is equal to 0, and so mu^* vanishes on the corresponding five atoms as shown in the information diagram. We now discuss the non-negativity of mu^* for the Markov Chain X_1, X_2, X_3, X_4. We have proved that mu^* vanishes on the five atoms shown in the information diagram. Suppress these atoms by setting them to the empty set to obtain the information diagram below. From this information diagram, it can readily be checked that the values of mu^* on the remaining 2 to the power 4 minus 1 minus 5 equals 10 non-empty atoms are equal to these information measures. These are all Shannon's information measures, which are always non-negative. Therefore, we have shown that mu^* is a measure. As an exercise, identify these ten atoms in the information diagram at the bottom. For a general n, the information diagram can be displayed in two dimensions because certain atoms can be suppressed. The values of mu^* on the remaining atoms correspond to Shannon's information measures and hence are non-negative. Therefore, mu^* continues to be a measure. See Chapter 12 for detailed discussion in the more general context of Markov random field.