# Gaussian Covariance faithful Markov Trees

Dhafer Malouche
Ecole Supérieure de la Statistique
et de l’Analyse de l’Information, Tunisia.
<EMAIL_ADDRESS>

and

Bala Rajaratnam
Standford University, USA.
<EMAIL_ADDRESS>
###### Abstract

A covariance graph is an undirected graph associated with a multivariate
probability distribution of a given random vector where each vertex represents
each of the different components of the random vector and where the absence of
an edge between any pair of variables implies marginal independence between
these two variables. Covariance graph models have recently received much
attention in the literature and constitute a sub-family of graphical models.
Though they are conceptually simple to understand, they are considerably more
difficult to analyze. Under some suitable assumption on the probability
distribution, covariance graph models can also be used to 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 be faithful to its covariance graph - though no such prior guarantee
exists. Despite the increasingly widespread use of these two types of
graphical models, to date no deep probabilistic analysis of this class of
models, in terms of the faithfulness assumption, is available. Such an
analysis is crucial 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.
The method of proof is original as it uses an entirely new approach and in the
process yields a technique that is novel to the field of graphical models.

##  1 Introduction

Markov random fields or graphical models are widely used to represent
conditional independences in a given multivariate probability distribution
(see Kunsch et al., (1995), Ji & Seymour, (1996), Spitzer, (1975), Kindermann
& Snell, (1980), Lauritzen, (1996) to name just a few). Many different types
of Markov Random fields or graphical models have been studied in the
literature. For example, directed acyclic graphs or DAGs are commonly referred
to as “Bayesian networks” (see Pearl, (1988)). When the graph is undirected
and when such graphs are constructed using marginal independence relationships
between pairs of random variables in a given random vector these graphical
models are called “covariance graph” models (see Cox & Wermuth, (1993), Cox &
Wermuth, (1996), Kauermann, (1996), Malouche & Rajaratnam, (2009) and Khare &
Rajaratnam, (2009)). Covariance graph models are commonly represented by
graphs with exclusively bi-directed or dashed edges (see Kauermann, (1996)).
This representation is used in order to distinguish them from the traditional
and widely used concentration graph models. Concentration graphs encode
conditional independence between pairs of variables given the remaining ones.
Formally, if we consider a random vector $\mathbf{X}=(X_{v},v\in V)^{\prime}$
with a probability distribution $P$ where $V$ is a finite set representing the
random variables in $\mathbf{X}$. The concentration graph associated with $P$
is an undirected graph $G=(V,E)$ where

  * •

$V$ is the set of vertices.

  * •

Each vertex represents one variable in $\mathbf{X}$.

  * •

$E$ is the set of edges (between the verices in $V$) constructed using the
pairwise rule : for pair $(u,v)\in V\times V$, $u\not=v$

$(u,v)\not\in
E\;\iff\;X_{u}\,\bot\bot\,X_{v}\mid\mathbf{X}_{V\setminus\\{u,v\\}}$ (1)

where $\mathbf{X}_{V\setminus\\{u,v\\}}:=(X_{w},\,w\not=u\mbox{ and
}w\not=v)^{\prime}$.

Note that $(u,v)\not\in E$ means that the vertices $u$ and $v$ are not
adjacent in $G$.

An undirected graph $G_{0}=(V,E_{0})$ is called the covariance graph
associated with the probability distribution $P$ if the set of edges $E_{0}$
is constructed as follows

$(u,v)\not\in E\;\iff\;X_{u}\,\bot\bot\,X_{v}$ (2)

The subscript zero is invoked for covariance graphs (i.e., $G_{0}$ vs $G$) as
the definition of covariance graphs does not involve conditional
independences.

Both concentration and covariance graphs are not only used to encode pairwise
relationships between pairs of variables in the random vector $\mathbf{X}$,
but as we will see below, these graphs can be used to encode conditional
independences that exist between subsets of variables of $\mathbf{X}$. First
we introduce some definitions:

The multivariate distribution $P$ is said to satisfy the “intersection
property” if for any subsets $A$, $B$ $C$ and $D$ of $V$ which are pairwise
disjoint,

$\left\\{\begin{array}[]{lcl}\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{C\cup
D}&&\\\ \mbox{and }&\mbox{ then }&\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B\cup
C}\mid\mathbf{X}_{D}\\\
\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{C}\mid\mathbf{X}_{B\cup D}&&\\\
\end{array}\right.$ (3)

We will call the intersection property (see Lauritzen, (1996)) in (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.

Let $P$ satisfy the concentration intersection property. Then for any triplet
$(A,B,S)$ of subsets of $V$ pairwise disjoint, if $S$ separates111We say that
$S$ separates $A$ and $B$ if any path connecting $A$ and $B$ in $G$ intersects
$S$, i.e., $A\bot_{G}B\mid S$, and is not to be confused with stochastic
independence which is denoted by $\,\bot\bot\,$ as compared to $\bot_{G}$. $A$
and $B$ in the concentration graph $G$ associated with $P$ then the random
vector $\mathbf{X}_{A}=(X_{v},\,v\in A)^{\prime}$ is independent of
$\mathbf{X}_{B}=(X_{v},\,v\in B)^{\prime}$ given $\mathbf{X}_{S}=(X_{v},\,v\in
S)^{\prime}$. This latter property is called concentration global Markov
property and is formally defined as,

$A\bot_{G}B\mid
S\;\Rightarrow\;\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}.$
(4)

Kauermann, (1996) and Banerjee & Richardson, (2003) show that if $P$ satisfies
the following property : for any triplet $(A,B,S)$ of subsets of $V$ pairwise
disjoint,

$\mbox{ if }\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mbox{ and
}\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{C}\;\mbox{ then
}\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B\cup C},$ (5)

then for any triplet $(A,B,S)$ of subsets of $V$ pairwise disjoint, if
$V\setminus(A\cup B\cup S)$ separates $A$ and $B$ in the covariance graph
$G_{0}$ associated with $P$ then
$\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}$. This latter
property is called the covariance global Markov property and can be written
formally as follows

$A\bot_{G_{0}}B\mid V\setminus(A\cup B\cup
S)\;\Rightarrow\;\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}.$
(6)

In parallel to the concentration graph case, property (5) will be called the
covariance intersection 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, i.e., 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 $G_{0}$.
Equivalently, a lack of a separation statement in the graph does not
necessarily imply conditional independences. On the contrary case when no
other conditional independence exist in $P$ except the ones encoded by the
graph, we classify $P$ as a faithful probability distribution to its graphical
model. 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 :

$S\mbox{ separates }A\mbox{ and
}B\;\iff\;\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}.$ (7)

Similarly, $P$ is said to be covariance faithful to its covariance graph
$G_{0}$ if for any triplet $(A,B,S)$ of subsets of $V$ pairwise disjoint, the
following statement holds :

$V\setminus(A\cup B\cup S)\mbox{ separates }A\mbox{ and
}B\;\iff\;\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}.$ (8)

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 are trees are
necessarily covariance faithful, i.e., these probability distributions satisfy
property (8), i.e., 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., (2005) 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 property (7) is satisfied). This result
was proved by showing that Gaussian distributions satisfy an additional
intersection property. The approach in the proof of the main result of this
paper is vastly different from the one used for concentration graphs by Becker
et al., (2005).

The outline of this paper is follows. Section 2 presents graph theory
preliminaries. Section 3 gives a brief overview of covariance and
concentration graphs associated with multivariate Gaussian distributions.
Furthermore, an easier way to encode conditional independence using covariance
graphs is given in Section 3. The prove of the main result of this paper is
given in Section 4. Section 5 concludes by summarizing the results in the
paper and the implications thereof.

##  2 Graph theory preliminaries

This section introduces notation and terminology that is required in
subsequent sections. An undirected graph $G=(V,E)$ consists of two sets $V$
and $E$, with $V$ representing the set of vertices, and $E\subseteq(V\times
V)\setminus\\{(u,u),\,u\in V\\}$ the set of edges satisfying :

$\forall\;(u,v)\in E\,\iff\,(v,u)\in E$

For $u,\,v\in V$, we write $u\sim_{G}v$ when $(u,v)\in E$ and we say that $u$
and $v$ are adjacent in $G$.

###### Definition 1

A path connecting two distinct vertices $u$ and $v$ in $G$ is a sequence of
distinct vertices $\left(u_{0},u_{1},\ldots,u_{n})\right)$ where $u_{0}=u$ and
$u_{n}=v$ where for every $i=0,\ldots,n-1$, $u_{i}\sim_{G}u_{i+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)$. Its
length, denoted by $|p(u,v,G)|$, is defined as the number of edges connecting
the vertices of $p$. So, in this case $|p(u,v,G)|=n$. We also denote by
$\mathcal{P}(u,v,G)$ the set of paths between $u$ and $v$.

Trees are a particular class of graphs that are studied in this paper. This
class of graphs are formally defined below.

###### Definition 2

Let $G=(V,E)$ be an undirected graph. The graph $G$ is called a tree if any
pair of vertices $(u,v)$ in $G$ are connected by exactly one path, i.e.,
$|\mathcal{P}(u,v,G)|=1\;\;\forall\;u,v\in V$.

A subgraph of $G$ induced by a subset $U\subseteq V$ is denoted by
$G_{U}=(U,E_{U})$, $U\subseteq V$ and $E_{U}=E\cap(U\times U)$.

###### Definition 3

A connected component of a graph $G$ is the largest subgraph $G_{U}=(U,E_{U})$
of $G$ such that each pair of vertices can be connected by at least one path
in $G_{U}$.

We now state a Lemma needed in the proof of the main result of this paper.

###### Lemma 1

Let $G=(V,E)$ be an undirected graph. If $G$ is a tree, any subgraph of $G$
induced by a subset of $V$ is a union of connected components, each of which
are trees (or what we shall refer to as a “union of tree connected
components”).

Proof. Consider $U\subset V$, the induced graph $G_{U}$ and a pair of vertices
$(u,v)\in U\times U$. Let us assume to the contrary that $u$ and $v$ are
connected by two distinct paths $p_{1}$ and $p_{2}$ in $G_{U}$ (i.e., $G_{U}$
is not a tree). As the set of edges $E_{U}$ of the graph $G_{U}$ is included
in the set of edges $E$ of $G$, i.e., $E_{U}=E\cap(U\times U)\subseteq E$,
then $p_{1}$ and $p_{2}$ are also paths in $G$. Hence $u$ and $v$ are vertices
in $G$ which are connected by two distinct paths, i.e., $p_{1}$ and $p_{2}$.
This of course yields a contradiction with the fact that $G$ is a tree. Thus
any pair of vertices in $G_{U}$ are connected by at most one path and, hence
$G_{U}$ is a union of connected components, each of which are trees (or a
“union of tree connected components”).

###### Definition 4

For a connected graph, a separator is a subset $S$ of $V$ such that there
exists a pair of non-adjacent vertices $u$ and $v$ such that $u,$ $v\not\in S$
and

$\forall p\in\mathcal{P}(u,v,G),\;\;p\cap S\not=\emptyset$ (9)

If $S$ is a separator then it is easily verified that every
$S^{\prime}\supseteq S$ such that $S^{\prime}\subseteq V\setminus\\{u,v\\}$ is
also a separator. We are thus lead to the notion of a minimal separator.

###### Definition 5

The separator $S$ is defined to be a minimal separator between two non-
adjacent vertices $u$ and $v$ if for any $w\in S$, the subsets
$S\setminus\\{w\\}$ is not a separator of $u$ and $v$.

Note that in the case where $G$ contains more than two connected components
and if $u$ and $v$ belong to different connected components the empty set is
the only possible separator of $u$ and $v$. Finally, let $A$, $B$ and $S$ be
pairwise disjoint subsets of $V$. We say that $S$ separates $A$ and $B$ if for
any pair of vertices $(u,v)\in A\times B$, any path connecting $u$ and $v$
intersects $S$. In the case where $A$ and $B$ belong to different connected
components of $G$ the subset $S$ can be empty because the set of paths between
any pair of vertices $(u,v)\in A\times B$ is empty.

##  3 Gaussian Concentration and Covariance Graphs

In this section we present a brief overview of concentration and covariance
graphs in the case when the probability distribution $P$ is multivariate
Gaussian. Such graphical models are commonly referred to as Gaussian
covariance or Gaussian concentration graph models.

###  3.1 Gaussian concentration graph models

Consider a probability space with triplet $(\Omega,{\cal F},\mathbb{P})$ and
let $\mathbf{X}\,:\,\Omega\rightarrow\mathbb{R}^{|V|}$ be a random vector
where $\mathbf{X}=(X_{v},\,v\in V)^{\prime}$ and $P$ represents the induced
measure of $\mathbb{P}$ by $\mathbf{X}$. If $\mathbf{X}$ follows a Gaussian
distribution then it has the following density function with respect to
Lebesgue measure :

$f(\mathbf{x})=\frac{1}{(2\pi)^{|V|/2}|\Sigma|^{1/2}}\,\exp\left(-\frac{1}{2}(\mathbf{x}-\mathbf{\mu})^{\prime}\Sigma^{-1}(\mathbf{x}-\mathbf{\mu})^{\prime}\right),$
(10)

where $\mathbf{x}=(x_{u},\,u\in V)^{\prime}\in{\rm IR}^{|V|}$,
$\mathbf{\mu}\in{\rm IR}^{|V|}$ is the mean vector and
$\Sigma=(\sigma_{uv})\in\mathcal{P}^{+}$ is the covariance matrix with
$\mathcal{P}^{+}$ denoting the cone of symmetric positive definite matrices.
Without loss of generality we will assume that $\mathbf{\mu}=\mathbf{0}$. As
any Gaussian distribution with $\mathbf{\mu}=\mathbf{0}$ is completely
determined by its covariance matrix $\Sigma$, this set of multivariate
Gaussian distributions can therefore be identified by the set of symmetric
positive definite matrices. Gaussian distributions can also be parameterized
by the inverse of the covariance matrix $\Sigma$ denoted by
$K=\Sigma^{-1}=(k_{uv})$. The matrix $K$ is called the precision or
concentration matrix. It is well known (see Lauritzen, (1996)) that for any
pair of variables $(X_{u},X_{v})$, where $u\not=v$

$X_{u}\,\bot\bot\,X_{v}\mid\mathbf{X}_{V\setminus\\{u,v\\}}\;\iff\;k_{uv}=0.$

Hence the concentration graph $G=(V,E)$ can be constructed simply using the
precision matrix $K$ and the following rule

$(u,v)\not\in E\;\iff\;k_{uv}=0.$

Furthermore it can be easily deduced from a classical result in Hammersly &
Clifford, (1971), that is reproved in Lauritzen, (1996), that any multivariate
random vector with a positive density necessarily satisfies the concentration
intersection property (3). Hence for Gaussian concentration graph models the
pairwise Markov property in (1) is equivalent to the concentration global
Markov property in (4).

###  3.2 Gaussian covariance graph models

As seen earlier in (2) covariance graphs are constructed using pairwise
marginal independence relationships. It is also well known that for
multivariate Gaussian distributions :

$X_{u}\,\bot\bot\,X_{v}\;\iff\,\sigma_{uv}=0.$

Hence in the Gaussian case the covariance graph $G_{0}=(V,E_{0})$ can be
constructed using the following rule :

$(u,v)\not\in E_{0}\;\iff\;\sigma_{uv}=0.$

It is also easily seen that Gaussian distributions satisfy the covariance
intersection property defined in (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
$V\setminus(A\cup B\cup S)$ separates $A$ and $B$ in the covariance graph
$G_{0}$ then $\mathbf{X}_{A}\,\bot\bot\,\mathbf{X}_{B}\mid\mathbf{X}_{S}$. We
now show (see proposition 2 below) that there is a simple way to read
conditional independence statements from the covariance graph. This result
holds true for any probability distribution that satisfy the covariance
intersection property given in (5).

###### Proposition 2

Let $\textbf{X}_{V}=(X_{v},\,v\in V)^{\prime}$ be a random vector with
probability distribution $P$ satisfying the covariance intersection property
in (5) and let $G_{0}=(V,E_{0})$ be the covariance graph associated with $P$.
Then the following statements are equivalent,

  * i.

for any pairwise disjoint subsets $A$, $B$ and $S$ of $V$ : if
$V\setminus(A\cup B\cup S)$ separates $A$ and $B$ in $G_{0}$ then
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{S}$

  * ii.

for any pairwise disjoint subsets $A$, $B$ and $S$ of $V$ : if $S$ separates
$A$ and $B$ in $G_{0}$ then
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}$

Proof. Let us first assume that (i) is satisfied and let us prove (ii).

Let $A$, $B$ and $S$ be three pairwise disjoint subsets of $V$ such that $S$
separates $A$ and $B$ in $G_{0}$. Note that we can write $S$ as follows:

$S=V\setminus(V\setminus(A\cup B\cup S))\cup A\cup B)$

Since $(V\setminus(A\cup B\cup S)\cup A\cup B=V\setminus S$ and
$V\setminus(V\setminus S)=S$.

By hypothesis $S$ separates $A$ and $B$ in $G_{0}$. Let
$S^{\prime}=V\setminus(A\cup B\cup S)$ and since $S=V\setminus(S^{\prime}\cup
A\cup B)$ we can apply property (i) to the triplet $(A,B,S^{\prime})$. Hence
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{S^{\prime}}$. Hence
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(S\cup
A\cup B)}$ since $S^{\prime}:=V\setminus(S\cup A\cup B)$. We have therefore
proved that if $S$ separates $A$ and $B$ in $G_{0}$, then
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(S\cup
A\cup B)}$.

Assume now that property (ii) is satisfied and let $A$, $B$ and $S$ be three
pairwise disjoint subsets of $V$ such that $V\setminus(S\cup A\cup B)$
separates $A$ and $B$ in $G_{0}$. Let us denote by
$S^{\prime}=V\setminus(S\cup A\cup B)$ which is a subset separating $A$ and
$B$ in $G_{0}$. Since (ii) is satisfied, we deduce that
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S^{\prime})}$. However

$V\setminus(A\cup B\cup S^{\prime})=V\setminus((V\setminus(A\cup B\cup S))\cup
A\cup B)=S$

Hence we conclude that $V\setminus(A\cup B\cup S)$ separates $A$ and $B$ in
$G_{0}$ implies that
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{S}$. Thus property
(i) is satisfied.

Proposition 2 can be used to formulate an equivalent definition of the
covariance faithfulness property.

###### Definition 6

Let $\textbf{X}_{V}=(X_{v},\,v\in V)^{\prime}$ be a random vector with
probability distribution $P$ satisfying the covariance intersection property
in (5) and let $G_{0}=(V,E_{0})$ be the covariance graph associated with $P$.
We say that $P$ is covariance faithful to $G_{0}$ if for any pairwise disjoint
subsets $A$, $B$ and $S$ of $V$ the following condition is satisfied

$S\mbox{ separates }A\mbox{ and
}B\;\iff\;\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}$

The above reformulation of the covariance faithfulness property is an
important ingredient in the proofs in the next section.

##  4 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 Theorem 3, proves that
multivariate Gaussian probability distributions having tree covariance graphs
are necessarily faithful to their covariance graphs. The analogous result for
concentration graphs was demonstrated by Becker et al., (2005) where the
authors proved that Gaussian distributions having tree concentration graphs
are necessarily faithful to these graphs. We now formally state Theorem 3. The
proof follows shortly after a series of lemmas/theorem(s) and an illustrative
example.

###### Theorem 3

Let $\textbf{X}_{V}=(X_{v},\,v\in V)^{\prime}$ be a random vector with
Gaussian distribution $P=\mathcal{N}_{|V|}(\mu,\Sigma^{-1})$. Let
$G_{0}=(V,E_{0})$ be the covariance graph associated with $P$. If $G_{0}$ is a
tree or more generally a union of connected components each of which are trees
(or a union of “tree connected components”), then $P$ is $g_{0}-$faithful to
$G_{0}$.

The proof of Theorem 3 requires among others a result proved by Jones & West,
(2005). This result gives a method that can be used to compute the covariance
matrix $\Sigma$ 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 $\Sigma$
using the paths in the covariance graph $G_{0}$. We now state the result by
Jones & West, (2005).

###### Theorem 4

Jones & West, (2005).

Let $\textbf{X}_{V}=(X_{v},\,v\in V)^{\prime}$ be a random vector with
Gaussian distribution $P=\mathcal{N}_{|V|}(\mu,\Sigma)$ where $\Sigma$ and
$K=\Sigma^{-1}$ are positive definite matrices. Let $G=(V,E)$ and
$G_{0}=(V,E_{0})$ denote respectively the concentration and covariance graph
associated with the probability distribution of $\textbf{X}_{V}$.

For all $(u,v)$ in $V\times V$

$k_{uv}=\displaystyle\sum_{p\in\mathcal{P}(u,v,G_{0})}(-1)^{|p|+1}|\sigma|_{p}\,\frac{|\Sigma\setminus
p|}{|\Sigma|}$

and

$\sigma_{uv}=\displaystyle\sum_{p\in\mathcal{P}(u,v,G)}(-1)^{|p|+1}|k|_{p}\frac{|K\setminus
p|}{|K|}$

where, if $p=(u_{0},\ldots,u_{n}),$

$|\sigma|_{p}=\sigma_{u_{0}u_{1}}\sigma_{u_{1}u_{2}}\ldots\sigma_{u_{n-1}u_{n}},\;\;|k|_{p}=k_{u_{0}u_{1}}k_{u_{1}u_{2}}\ldots
k_{u_{n-1}u_{n}},$

$K\setminus p=\left(k_{uv},\,(u,v)\in(V\setminus p)\times(V\setminus
p)\right)$ and $\Sigma\setminus p=\left(\sigma_{uv},\,(u,v)\in(V\setminus
p)\times(V\setminus p)\right)$ denote respectively $K$ and $\Sigma$ with rows
and columns corresponding to variables in path $p$ omitted. The determinant of
a zero-dimensional matrix is defined to be $1$.

The proof of our main theorem (Theorem 3) also requires the results proved in
the lemma below.

###### Lemma 5

Let $\textbf{X}_{V}=(X_{v},\,v\in V)^{\prime}$ be a random vector with
Gaussian distribution $P=\mathcal{N}_{|V|}(\mu,K=\Sigma^{-1})$. Let
$G_{0}=(V,E_{0})$ and $G=(V,E)$ denote respectively the covariance and
concentration graphs associated with $P$, then

  * i.

$G$ and $G_{0}$ have the same connected components

  * ii.

If a given connected component in $G_{0}$ is a tree then the corresponding
connected component in $G$ is complete and vice-versa.

Proof.

  * Proof of (i).

The fact that $G_{0}$ 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 $G_{0}$ correspond to block diagonal matrices in
$\Sigma$. Since $K=\Sigma^{-1}$, then by properties of inverting partitioned
matrices, $K$ also has the same block diagonal matrices as $\Sigma$ in terms
of the variables that constitute these matrices. These blocks corresponds to
distinct components in $G$ and $G_{0}$. Hence both matrices have the same
connected components.

  * Proof of (ii).

Let us assume now that the covariance graph $G_{0}$ is a tree, hence it is a
connected graph with only one connected component. We shall prove that the
concentration graph $G$ is complete by using Theorem 4 by Jones & West, (2005)
and computing any coefficient $k_{uv}$ ($u\not=v$). Since $G_{0}$ is a tree,
there exists exactly one path between between any two vertices $u$ and $v$. We
shall denote this path as $p=(u_{0}=u,\ldots,u_{n}=v)$. Then by Theorem 4

$k_{uv}=(-1)^{n+1}\sigma_{u_{0}u_{1}}\ldots\sigma_{u_{n-1}u_{n}}\displaystyle\frac{\left|\Sigma\setminus
p\right|}{\left|\Sigma\right|}$ (11)

First note that the determinant of the matrices in (11) are all positive since
principal minors of positive definite matrices are positive. Second since we
are considering a path in $G_{0}$, $\sigma_{u_{i-1}u_{i}}\not=0$,
$\forall\;i=1,\ldots,n$. Using these two facts we deduce from (11) that
$k_{uv}\not=0$ for all $(u,v)\in E$. Hence $u$ and $v$ are adjacent in $G$ for
all $(u,v)\in E$. The concentration graph $G$ is therefore complete. The proof
that when $G$ is assumed to be a tree implying that $G_{0}$ is complete
follows similarly.

Remark. We further note that Theorem 4 is also directly useful in deducing the
completeness of the concentration graph by using the covariance graph in other
settings. As a concrete example consider the case when $G_{0}$ is a cycle with
an even number of edges s.t. $|V|=2k$ for some odd integer $k$, and assume
that all the coefficients in the covariance matrix $\Sigma$ of
$\textbf{X}_{V}$ are positive. Hence a given pair of vertices $(u,v)$ in
$G_{0}$ are connected by two paths which are both of odd length. Let us denote
these paths as $p_{1}$ and $p_{2}$. Using Theorem 4, it is easily deduced that

$k_{uv}=\sigma_{|p_{1}|}\frac{|\Sigma\setminus
p_{1}|}{|\Sigma|}+\sigma_{|p_{2}|}\frac{|\Sigma\setminus p_{2}|}{|\Sigma|}$

Here $|\sigma_{p_{1}}|$ and $|\sigma_{p_{1}}|$ are different from zero as they
are both equal to a product of positive coefficients. Hence $k_{uv}\not=0$.
The same argument can also be used in the case when $p_{1}$ and $p_{2}$ both
have even length (i.e., $|V|=2k$ for some even integer $k$) to deduce that
$k_{uv}\not=0$. Hence $u$ and $v$ are adjacent in the concentration graph $G$;
thus $G$ is necessarily complete.

We now give an example illustrating the main result in this paper (Theorem 3).

###### Example 1

Consider a Gaussian random vector $\textbf{X}=(X_{1},\ldots,X_{8})^{\prime}$
with covariance matrix $\Sigma$ and its associated covariance graph as given
in Figure 1.

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 1: An $8-$vertex covariance tree $G_{0}$.

Consider the sets $A=\\{1,2\\}$, $B=\\{5\\}$ and $S=\\{4,6\\}$. Note that $S$
does not separate $A$ and $B$ in $G_{0}$ as any path from $A$ and $B$ does not
intersect $S$. In this case we cannot use the covariance global Markov
property to claim that $\textbf{X}_{A}$ is not independent of $\textbf{X}_{B}$
given $\textbf{X}_{V\setminus(A\cup B\cup 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 shall show however that in this example that $\textbf{X}_{A}$ is indeed not
independent of $\textbf{X}_{B}$ given $\textbf{X}_{V\setminus(A\cup B\cup
S)}$. In other words we shall show that the graph has the ability to capture
this conditional dependence present in the probability distribution $P$.

Let us now examine the relationship between $X_{2}$ and $X_{5}$ given
$\textbf{X}_{\\{3,7,8\\}}$. Note that in this example $V\setminus(A\cup B\cup
S)=\\{3,8,7\\}$, $2\in A$ and $5\in B$. Note that the covariance graph
associated with the probability distribution of the random vector
$(X_{2},X_{5},\textbf{X}_{\\{3,8,7\\}})^{\prime}$ is the subgraph represented
in Figure 2 and can be obtained directly as a subgraph of $G_{0}$ induced by
the subset $\\{2,5,3,7,8\\}$.

$2$$3$$5$$7$$8$ Figure 2: the covariance graph $(G_{0})_{\\{2,5,3,8,7\\}}$

Since $2$ and $5$ are connected by exactly one path in
$(G_{0})_{\\{2,5,3,7,8\\}}$, that is $p=(2,3,5)$, then the coefficient
$k_{25\mid 387}$, i.e., the coefficient between $2$ and $5$ in inverse of the
covariance matrix of $(X_{2},X_{5},\textbf{X}_{\\{3,8,7\\}})^{\prime}$, can be
computed using Theorem 4 as follows

$k_{25\mid
387}=(-1)^{2+1}\sigma_{23}\,\sigma_{35}\displaystyle\frac{|\Sigma(\\{8,7\\})|}{|\Sigma(\\{2,5,3,8,7\\})|}$
(12)

where $\Sigma(\\{7,8\\})$ and $\Sigma(\\{2,5,3,8,7\\})$ are respectively the
covariance matrices of the Gaussian random vectors $(X_{7},X_{8})^{\prime}$
and $(X_{2},X_{5},\textbf{X}_{\\{3,8,7\\}})^{\prime}$. Hence $k_{25\mid
387}\not=0$ since the right hand side of the equation in (12) is different
from zero. Hence
$X_{2}\,\not\\!\\!\\!\bot\bot\,X_{5}\mid\textbf{X}_{\\{3,8,7\\}}$.

Now recall that for any Gaussian random vector vector
$\textbf{X}_{V}=(X_{u},\,u\in V)^{\prime}$ ,

$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{C}\mbox{ if and only
if }\;\forall\,(u,v)\in A\times
B,\;\;X_{u}\,\bot\bot\,X_{v}\mid\textbf{X}_{C}$ (13)

where $A$, $B$ and $C$ are pairwise disjoint subsets of $V$. The
contrapositive of (13) yields

$X_{2}\,\not\\!\\!\\!\bot\bot\,X_{5}\mid\textbf{X}_{\\{3,7,8\\}}\;\Rightarrow\;\textbf{X}_{\\{1,2\\}}\,\not\\!\\!\\!\bot\bot\,X_{5}\mid\textbf{X}_{\\{3,7,8\\}}.$

Hence we conclude that since $\\{3,7,8\\}$ does not separate $\\{1,2\\}$ and
$\\{5\\}$ therefore $\textbf{X}_{\\{1,2\\}}$ is not independent of $X_{5}$
given $\textbf{X}_{\\{3,7,8\\}}$, i.e.,

$\\{1,2\\}\not\perp_{G_{0}}\\{5\\}\mid\\{3,7,8\\}\Rightarrow\textbf{X}_{\\{1,2\\}}\,\not\\!\\!\\!\bot\bot\,X_{5}\mid\textbf{X}_{\\{3,7,8\\}}$

.

We now proceed to the proof of Theorem 3. Proof. of Theorem 3. Without loss of
generality we assume that $G_{0}$ is a connected tree. Let us assume to the
contrary that $P$ is not covariance faithful to $G_{0}$, then there exists a
triplet $(A,B,S)$ of pairwise disjoint subsets of $V$, such that
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}$, but $S$ does not separate $A$ and $B$ in $G_{0}$, i.e.,

$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}\;\mbox{ and }\;A\not\perp_{G_{0}}B\mid S$

As $S$ does not separate $A$ and $B$ and since $G_{0}$ is a connected tree,
then there exists a pair of vertices $(u,v)\in A\times B$ such that the single
path $p$ connecting $u$ and $v$ in $G_{0}$ does not intersect $S$, i.e.,
$S\cap p=\emptyset$. Hence $p\subseteq V\setminus S=(A\cup
B)\cup(V\setminus(A\cup B\cup S))$. Thus two cases are possible with regards
to where the path $p$ can lie : either $p\subseteq A\cup B$ or
$p\cap(V\setminus(A\cup B\cup S))\not=\emptyset$. Let us examine both cases
separately.

  * •

Case 1 : $p\subseteq A\cup B$

In this case the entire path between $u$ and $v$ lies in $A\cup B$ and hence
we can find a pair of vertices222As an illustration of this point consider the
graph presented in Figure 1. 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\cup B$
and hence we can find two vertices, namely, $2\in A$ and $3\in B$, belonging
to path $p$ that are adjacent in $G_{0}$. $(u^{\prime},v^{\prime})$ belonging
to $p$ and $(u^{\prime},v^{\prime})\in A\times B$ such that
$u^{\prime}\sim_{G_{0}}v^{\prime}$.

Recall that since $G_{0}$ is a tree, any induced graph of $G_{0}$ by a subset
of $V$ is a union of tree connected components (see Lemma 1). Hence the
subgraph $(G_{0})_{W}$ of $G_{0}$ induced by
$W=\\{u^{\prime},v^{\prime}\\}\cup V\setminus(A\cup B\cup S)$ is a union of
tree connected components. As $u^{\prime}$ and $v^{\prime}$ are adjacent in
$G_{0}$, they are also adjacent in $(G_{0})_{W}$ and belong to the same
connected component333In our example in Figure 1 with $W=\\{2,3,8,7\\}$,
$(G_{0})_{W}$ consists a union of two connected components with its respective
vertices being $\\{2,3\\}$ and $\\{8,7\\}$. of $(G_{0})_{W}$. Hence the only
path between $u^{\prime}$ and $v^{\prime}$ is precisely the edge
$(u^{\prime},v^{\prime})$. Using theorem 4 to compute the coefficient
$k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup S)}$, i.e.,
$(u^{\prime},v^{\prime})th$ coefficient in the inverse of the covariance
matrix of the random vector $\textbf{X}_{W}=(X_{w},\,w\in
W)^{\prime}=(X_{u^{\prime}},X_{v^{\prime}},\textbf{X}_{V\setminus(A\cup B\cup
S)})^{\prime}$, we obtain,

$k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup
S)}=(-1)^{1+1}\sigma_{u^{\prime}v^{\prime}}\,\displaystyle\frac{\left|\Sigma(W\setminus\\{u^{\prime},v^{\prime}\\})\right|}{|\Sigma(W)|},$
(14)

where $\Sigma(W)$ denotes the covariance matrix of $\textbf{X}_{W}$, and
$\Sigma(W\setminus\\{u^{\prime},v^{\prime}\\})$ denotes the matrix $\Sigma(W)$
with the rows and the columns corresponding to variables $X_{u^{\prime}}$ and
$X_{v^{\prime}}$ omitted. We can therefore deduce from (14) that
$k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup S)}\not=0$. Recall that at
the start of the proof we assumed to the contrary that
$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}$. Now since $P$ is Gaussian, for pairwise disjoint subsets
$A,B,V\setminus(A\cup B\cup C)$ then

$\textbf{X}_{A}\,\bot\bot\,\textbf{X}_{B}\mid\textbf{X}_{V\setminus(A\cup
B\cup C)}\Leftrightarrow\forall\,(u,v)\in A\times
B,\;X_{u}\,\bot\bot\,X_{v}\mid\textbf{X}_{V\setminus(A\cup B\cup C)}$ (15)

Note however that we have established that
$X_{u^{\prime}}\,\not\\!\\!\\!\bot\bot\,X_{v^{\prime}}\mid\textbf{X}_{V\setminus(A\cup
B\cup S)}$ since $k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup S)}\neq
0$. Hence we obtain a contradiction to (15) since $u^{\prime}\in A$ and
$v^{\prime}\in B$.

  * •

Case 2 : $p\cap(V\setminus(A\cup B\cup S))\not=\emptyset$ & $V\setminus(A\cup
B\cup S)$ is not empty.

Now if $V\setminus(A\cup B\cup S)$ is empty then $p$ has to lie entirely in
$A\cup B$. This is because by assumption $p$ does not intersect $S$. The case
when $p$ lies in $A\cup B$ is covered in Case 1 and hence it is assumed that
$V\setminus(A\cup B\cup S)\not=\emptyset.$ 444As an illustration of this point
consider once more the graph presented in Figure 1. Consider $A=\\{1,2\\}$,
$B=\\{7,8\\}$ and $S=\\{4,6\\}$. Here $V\setminus(A\cup B\cup S)=\\{3,5\\}$
and the path $p=(1,2,3,5,7,8)$ connecting $A$ and $B$ intersects
$V\setminus(A\cup B\cup S)$.

In this case there exists a pair of vertices $(u^{\prime},v^{\prime})\in
A\times B$ with $u^{\prime},v^{\prime}\in p$, such that the vertices
$u^{\prime}$ and $v^{\prime}$ are connected by exactly one path
$p^{\prime}\subseteq p$ in the induced graph $(G_{0})_{W}$ of $G_{0}$ by
$W=\\{u^{\prime},v^{\prime}\\}\cup V\setminus(A\cup B\cup S)$ (see Lemma 1)
555In our example in figure 1 with $A=\\{1,2\\}$, $B=\\{7,8\\}$ and
$S=\\{4,6\\}$ , the vertices $u^{\prime}$ and $v^{\prime}$ will correspond to
vertices $2$ and $7$ respectively, and $p^{\prime}=(2,3,5,7)$, which is a path
entirely contained in $V\setminus(A\cup B\cup
S)\cup\\{u^{\prime},v^{\prime}\\}$..

Let us now use Theorem 4 to compute the coefficient
$k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup S)}$, i.e., the
$(u^{\prime},v^{\prime})-$coefficient in the inverse of the covariance matrix
of the random vector $\textbf{X}_{W}=(X_{w},\,w\in
W)^{\prime}=(X_{u^{\prime}},X_{v^{\prime}},\textbf{X}_{V\setminus(A\cup B\cup
S)})^{\prime}$. We obtain that

$k_{u^{\prime}v^{\prime}\mid V\setminus(A\cup B\cup
S)}=(-1)^{|p^{\prime}|+1}|\sigma_{p^{\prime}}|\,\displaystyle\frac{\left|\Sigma(W\setminus
p^{\prime})\right|}{|\Sigma(W)|},$ (16)

where $\Sigma(W)$ denotes the covariance matrix of $\textbf{X}_{W}$ and
$\Sigma(W\setminus p^{\prime})$ denotes $\Sigma(W)$ with the rows and the
columns corresponding to variables in path $p^{\prime}$ omitted. One can
therefore easily deduce from (16) that $k_{u^{\prime}v^{\prime}\mid
V\setminus(A\cup B\cup S)}\not=0$. Thus $X_{u^{\prime}}$ is not independent of
$X_{v^{\prime}}$ given $\textbf{X}_{V\setminus(A\cup B\cup S)}$. Hence once
more we obtain a contradiction to (15) since $u^{\prime}\in A$ and
$v^{\prime}\in B$.

Remark. The dual result of the theorem above for the case of concentration
trees was proved by Becker et al., (2005). We note however that the argument
used in the proof of Theorem 3 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 sub-graph
$(G_{0})_{\\{u,v\\}\cup S}$ of $G_{0}$ induced by a subset ${\\{u,v\\}\cup
S}\subseteq V$ is also the covariance graph associated with the Gaussian sub-
random vector of $\textbf{X}_{V}$ as denoted by $\textbf{X}_{\\{u,v\\}\cup
S}=(X_{w},\,w\in\\{u,v\\}\cup S)^{\prime}$. Hence it was possible to compute
the coefficient $k_{uv\mid S}$ which quantifies the conditional (in)dependence
between $u$ and $v$ given $S$, in terms of the paths in
$(G_{0})_{\\{u,v\\}\cup S}$ and the coefficients of the covariance matrix of
$\textbf{X}_{\\{u,v\\}\cup S}=(X_{w},\,u\in\\{u,v\\}\cup S)^{\prime}$. On the
contrary, in the case of concentration graphs the sub-graph $G_{\\{u,v\\}\cup
S}$ of the concentration graph $G$ induced by $\\{u,v\\}\cup S$ is not in
general the concentration graph of the random vector
$\textbf{X}_{\\{u,v\\}\cup S}=(X_{w},\,u\in\\{u,v\\}\cup S)^{\prime}$. Hence
our approach is not directly applicable in the concentration graph setting.

##  5 Conclusion

Faithfulness of a probability distribution to a graph is a crucial assumption
that is often made in the probabilistic treatment of graphical models. This
assumption describes the ability of a graph to reflect or encode the
multivariate dependencies that are present in a joint probability
distribution. Much of the methodology in this area often do not undertake a
detailed analysis of the faithfulness assumption, as such an endeavor requires
a more careful and rigorous probabilistic study of the joint distribution at
hand. 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 that is employed in this paper is
novel in the sense that it is self contained and yields a completely new
approach to demonstrating faithfulness - as compared to the methods that are
traditionally used in the literature. Moreover, it is also vastly different in
nature from the proof of the analogous result for concentration graph models.
Hence the approach used in this paper promises to have further implications
and give other insights. Future research in this area will explore if the
techniques used in this paper can be modified to prove or disprove
faithfulness for other classes of graphs.

## Acknowledgments

The authors gratefully acknowledge the faculty at Stanford University for
their feedback and tremendous enthusiasm for this work.

## References

  * Banerjee & Richardson, (2003) Banerjee, M., & Richardson, T. 2003.  On a Dualization of Graphical Gaussian Models: A Correction Note.  Scand. J. Statist., Vol 30, 817–820.
  * Becker et al., (2005) Becker, Ann, Geiger, Dan, & Meek, Christopher. 2005.  Perfect Tree-like Markovian Distributions.  Probability and Mathematical Statistics, 25(2), 231–239.
  * Cox & Wermuth, (1996) Cox, D. R., & Wermuth, N. 1996.  Multivariate Depencies : Models, Analysis and Interpretations.  Chapman and Hall.
  * Cox & Wermuth, (1993) Cox, D.R., & Wermuth, M. 1993.  Linear dependencies represented by chain graphs (with Discussion).  Statist. Sci., 8, 204–218, 247–277.
  * Hammersly & Clifford, (1971) Hammersly, J. M., & Clifford, P. E. 1971.  Markov fields on finite graphs and lattices.  Unpublished manuscript.
  * Ji & Seymour, (1996) Ji, C., & Seymour, L. 1996.  A consistent model selection procedure for Markov random fields based on penalized pseudolikelihood.  The Annals of Applied Probability, 6(2), 423–443.
  * Jones & West, (2005) Jones, B., & West, M. 2005.  Covariance decomposition in undirected Gaussian graphical models.  Biometrika, 92, 770–786.
  * Kauermann, (1996) Kauermann, G. 1996.  On a dualization of graphical Gaussian models.  Scand. J. Statist., 23, 105–116.
  * Khare & Rajaratnam, (2009) Khare, K., & Rajaratnam, B. 2009.  Wishart distributions for decomposable covariance graph models.  under review in the Annals of Statistics.
  * Kindermann & Snell, (1980) Kindermann, R., & Snell, J. L. 1980.  Markov Random Fields and Their Applications.  American Mathematical Society, Providence, Rhode Island.
  * Kunsch et al., (1995) Kunsch, H., Gemanand, S., & Kehagias, A. 1995.  Hidden Markov Random Fields.  The Annals of Applied Probability, 5(3), 577–602.
  * Lauritzen, (1996) Lauritzen, S. L. 1996.  Graphical Models.  New York : Oxford University Press.
  * Malouche & Rajaratnam, (2009) Malouche, D., & Rajaratnam, B. 2009.  Analysis of the faithfulness assumption in Graphical Models.  Technical Report, Department of Statistics, Stanford University.
  * Pearl, (1988) Pearl, J. 1988.  Probabilistic Reasoning in Intelligent Systems.  Tech. rept. Morgan Kaufman.
  * Spitzer, (1975) Spitzer, C. 1975.  Markov random fields on an infinite tree.  The Annals of Probability, 3, 387–398.