# Gaussian Covariance Faithful Markov Trees

Authors: Dhafer Malouche; Bala Rajaratnam
Journal: Journal of Probability and Statistics
 (2011)

---

## Abstract

Graphical models are useful for characterizing conditional and marginal independence structures in high-dimensional distributions. An important class of graphical models is covariance graph models, where the nodes of a graph represent different components of a random vector, and the absence of an edge between any pair of variables implies marginal independence. Covariance graph models also represent more complex conditional independence relationships between subsets of variables. When the covariance graph captures or reflects all the conditional independence statements present in the probability distribution, the latter is said to befaithful to its covariance graph—though in general this is not guaranteed. Faithfulness however is crucial, for instance, in model selection procedures that proceed by testing conditional independences. Hence, an analysis of the faithfulness assumption is important in understanding the ability of the graph, a discrete object, to fully capture the salient features of the probability distribution it aims to describe. In this paper, we demonstrate that multivariate Gaussian distributions that have trees as covariance graphs are necessarily faithful.


---

## Body

## 1. Introduction

Markov random fields and graphical models are widely used to represent conditional independences in a given multivariate probability distribution (see [1–5], to name just a few). Many different types of graphical models have been studied in the literature. Concentration graphs encode conditional independence between pairs of variables given the remaining ones. Formally, let us consider a random vector X=(Xv,v∈V)′ with a probability distribution P where V is a finite set representing the random variables in X. An undirected graph G0=(V,E0) is called the covariance graph (see [1, 6–11]) associated with the probability distribution P if the set of edges E0 is constructed as follows: (1.1)(u,v)∉E0⟺Xu⫫Xv.
Note that (u,v)∉E means that the vertices u and v are not adjacent in G.Theconcentration graph associated with P is an undirected graph G=(V,E), where V is the set of vertices and each vertex represents one variable in X. The set E is the set of edges (between the vertices in V) constructed using the pairwise rule: for pair (u,v)∈V×V,u≠v,(1.2)(u,v)∉E⟺Xu⫫Xv∣XV∖{u,v},
where XV∖{u,v}∶=(Xw,w≠uandw≠v)′.Note that the subscript zero is invoked for covariance graphs (i.e.,G0 versus G) as the definition of covariance graphs does not involve conditional independences.Both concentration and covariance graphs not only are used to encode pairwise relationships between pairs of variables in the random vectorX, but as we will see below, these graphs can also be used to encode conditional independences that exist between subsets of variables of X. First, we introduce some definitions.The multivariate distributionP is said to satisfy the “intersection property” if for, any subsets A, B, C, and D of V which are pairwise disjoint,(1.3)XA⫫XB∣XC∪DandXA⫫XC∣XB∪DthenXA⫫XB∪C∣XD.We will call theintersection property (see [2]) in (1.3) above the concentration intersection property in this paper in order to differentiate it from another property that is satisfied by P when studying covariance graph models. Though this property can be further relaxed, we will retain the terminology used in [2].We first define the concept of separation on graphs. LetA, B, and S denote a pairwise disjoint set of vertices. We say that a set SseparatesA and B if all paths connecting A and B in G intersect S, that is, A⊥GB∣S. (This is not to be confused with stochastic independence which is denoted by ⫫ as compared to ⊥G.) Now, let P satisfy the concentration intersection property. Then, for any triplet (A,B,S) of subsets of V pairwise disjoint, if S separates A and B in the concentration graph G associated with P, then the random vector XA=(Xv,v∈A)′ is independent of XB=(Xv,v∈B)′ given XS=(Xv,v∈S)′. This latter property is called concentration global Markov property and is formally defined as(1.4)A⊥GB∣S⟹XA⫫XB∣XS.
Kauermann [6] shows that if P satisfies the following property: for any triplet (A,B,S) of subsets of V pairwise disjoint,(1.5)ifXA⫫XBandXA⫫XCthenXA⫫XB∪C,
then, for any triplet (A,B,S) of subsets of V pairwise disjoint, if S separates A and B in the covariance graph G0 associated with P, then XA⫫XB∣XV∖(A∪B∪S). This latter property is called the covariance global Markov property and can be written formally as follows:(1.6)A⊥G0B∣S⟹XA⫫XB∣XV∖(A∪B∪S).
In parallel to the concentration graph case, property (1.5) will be called the covariance intersection property and is sometimes also referred to as the composition property. Even if P satisfies both intersection properties, the covariance and concentration graphs may not be able to capture or reflect all the conditional independences present in the distribution; that is, there may exist one or more conditional independences present in the probability distribution that does not correspond to any separation statement in either G or G0. Equivalently, a lack of a separation statement in either G or G0 does not necessarily imply a conditional independence. On the contrary case when no other conditional independence exists in P except the ones encoded by the graph, we classify P as a faithful probability distribution to its graphical model (see [12]). More precisely, we say that P is concentration faithful to its concentration graph if, for any triplet (A,B,S) of subsets of V pairwise disjoint, the following statement holds:(1.7)A⊥GB∣S⟺XA⫫XB∣XS.
Similarly, P is said to be covariance faithful to its covariance graph G0 if, for any triplet (A,B,S) of subsets of V pairwise disjoint, the following statement holds:(1.8)A⊥G0B∣S⟺XA⫫XB∣XV∖(A∪B∪S).
A natural question of both theoretical and applied interest in probability theory is to understand the implications of the faithfulness assumption. This assumption is fundamental since it yields a bijection between the probability distribution P and the graph G in terms of the independences that are present in the distribution. In this paper, we show that when P is a multivariate Gaussian distribution, whose covariance graph is a tree, it is necessarily covariance faithful, that is, such probability distributions satisfy property (1.8). Equivalently, the associated covariance graph G is fully able to capture all the conditional independences present in the multivariate distribution P. This result can be considered as a dual of a previous probabilistic result proved by Becker et al. [13] for concentration graphs that demonstrates that Gaussian distributions having concentration trees (i.e., the concentration graph is a tree) are necessarily concentration faithful to its concentration graph (implying that property (1.7) is satisfied). This result was proved by showing that Gaussian distributions satisfy two types of conditional independence properties: the intersection property and the decomposable transitivity property. The approach in the proof of the main result of this paper is vastly different from the one used for concentration graphs (see [13]). Indeed, a naïve or unsuspecting reader could mistakenly think that the result for covariance trees follows simply by replacing the covariance matrix with its inverse in the result in Becker et al. [13]. This is of course incorrect and, in some sense, equivalent to saying that a matrix and its inverse are the same. The covariance matrix encodes marginal independences whereas the inverse covariance matrix encodes conditional independences. These are very different models. Moreover, the former is a curved exponential family model whereas the latter is a natural exponential family model.The outline of this paper is as follows. Section2 presents graph theory preliminaries. Section 2.2 gives a brief overview of covariance and concentration graphs associated with multivariate Gaussian distributions. The proof of the main result of this paper is given in Section 3. Section 4 concludes by summarizing the results in the paper and the implications thereof.


## 2. Preliminaries

### 2.1. Graph Theoretic Concepts

This section introduces notation and terminology that is required in subsequent sections. An undirected graphG=(V,E) consists of two sets V and E, with V representing the set of vertices, and E⊆(V×V)∖{(u,u),u∈V} the set of edges satisfying, forall(u,v)∈E⇔(v,u)∈E. For u,v∈V, we write u~Gv when (u,v)∈E and we say that u and v are adjacent in G. A path connecting two distinct vertices u and v in G is a sequence of distinct vertices (u0,u1,…,un), where u0=u and un=v, where, for every i=0,…,n-1, ui~Gui+1. Such a path will be denoted p=p(u,v,G) and we say that p(u,v,G) connects u and v or alternatively u and v are connected by p(u,v,G). We also denote by 𝒫(u,v,G) the set of paths between u and v. We now proceed to define the subclass of graphs known as trees. Let G=(V,E) be an undirected graph. The graph G is called a tree if any pair of vertices (u,v) in G is connected by exactly one path; that is, |𝒫(u,v,G)|=1forallu,v∈V. A subgraph of Ginduced by a subset U⊆V is denoted by GU=(U,EU), U⊆V and EU=E∩(U×U). A connected component of a graph G is the largest subgraph GU=(U,EU) of G such that each pair of vertices can be connected by at least one path in GU. We now state a lemma, without proof, that is needed in the proof of the main result of this paper.Lemma 2.1.
LetG=(V,E) be an undirected graph. If G is a tree, then any subgraph of G induced by a subset of V is a union of connected components, each of which are trees (or what we will refer to as a “union of tree connected components”).For a connected graph, aseparator is a subset S of V such that there exists a pair of nonadjacent vertices u and v such that u, v∉S and(2.1)∀p∈P(u,v,G),p∩S≠∅.
If S is a separator, then it is easily verified that every S′⊇S such that S′⊆V∖{u,v} is also a separator.


### 2.2. Gaussian Concentration and Covariance Graphs

In this section, we present a brief overview of concentration and covariance graphs in the case when the probability distributionP is multivariate Gaussian. Consider a random variable X~𝒩(0,Σ), where μ∈IR|V| and Σ=(σuv)∈ℙ+, where ℙ+ denotes the cone of positive definite matrices. Without loss of generality, we will assume that μ=0. Gaussian distributions can also be parameterized by the inverse of the covariance matrix Σ denoted by K=Σ-1=(kuv). The matrix K is called the precision or concentration matrix. It is well known (see [2]) that for any pair of variables (Xu,Xv), where u≠v, Xu⫫Xv∣XV∖{u,v}⇔kuv=0. Hence, the concentration graph G=(V,E) can be constructed simply using the precision matrix K and the following rule: (u,v)∉E⇔kuv=0. Furthermore, it can be easily deduced from a classical result (see [2]) that for any Gaussian concentration graph model the pairwise Markov property in (1.2) is equivalent to the concentration global Markov property in (1.4).As seen earlier in (1.1) covariance graphs on the other hand are constructed using pairwise marginal independence relationships. It is also well known that, for multivariate Gaussian distributions, Xu⫫Xv⇔σuv=0. Hence, in the Gaussian case, the covariance graph G0=(V,E0) can be constructed using the following rule: (u,v)∉E0⇔σuv=0. It is also easily seen that Gaussian distributions satisfy the covariance intersection property defined in (1.5). Hence, Gaussian covariance graphs can also encode conditional independences according to the following rule: for any triplet (A,B,S) of subsets of V pairwise disjoint, if S separates A and B in the covariance graph G0, then XA⫫XB∣XV∖(A∪B∪S).


## 2.1. Graph Theoretic Concepts

This section introduces notation and terminology that is required in subsequent sections. An undirected graphG=(V,E) consists of two sets V and E, with V representing the set of vertices, and E⊆(V×V)∖{(u,u),u∈V} the set of edges satisfying, forall(u,v)∈E⇔(v,u)∈E. For u,v∈V, we write u~Gv when (u,v)∈E and we say that u and v are adjacent in G. A path connecting two distinct vertices u and v in G is a sequence of distinct vertices (u0,u1,…,un), where u0=u and un=v, where, for every i=0,…,n-1, ui~Gui+1. Such a path will be denoted p=p(u,v,G) and we say that p(u,v,G) connects u and v or alternatively u and v are connected by p(u,v,G). We also denote by 𝒫(u,v,G) the set of paths between u and v. We now proceed to define the subclass of graphs known as trees. Let G=(V,E) be an undirected graph. The graph G is called a tree if any pair of vertices (u,v) in G is connected by exactly one path; that is, |𝒫(u,v,G)|=1forallu,v∈V. A subgraph of Ginduced by a subset U⊆V is denoted by GU=(U,EU), U⊆V and EU=E∩(U×U). A connected component of a graph G is the largest subgraph GU=(U,EU) of G such that each pair of vertices can be connected by at least one path in GU. We now state a lemma, without proof, that is needed in the proof of the main result of this paper.Lemma 2.1.
LetG=(V,E) be an undirected graph. If G is a tree, then any subgraph of G induced by a subset of V is a union of connected components, each of which are trees (or what we will refer to as a “union of tree connected components”).For a connected graph, aseparator is a subset S of V such that there exists a pair of nonadjacent vertices u and v such that u, v∉S and(2.1)∀p∈P(u,v,G),p∩S≠∅.
If S is a separator, then it is easily verified that every S′⊇S such that S′⊆V∖{u,v} is also a separator.


## 2.2. Gaussian Concentration and Covariance Graphs

In this section, we present a brief overview of concentration and covariance graphs in the case when the probability distributionP is multivariate Gaussian. Consider a random variable X~𝒩(0,Σ), where μ∈IR|V| and Σ=(σuv)∈ℙ+, where ℙ+ denotes the cone of positive definite matrices. Without loss of generality, we will assume that μ=0. Gaussian distributions can also be parameterized by the inverse of the covariance matrix Σ denoted by K=Σ-1=(kuv). The matrix K is called the precision or concentration matrix. It is well known (see [2]) that for any pair of variables (Xu,Xv), where u≠v, Xu⫫Xv∣XV∖{u,v}⇔kuv=0. Hence, the concentration graph G=(V,E) can be constructed simply using the precision matrix K and the following rule: (u,v)∉E⇔kuv=0. Furthermore, it can be easily deduced from a classical result (see [2]) that for any Gaussian concentration graph model the pairwise Markov property in (1.2) is equivalent to the concentration global Markov property in (1.4).As seen earlier in (1.1) covariance graphs on the other hand are constructed using pairwise marginal independence relationships. It is also well known that, for multivariate Gaussian distributions, Xu⫫Xv⇔σuv=0. Hence, in the Gaussian case, the covariance graph G0=(V,E0) can be constructed using the following rule: (u,v)∉E0⇔σuv=0. It is also easily seen that Gaussian distributions satisfy the covariance intersection property defined in (1.5). Hence, Gaussian covariance graphs can also encode conditional independences according to the following rule: for any triplet (A,B,S) of subsets of V pairwise disjoint, if S separates A and B in the covariance graph G0, then XA⫫XB∣XV∖(A∪B∪S).


## 3. Gaussian Covariance Faithful Trees

We now proceed to study the faithfulness assumption in the context of multivariate Gaussian distributions and when the associated covariance graphs are trees. The main result of this paper, presented in Theorem3.1, proves that multivariate Gaussian probability distributions having tree covariance graphs are necessarily faithful to their covariance graphs; that is, all of the independence and dependences in P can be read by using graph separation. We now formally state Theorem 3.1. The proof follows shortly after a series of lemmas/theorem(s) and an illustrative example.Theorem 3.1.
LetXV=(Xv,v∈V)′ be a random vector with Gaussian distribution P=𝒩|V|(μ,Σ). Let G0=(V,E0) be the covariance graph associated with P. If G0 is a disjoint union of trees, then P is covariance faithful to G0.The proof of Theorem3.1 requires, among others, a result that gives a method to compute the covariance matrix Σ from the precision matrix K using the paths in the concentration graph G. The result can also be easily extended to show that the precision matrix K can be computed from the covariance matrix Σ using the paths in the covariance graph G0. We now formally state this result.Lemma 3.2.
LetXV=(Xv,v∈V)′ be a random vector with Gaussian distribution P=𝒩|V|(μ,Σ), where Σ and K=Σ-1 are positive definite matrices. Let G=(V,E) and G0=(V,E0) denote, respectively, the concentration and covariance graph associated with the probability distribution of XV. For all (u,v) in V×V,
(3.1)kuv=∑p∈P(u,v,G0)(-1)|p|+1|σ|p|Σ∖p||Σ|,σuv=∑p∈P(u,v,G)(-1)|p|+1|k|p|K∖p||K|,
where, if p=(u0,…,un), |σ|p=σu0u1σu1u2…σun-1un,|k|p=ku0u1ku1u2…kun-1un, K∖p=(kuv,(u,v)∈(V∖p)×(V∖p))andΣ∖p=(σuv,(u,v)∈(V∖p)×(V∖p)) denote, respectively, K and Σ with rows and columns corresponding to variables in path p omitted. The determinant of a zero-dimensional matrix is defined to be 1.The lemma above follows immediately from a basic result in linear algebra which gives the cofactor expression for the inverse of a square matrix. In particular, for an invertible matrixA, its inverse A-1 can be expressed as follows:(3.2)A-1=1det⁡(A)adj(A),whereadj(A)denotestheadjointofA.A simple proof can be found in Brualdi and Cvetkovic [14]. The result has been rediscovered in other contexts (see [15]), but, as noted above, it follows immediately from the expression for the inverse of a matrix.The proof of our main theorem (Theorem3.1) also requires the results proved in the lemma below.Lemma 3.3.
LetXV=(Xv,v∈V)′ be a random vector with Gaussian distribution P=𝒩|V|(μ,K=Σ-1). Let G0=(V,E0) and G=(V,E) denote, respectively, the covariance and concentration graphs associated with P, then  (i)
G and G0 have the same connected components,(ii)
if a given connected component inG0 is a tree, then the corresponding connected component in G is complete and vice versa.Proof.
Proof of (i): the fact thatG0 and G have the same connected components can be deduced from the matrix structure of the covariance and the precision matrix. The connected components of G0 correspond to block diagonal matrices in Σ. Since K=Σ-1, then, by properties of inverting partitioned matrices, K also has the same block diagonal matrices as Σ in terms of the variables that constitute these matrices. These blocks correspond to distinct components in G and G0. Hence, both matrices have the same connected components.
Proof of (ii): let us assume now that the covariance graphG0 is a tree, hence it is a connected graph with only one connected component. We will prove that the concentration graph G is complete by using Lemma 3.2 and computing any coefficient kuv (u≠v). Since G0 is a tree, there exists exactly one path between any two vertices u and v. We will denote this path as p=(u0=u,…,un=v). Then, by Lemma 3.2,
(3.3)kuv=(-1)n+1σu0u1…σun-1un|Σ∖p||Σ|.
First, note that the determinants of the matrices in (3.3) are all positive since principal minors of positive definite matrices are positive. Second, since we are considering a path in G0, σui-1ui≠0, foralli=1,…,n. Using these two facts, we deduce from (3.3) that kuv≠0 for all (u,v)∈E. Hence, u and v are adjacent in G for all (u,v)∈E. The concentration graph G is therefore complete. The proof that when G is assumed to be a tree implying that G0 is complete follows similarly.We now give an example illustrating the main result in this paper (Theorem3.1).Example 3.4.
Consider a Gaussian random vectorX=(X1,…,X8)′ with covariance matrix Σ and its associated covariance graph (which is a tree) as given in Figure 1(a).
Consider the setsA={1,2}, B={5}, and S={4,6}. Note that S does not separate A and B in G0 as any path from A and B does not intersect S. Hence, we cannot use the covariance global Markov property to claim that XA is not independent of XB given XV∖(A∪B∪S). This is because the covariance global Markov property allows us to read conditional independences present in a distribution if a separation is present in the graph. It is not an “if and only if” property in the sense that the lack of a separation in the graph does not necessarily imply the lack of the corresponding conditional independence. We will show however that in this example XA is indeed not independent of XB given XV∖(A∪B∪S). In other words, we will show that the graph has the ability to capture this conditional dependence present in the probability distribution P.
Let us now examine the relationship betweenX2 and X5 given X{3,7,8}. Note that in this example V∖(A∪B∪S)={3,8,7}, 2∈A, and 5∈B. Note that the covariance graph associated with the probability distribution of the random vector (X2,X5,X{3,8,7})′ is the subgraph represented in Figure 1(b) and can be obtained directly as a subgraph of G0 induced by the subset {2,5,3,7,8}.
Since 2 and 5 are connected by exactly one path in(G0){2,5,3,7,8}, that is, p=(2,3,5), then the coefficient k25∣387, that is, the coefficient between 2 and 5 in inverse of the covariance matrix of (X2,X5,X{3,8,7})′, can be computed using Lemma 3.2 as follows:
(3.4)k25∣387=(-1)2+1σ23σ35|Σ({8,7})||Σ({2,5,3,8,7})|,
where Σ({7,8}) and Σ({2,5,3,8,7}) are, respectively, the covariance matrices of the Gaussian random vectors (X7,X8)′ and (X2,X5,X{3,8,7})′. Hence, k25∣387≠0 since the right hand side of the equation in (3.4) is different from zero. Hence, X2⫫X5∣X{3,8,7}.
Now, recall that, for any Gaussian random vectorXV=(Xu,u∈V)′,
(3.5)XA⫫XB∣XSiff∀(u,v)∈A×B,Xu⫫Xv∣XS,
where A, B, and S are pairwise disjoint subsets of V. The contrapositive of (3.5) yields
(3.6)X2⫫X5∣X{3,7,8}⟹X{1,2}⫫X5∣X{3,7,8}.
Hence, we conclude that since{4,6} does not separate {1,2} and {5}, X{1,2} is not independent of X5 given X{3,7,8}. Thus, we obtain the desired result:
(3.7){1,2}⊥G0{5}∣{4,6}⟹X{1,2}⫫X5∣X{3,7,8}.Covariance graph in Example3.4.
(a)
An 8-vertex covariance treeG0(b)
Sub-graph(G0){2,5,3,8,7}We now proceed to the proof of Theorem3.1.Proof of Theorem3.1.
Without loss of generality, we assume thatG0 is a connected tree. Let us assume to the contrary that P is not covariance faithful to G0, then there exists a triplet (A,B,S) of pairwise disjoint subsets of V, such that XA⫫XB∣XV∖(A∪B∪S), but S does not separate A and B in G0, that is,
(3.8)XA⫫XB∣XV∖(A∪B∪S),A⊥G0B∣S.
AsS does not separate A and B and since G0 is a connected tree, then there exists a pair of vertices (u,v)∈A×B such that the single path p connecting u and v in G0 does not intersect S; that is, S∩p=∅. Hence, p⊆V∖S=(A∪B)∪(V∖(A∪B∪S)). Thus, two cases are possible with regard to where the path p can lie: either p⊆A∪B or p∩(V∖(A∪B∪S))≠∅. Let us examine both cases separately.
Case 1 (p⊆A∪B).
In this case, the entire path betweenu and v lies in A∪B and hence we can find a pair of vertices  (u′,v′) belonging to p and (u′,v′)∈A×B such that u′~G0v′. (As an illustration of this point, consider the graph presented in Figure 1(a). Let A={1,2}, B={3,5}, and S={4,6}. We note that the path p=(1,2,3,5) lies entirely in A∪B and hence we can find two vertices, namely, 2∈A and 3∈B, belonging to path p that are adjacent in G0).Recall that since G0 is a tree, any induced graph of G0 by a subset of V is a union of tree connected components (see Lemma 2.1). Hence, the subgraph (G0)W of G0 induced by W={u′,v′}∪V∖(A∪B∪S) is a union of tree connected components. As u′ and v′ are adjacent in G0, they are also adjacent in (G0)W and belong to the same connected component of (G0)W. (In our example in Figure 1(a) with W={2,3,8,7}, (G0)W consists of a union of two connected components with its respective vertices being {2,3} and {8,7}.) Hence, the only path between u′ and v′ is precisely the edge (u′,v′). Using Lemma 3.2 to compute the coefficient ku′v′∣V∖(A∪B∪S), that is, (u′,v′)th coefficient in the inverse of the covariance matrix of the random vector XW=(Xw,w∈W)′=(Xu′,Xv′,XV∖(A∪B∪S))′, we obtain,
(3.9)ku′v′∣V∖(A∪B∪S)=(-1)1+1σu′v′|Σ(W∖{u′,v′})||Σ(W)|,
where Σ(W) denotes the covariance matrix of XW and Σ(W∖{u′,v′}) denotes the matrix Σ(W) with the rows and the columns corresponding to variables Xu′ and Xv′ omitted. We can therefore deduce from (3.9) that ku′v′∣V∖(A∪B∪S)≠0. Hence, Xu′⫫Xv′∣XV∖(A∪B∪S). Now, since P is Gaussian, u′∈A, and v′∈B, we can apply (3.5) to arrive at a contradiction to our initial assumption in (3.8).Note in the case that V∖(A∪B∪S) is empty the path p has to lie entirely in A∪B. This is because by assumption p does not intersect S. The case when p lies in A∪B is covered in Case 1 and hence it is assumed that V∖(A∪B∪S)≠∅. (As an illustration of this point, consider once more the graph presented in Figure 1(a). Consider A={1,2}, B={7,8}, and S={4,6}. Here, V∖(A∪B∪S)={3,5} and the path p=(1,2,3,5,7,8) connecting A and B intersects V∖(A∪B∪S).) Case 2 (p∩(V∖(A∪B∪S))≠∅ and V∖(A∪B∪S)≠∅).
In this case, there exists a pair of vertices(u′,v′)∈A×B with u′,v′∈p, such that the vertices u′ and v′ are connected by exactly one path p′⊆p in the induced graph (G0)W of G0 by W={u′,v′}∪V∖(A∪B∪S) (see Lemma 2.1). (In our example in Figure 1 with A={1,2}, B={7,8}, and S={4,6}, the vertices u′ and v′ will correspond to vertices 2 and 7, respectively, and p′=(2,3,5,7), which is a path entirely contained in {u′,v′}∪(V∖(A∪B∪S).)
Let us now use Lemma3.2 to compute the coefficient ku′v′∣V∖(A∪B∪S), that is, the (u′,v′)-coefficient in the inverse of the covariance matrix of the random vector XW=(Xw,w∈W)′=(Xu′,Xv′,XV∖(A∪B∪S))′. We obtain that
(3.10)ku′v′∣V∖(A∪B∪S)=(-1)|p′|+1|σp′||Σ(W∖p′)||Σ(W)|,
where Σ(W) denotes the covariance matrix of XW and Σ(W∖p′) denotes Σ(W) with the rows and the columns corresponding to variables in path p′ omitted. One can therefore easily deduce from (3.10) that ku′v′∣V∖(A∪B∪S)≠0. Thus, Xu′ is not independent of Xv′ given XV∖(A∪B∪S). Hence, once more we obtain a contradiction to (3.5) since u′∈A and v′∈B.Remark 3.5.
The dual result of the theorem above for the case of concentration trees was proved by Becker et al. [13]. We note however that the argument used in the proof of Theorem 3.1 cannot also be used to prove faithfulness of Gaussian distributions that have trees as concentration graphs. The reason for this is as follows. In our proof, we employed the fact that the subgraph (G0){u,v}∪S of G0 induced by a subset {u,v}∪S⊆V is also the covariance graph associated with the Gaussian subrandom vector of XV as denoted by X{u,v}∪S=(Xw,w∈{u,v}∪S)′. Hence, it was possible to compute the coefficient kuv∣S which quantifies the conditional (in)dependence between u and v given S, in terms of the paths in (G0){u,v}∪S and the coefficients of the covariance matrix of X{u,v}∪S=(Xw,w∈{u,v}∪S)′. On the contrary, in the case of concentration graphs the sub-graph G{u,v}∪S of the concentration graph G induced by {u,v}∪S is not in general the concentration graph of the random vector X{u,v}∪S=(Xw,w∈{u,v}∪S)′. Hence our approach is not directly applicable in the concentration graph setting.


## 4. Conclusion

In this note we looked at the class of multivariate Gaussian distributions that are Markov with respect to covariance graphs and prove that Gaussian distributions which have trees as their covariance graphs are necessarily faithful. The method of proof used in the paper is also vastly different in nature from the proof of the analogous result for concentration graph models. Hence, the approach that is used could potentially have further implications. Future research in this area will explore if the analysis presented in this paper can be extended to other classes of graphs or distributions.



---

*Source: 152942-2011-12-11.xml*