GM Notes
GM Notes
S TEFFEN L. L AURITZEN
D EPARTMENT OF M ATHEMATICAL S CIENCES
U NIVERSITY OF C OPENHAGEN
U NIVERSITETSPARKEN 5
2100 C OPENHAGEN , D ENMARK
ISBN 978-87-70787-53-6
PREFACE
These lecture notes have as their purpose to give a rigorous introduction to the notion
of conditional distributions and expectations, as well as properties of conditional
independence as this concept underpins the Markov theory of graphical models. A
major part of these lecture notes are based on Conditioning and Markov properties by
Anders Rønn–Nielsen and Ernst Hansen (Third edition, 2016), in particular the
treatment of conditional distributions using Markov kernels in Chapter 1, but also the
measure-theoretic version of conditional independence and a large number of
exercises. These were again heavily using previous lecture notes of Martin Jacobsen,
Søren Tolver Jensen, and Søren Feodor Nielsen. I am indebted to this tradition of
openness in the Statistics group at the Department of Mathematical Sciences and in
particular to Anders and Ernst for permission to use their material of which parts have
been copied and pasted directly into this document. Clearly, I take full responsibility
for any error that may have crept into the notes in one way or another during this
process. For basic results in measure theory, the reader is referred to Hansen (2009).
Much of the remaining material builds heavily on Lauritzen (1996).
Copenhagen S.L.L.
27 September 2017.
Copenhagen S.L.L.
5 September 2018
Copenhagen S.L.L.
14 October 2019
CONTENTS
1 Conditional Distributions 1
1.1 Markov kernels 1
1.2 Integration of Markov kernels 3
1.3 Properties of the integration measure 6
1.4 Conditional distributions 9
1.5 Transformations of conditional distributions 16
1.6 Conditional moments 22
1.7 Exercises 29
2 Conditional independence 39
2.1 Conditional probabilities given a σ–algebra 39
2.2 Conditionally independent events 40
2.3 Conditionally independent σ-algebras 42
2.4 Combination of Markov kernels 46
2.5 Conditional independence revisited 48
2.5.1 Independence models 51
2.5.2 Graphical independence models 54
2.5.3 General graph separation 54
2.5.4 Directed acyclic graphs 56
2.6 Markov properties 58
2.6.1 Markov properties on undirected graphs 59
2.6.2 Markov properties on directed acyclic graphs 64
2.6.3 Markov equivalence 69
2.7 Exercises 73
3 Local computation 79
3.1 Local computation 79
3.2 Probability propagation 79
3.2.1 Basic problem 79
3.2.2 Setting up the structure 80
3.2.3 The basic invariant 80
3.2.4 Message passing 81
3.2.5 Message scheduling 83
3.2.6 Alternative scheduling of messages 84
3.2.7 Alternative computations 84
3.2.8 An example 84
3.3 Exercises 94
4 Multivariate normal models 95
4.1 Basic facts and concepts 95
4.1.1 Notation 95
4.1.2 The saturated model 96
4.1.3 Conditional independence 97
4.1.4 Interaction 99
4.2 Covariance selection models 99
4.2.1 Maximum likelihood estimation 100
4.3 Decomposable models 103
4.3.1 Basic factorizations 103
4.3.2 Maximum likelihood estimation 104
4.4 The graphical lasso 104
4.4.1 A constrained optimization problem 105
4.4.2 Blocking the subgradient equation 105
4.5 Exercises 108
A Some mathematical prerequisites 111
A.1 Measurable spaces 111
A.2 Möbius inversion 113
A.3 Convexity and optimization 114
A.3.1 Convex sets and functions 114
A.3.2 Convex optimization problems 115
A.3.3 Duality and optimality 116
A.4 Iterative partial maximization 118
B Some graph theory 121
B.1 Notation and terminology 121
B.2 Undirected graphs 124
B.2.1 Separation and connectivity 124
B.2.2 Decomposition 124
B.2.3 Simplicial subsets and perfect sequences 126
B.3 Hypergraphs 130
B.3.1 Basic concepts 130
B.3.2 Graphs and hypergraphs 131
B.3.3 Junction trees and forests 132
B.4 Algorithms 136
B.4.1 Identifying chordal graphs 136
B.4.2 Finding cliques and constructing a junction tree 137
B.4.3 Junction trees of prime components 139
C Linear algebra and random vectors 141
C.1 Matrix results 141
C.2 Random vectors 142
D The multivariate normal distribution 147
D.1 Basic properties 147
References 149
Index 153
1
CONDITIONAL DISTRIBUTIONS
Let (X , E) and (Y, K) be two measurable spaces. In this chapter we shall discuss the
relation between measures on the product space (X × Y, E ⊗ K) and measures on the
two marginal spaces (X , E) and (Y, K). Following the notation in Hansen (2009) we
say that the map f : (X , E) → (Y, K) is E − K–measurable, if
f −1 (K) ∈ E
for all K ∈ K. For ease of notation, we will say that f is E-measurable instead of
E − B–measurable, when f has values in (R, B), where B is the Borel σ–algebra.
Similarly, if X defined on (Ω, F, P ) is a random variable with values in (X , E), and D
is a sub σ–algebra of F, we will say that X is D − E–measurable, if
X −1 (E) = (X ∈ E) ∈ D
x 7→ Px (B)
Then !x !
∞ ∞
!
[ [
Px Gn = Px Gxn = lim Px (Gxn )
n→∞
n=1 n=1
x
S∞ is E–measurable, since each of the functions x 7→ Px (Gn ) are measurable.
This limit
Then n=1 Gn ∈ H. 2
In the second equality we have used that each Px is a measure, and in the third equality
we have used monotone convergence to interchange integration and summation. From
this we have that λ is a measure. And since
4 Conditional Distributions
Z Z Z
λ(X × Y) = Px ((X × Y)x ) dµ(x) = Px (Y) dµ(x) = 1 dµ(x) = 1
Proof The second statement is obvious. For the first result just note that Px (Y) = 1
for all x ∈ X . 2
The probability measure on (Y, K) defined by λ(X × B) is called the mixture of the
Markov kernel with respect to µ.
Example 1.7 Let µ be a probability measure on (X , E) and let ν be a probability
measure on (Y, K). Define Px = ν for all x ∈ X . Then, trivially, (Px )x∈X is an
X –Markov kernel on Y. Let λ be the integration of this kernel with respect to µ. Then
for all A ∈ E and B ∈ K
Z
λ(A × B) = ν(B) dµ(x) = µ(A) · ν(B) .
A
E0 = {x ∈ X : Px = P̃x }
Proof Let (Bn )n∈N be a countable generating system for (Y, K). Then
∞
\
E0 = {x ∈ X : Px (Bn ) = P̃x (Bn )}
n=1
such that µ = µ̃. The proof will be complete, if we can show that
and since the integrand is strictly positive on En+ , we can conclude that µ(En+ ) = 0. It
is shown similarly that µ(En− ) = 0, where
is E–measurable.
Proof Firstly note that for fixed x then f (x, y) = f ◦ ix (y) which is a K–measurable
function. Hence the integral in (1.1) is well–defined. Now assume that f is a simple
function
Xn
f= ck 1Gk (1.2)
k=1
Hence the right hand side is the point–wise limit of E–measurable functions. Thereby
it is E–measurable. 2
Properties of the integration measure 7
Proof The inner integral on the right hand side is E–measurable with values in [0, ∞]
according to Lemma 1.10. Hence both the left-hand side and the right-hand side are
well-defined.
Now assume that f is a simple function on the form (1.2). Then
Z Xn
f dλ = ck λ(Gk )
k=1
Xn Z
= ck Px (Gxk ) dµ(x)
k=1
Xn ZZ
= ck 1Gxk (y) dPx (y) dµ(x)
k=1
Xn ZZ
= ck 1Gk (x, y) dPx (y) dµ(x)
k=1
n
ZZ X
= ck 1Gk (x, y) dPx (y) dµ(x)
k=1
ZZ
= f (x, y) dPx (y) dµ(x)
From this we see that the function g defined in the theorem is measurable according to
Lemma 1.10. Furthermore we obtain from the extended Tonelli’s Theorem that
Z Z Z
|g(x)|dµ(x) = f (x, y) dPx (y) dµ(x)
ZAZ0
≤ 1A0 ×Y (x, y)|f (x, y)| dPx (y) dµ(x)
< ∞,
showing that g is µ–integrable. Finally, we have from the extended Tonelli that
Z Z
f (x, y) dPx (y) dµ(x)
A0
Z Z Z Z
= f (x, y)+ dPx (y) dµ(x) − f (x, y)− dPx (y) dµ(x)
ZA0 Z A0
= 1A0 (x)f (x, y) dλ(x, y) − 1A0 (x)f − (x, y) dλ(x, y)
+
Z Z
= 1A0 (x)f (x, y) dλ(x, y) = f (x, y) dλ(x, y) .
A0 ×Y
Conditional distributions 9
where P0 is some probability measure on (Y, K). Note that x 7→ P̃x (B) is measurable,
since A0 is a measurable set.
The interpretation of the conditional distribution of Y given X is that Px describes the
distribution of Y if we know that X = x. This interpretation is very useful although it
should not be taken too seriously, since it may be difficult to give a strict mathematical
description when the event X = x is a nullset. This interpretation leads to the
10 Conditional Distributions
following alternative notation for a Markov kernel (Px )x∈X that is a conditional
distribution of Y given X:
P (Y ∈ B | X = x) = Px (B) for B ∈ K .
A more relaxed but useful notation will be simply talking about ’the distribution of
Y | X = x’ instead of the longer ’the distribution Px , when (Px )x∈X is the
conditional distribution of Y given X’. We will also from time to time write
expressions like Y | X = x ∼ ν.
For completely arbitrary random variables, a conditional distribution may not always
be well-defined. However, if the image space of Y is a Borel space (i.e. isomorphic to
a Borel subset of the unit interval), this is the case:
Theorem 1.14 Let X and Y be random variables defined on the probability space
(Ω, F, P ) with values in (X , E) and (Y, K) respectively, such that Y is a Borel space.
Then there exists a conditional distribution of Y given X.
This result is particularly important, since spaces of the form R, Rn , and R∞ are all
Borel spaces. We refrain from proving Theorem 1.14 as well as these facts and refer
the reader to other textbooks on probability.
Although the conditional distributions exist, it is in general difficult and not clear how
the corresponding Markov kernels should be constructed. However, direct construction
of the Markov kernels is possible in specific situations.
Theorem 1.15 Assume that X and Y are random variables on (X , E) and (Y, K)
such that (Px )x∈X is the conditional distribution of Y given X. Then X and Y are
independent if and only if Px does not depend on x, i.e. the Markov kernel can be
chosen so that
Px = P0
for all x ∈ X . In the case of independence, then Px = P0 = Y (P ) for all x ∈ X .
which shows that the constant Markov kernel (Y (P ))x∈X is the conditional
distribution of Y given X.
Conversely, assume that Px = P0 for all x ∈ X , where P0 is some probability measure
on (Y, K). Then for B ∈ K we have
Z
P (Y ∈ B) = P (X ∈ X , Y ∈ B) = Px (B) dX(P )(x)
Z
= P0 (B) dX(P )(x) = P0 (B)
Z Z
P (X ∈ A, Y ∈ B) = Px (B) dX(P )(x) = P0 (B) dX(P )(x)
A A
= X(P )(A)P0 (B) = P (X ∈ A)P (Y ∈ B)
P (X = x, Y ∈ B)
Px (B) = = P (Y ∈ B | X = x)
P (X = x)
Proof Let A0 = {x ∈ X : P (X = x) > 0} and note that X(P )(A0 ) = 1 such that
(1.3) defines an (X , E)–Markov kernel on (Y, K) – the measurability is not a problem,
since all functions on X are E–measurable. For A ⊆ X and B ∈ K we have
Z Z
Px (B) dX(P )(x) = Px (B) dX(P )(x)
A A∩A0
X P (X = x, Y ∈ B)
= P (X = x)
P (X = x)
x∈A∩A0
X
= P (X = x, Y ∈ B)
x∈A∩A0
= P (X ∈ A ∩ A0 , Y ∈ B)
= P (X ∈ A, Y ∈ B)
where the last equality is follows from Tonelli’s theorem. We see that (X, Y )(P ) and
h · µ ⊗ ν coincide on all product sets, and therefore must be equal. 2
The theorem states that the joint density is the product of the marginal density and the
conditional densities. The next theorem gives the converse result: The densities for the
conditional distribution is the ratio of the joint density and the marginal density.
Conditional distributions 13
Theorem 1.19 Assume that X and Y are random variables defined on (Ω, F, P ) with
values in (X , E) and (Y, K). Furthermore let µ and ν be σ–finite measures on (X , E)
and (Y, K) and assume that (X, Y )(P ) = h · µ ⊗ ν. Then the conditional distribution
of Y given X exists. The marginal distribution of X has density with respect to µ given
by Z
f (x) = h(x, y) dν(y)
Let A0 = {x ∈ X : 0 < f (x) < ∞}. Then X(P )(A0 ) = 1 and the conditional
distribution (Px )x∈X of Y given X has density with respect to ν given by
h(x, y)
gx (y) =
f (x)
for all x ∈ A0 .
Proof Finding the marginal density for X(P ) is a well–known calculation. For
A ∈ E we have
so µ(A2 ) = 0. Clearly we have that X(P )(A1 ) = 0, such that X(P )(A0 ) = 1.
R
From Tonelli we have that x 7→ h(x, y)dν(y) = f (x) is E–measurable. Then also
h(x, y)
(x, y) 7→ 1A0 (x) = 1A0 (x)gx (y)
f (x)
is E ⊗ K − B–measurable, and we have from Theorem 1.2 that (Px )x∈A0 is a Markov
kernel, when Px = gx · ν. Finally we have for A ∈ E and B ∈ K that
14 Conditional Distributions
Z Z Z
Px (B) dX(P )(x) = gx (y) dν(y) f (x) dµ(x)
A A∩A0 B
Z Z
h(x, y)
= dν(y) f (x) dµ(x)
A∩A B f (x)
Z Z0
= h(x, y) dν(y) dµ(x)
ZA B
which shows, that (Px )x∈A0 is the conditional distribution for Y given X. 2
Example 1.20 Suppose V = Rd and assume the random vector X partitioned into
components X1 and X2 , where X1 ∈ Rr and X2 ∈ Rs with r + s = d. Its mean vector
and covariance matrix can then be partitioned accordingly into blocks as
ξ1 Σ11 Σ12
ξ= and Σ =
ξ2 Σ21 Σ22
such that Σ11 has dimensions r × r and so on. Let X be distributed as Nd (ξ, Σ), where
X, ξ and Σ are partitioned as above and Σ is regular. Then the conditional distribution
of X1 given X2 = x2 is Nr (ξ1|2 , Σ1|2 ), where
ξ1|2 = ξ1 + Σ12 (Σ22 )−1 (x2 − ξ2 ) and Σ1|2 = Σ11 − Σ12 (Σ22 )−1 Σ21 . (1.4)
This is seen as follows: Since Σ is positive definite we can let K = Σ−1 denote the
concentration matrix and assume this to be partitioned in the same fashion as Σ. By
Theorem 1.19, the conditional density is proportional to the joint density of X1 and
X2 . Hence, exploiting that x2 is fixed, we find by direct calculation that
and the result follows. Note that the proportionality constant may in principle depend
on the parameters as well as on x2 . But as the distribution is normal, this turns out not
to be the case. It follows from (C.1) that we have
det Σ22
det Σ = det Σ1|2 det Σ22 = . (1.7)
det K11
Note also the identities (1.5) and (1.6), which are quite useful in their own right. The
first expresses that the concentration matrix of the conditional distribution is obtained
from the concentration matrix of the joint distribution by deleting rows and columns
corresponding to the variables conditioned upon. We thus obtain an alternative formula
for the parameters of the conditional distribution
ξ1|2 = ξ1 − (K11 )−1 K12 (x2 − ξ2 ) and K1|2 = K11 (1.8)
which may be simpler to use in certain contexts. 2
We can reformulate Theorem 1.19 to obtain what is known as Bayes’ formula.
Corollary 1.21. (Bayes’ formula) If π = X(P ) and Px has density gx w.r.t. ν, then
the conditional distribution of X given Y exists and is determined by the Markov
kernel (πy∗ )y∈Y with density Ly w.r.t. π where
Ly (x) = gx (y)/c(y)
where Z
c(y) = gx (y) dπ(x).
Hence, h(x, y) = gx (y) is the joint density of (X, Y ) w.r.t. π ⊗ ν. Using now
Theorem 1.19 with x and y interchanged we get that the conditional distribution of X
given Y = y exists and has density
Ly (x) = gx (y)/c(y)
w.r.t. π. 2
Bayes’ theorem is of course particularly important for Bayesian inference. We use the
term Fisherian model for a parametrized family P = {Pθ , θ ∈ Θ} of probability
measures on a measurable space (Y, F). If the parameter space Θ is equipped with a
σ-algebra T and the map θ 7→ Pθ (A) is measurable for all A ∈ F, this family can be
seen as a Markov kernel. We then define a corresponding Bayesian model as follows:
16 Conditional Distributions
In other words, the corollary says that the likelihood function Ly (θ) ∝ gθ (y) is the
density of the posterior distribution πy∗ w.r.t. the prior distribution π:
Theorem 1.24. (Substitution Theorem) Assume that (Px )x∈X is the conditional
distribution of Y given X. Let (Z, H) be a measurable space, and let φ : X × Y → Z
be a measurable map. Define Z = φ(X, Y ). Then the conditional distribution of Z
given X exists and is determined by (P̃x )x∈X , where
P̃x = (φ ◦ ix )(Px )
Note that this is not at all surprising: If we know that X = x, then we have
Z = φ(x, Y ) = (φ ◦ ix )(Y ), and apparently we are allowed to plug the conditional
distribution into this formula.
Transformations of conditional distributions 17
It is seen that if x ∈
/ A then
and if x ∈ A we have
Hence
Z Z
P (X ∈ A, Z ∈ C) = Px ((φ ◦ ix )−1 (C)) dX(P )(x) = P̃x (C) dX(P )(x) ,
A A
Ir −Σ12 Σ−
Z 22 X1
= .
X2 0 Is X2
To find the joint distribution of Z and X2 we use Proposition D.3 and calculate
Ir −Σ12 Σ−
22 Σ11 Σ12 Ir 0
0 Is Σ21 Σ22 −Σ− 22 Σ21 Is
− −
I −Σ12 Σ22 Σ11 − Σ12 Σ22 Σ21 Σ12
= r
0 Is 0 Σ22
−
Σ11 − Σ12 Σ22 Σ21 0
= .
0 Σ22
Σ21 − Σ22 Σ− −
22 Σ21 = (Ir − Σ22 Σ22 )Σ21 = 0
since also
(Ir − Σ22 Σ− −
22 )Σ22 = Σ22 − Σ22 Σ22 Σ22 = 0.
Z ∼ Nr (ξ1 − Σ12 Σ− −
22 ξ2 , Σ11 − Σ12 Σ22 Σ21 ) .
on the set {(x, y) ∈ R2 : 0 < x, 0 < y, x + y < 1}. It can be shown that the marginal
distribution of X is a B–distribution with parameters (λ1 , λ2 + λ). Hence it has density
Transformations of conditional distributions 19
Γ(λ + λ1 + λ2 ) λ1 −1
g(x) = x (1 − x)λ2 +λ−1
Γ(λ1 )Γ(λ2 + λ)
for x ∈ (0, 1). The conditional distribution Px of Y given X = x for x ∈ (0, 1) must
be concentrated on the interval (0, 1 − x) and have density
λ2 −1 λ−1
f (x, y) Γ(λ2 + λ) y y 1
fx (y) = = 1− .
g(x) Γ(λ)Γ(λ2 ) 1 − x 1−x 1−x
If Px is transformed by the map y → y/(1 − x) then a B–distribution with parameters
(λ2 , λ) is obtained. According to Theorem 1.24 the constant family consisting of
B–distributions with parameters (λ2 , λ) indexed by x ∈ (0, 1) must be the conditional
distribution of Y /(1 − X) given X. It follows from Theorem 1.15 that Y /(1 − X) and
X are independent and that Y /(1 − X) is B–distributed with parameters (λ2 , λ). 2
The following rather deep results is a type of converse to Corollary 1.25 and shows that
the functional construction in some sense is a universal representation of a Markov
kernel.
Theorem 1.28 Let X and Y be random variables with values in (X , E) and (Y, K).
There exists a map φ : X × (0, 1) → Y, which is E ⊗ B(0,1) − K measurable, with the
following property: if X 0 is a random variable with the same distribution as X, U is a
real valued random variable, independent of X 0 and uniformly distributed on (0, 1),
and if we let
Y 0 = φ(X 0 , U )
then (X 0 , Y 0 ) has the same distribution as (X, Y ).
Proof Due to the underlying assumption that the spaces involved are Borel spaces, we
may assume that (Y, K) = (R, B). Let (Px )x∈X be the conditional distribution of Y
given X. We know that the conditional distribution of U given X 0 is degenerate:
Qx = ν for all x ∈ X ,
where ν is the uniform distribution on (0, 1). By the substitution theorem, the
conditional distribution of Y 0 given X 0 is
Rx = φ ◦ ix (Qx ) = φ ◦ ix (ν) .
The proof is complete, once we show how to choose φ such that Rx = Px for every x,
as the joint distribution is uniquely determined from one marginal distribution and the
conditional distribution of the remaining marginal given the first.
The deep claim is not so much that it is possible to choose φ is such a way that
φ ◦ ix (ν) = Px for all x ∈ X . (1.9)
For if we let Fx be the distribution function corresponding to Px , and if we let qx be a
quantile function for Fx , it is well known that qx (ν) = Px . So we may let
φ(x, u) = qx (u) ,
and (1.9) will be satisfied bona fide.
20 Conditional Distributions
What is a deep claim is that the construction can be carried out in a way that guarantees
φ to be measurable. There is a choice involved, in the sense that quantile functions are
not unique, and even though the individual quantile functions are increasing, and thus
necessarily measurable, the various choices may destroy joint measurability.
The key is to get rid of the choices, and find an operationally defined quantile function.
A nice one is
qx (p) = inf{y ∈ R | Fx (y) > p} for all x ∈ X , p ∈ (0, 1) .
The idea is to single out the largest possible p-quantile whenever there is a choice. Let
us prove that this is in fact a quantile function: For fixed x and p, we have that
(
(y0 , ∞)
{y ∈ R | Fx (y) > p} = ,
[y0 , ∞)
for some y0 ∈ R. Whether we have the open or the halfclosed interval, depends on the
specifics of the situation, but in both cases we see that qx (p) = y0 . For each n we have
that y0 + n1 > y0 , and thus
1
Fx y0 + > p.
n
Using right continuity of Fx , we can conclude that
Fx (y0 ) ≥ p .
1
Similarly, y0 − n < y0 , and so
1
Fx y0 − ≤ p.
n
Using monotonicity of Fx , we can conclude that
Fx (y0 −) ≤ p .
Together these inequalities show that y0 is a p-quantile for Fx . As for measurability, an
elementary argument shows that
[
{(x, p) | qx (p) < z} = {(x, p) | Fx (w) > p} . (1.10)
w<z,w∈Q
The point of Theorem 1.28 is that we may think of as any pair of variables as generated
in a two-step procedure, where the generation of the second variable can be
accomplished by mixing the first variable with random noise. It is the way that the
mixing is carried out, that determines the joint distribution.
The update function φ is not at all unique. There are literally uncountably many ways
to choose it. In certain cases it matters which one we use, in most cases it is irrelevant.
However, in typical applications there is a specific update function that almost forces
itself upon us.
We conclude the section by identifying some cases where the structure of conditional
distribution simplifies.
Theorem 1.29 Assume that (Px )x∈X is the conditional distribution of Y given X. Let
(Z, H) be a measurable space and let t : X → Z be an E − H–measurable map.
Define Z = t(X). Then the conditional distribution (Qx,z )(x,z)∈X ×Z of Y given
(X, Z) is given by
Qx,z = Px for all x ∈ X , z ∈ Z (1.11)
Note: This is a situation where it is quite clear that conditional distributions are not
uniquely determined. The variable (X, Z) does not have values in the entire product
space X × Z but only on the graph of t, meaning the set of points
{(x, z) ∈ X × Z : z = t(x)}
Then Qx,z could be defined as any probability measure outside the graph, if only some
measurability conditions are fulfilled. Hence the Markov kernel defined in (1.11) is not
the only possible conditional distribution of Y given (X, Z) – it is simply a convenient
choice.
Proof It is easily argued that a (X × Z, E ⊗ H)–Markov kernel (Qx,z )(x,z)∈X ×Z on
(Y, K) is defined by (1.11). For A ∈ E, B ∈ K and C ∈ H we have
Z Z
Qx,z (B) d(X, Z)(P )(x, z) = 1A×C (x, z)Qx,z (B) d((id, t) ◦ X)(P )(x, z)
A×C
Z
= 1A×C ◦ (id, t)(x) Q(id,t)(x) (B) dX(P )(x)
Z
= 1A∩t−1 (C) (x)Px (B) dX(P )(x) .
Since (Px )x∈X is the conditional distribution of Y given X, the last integral can be
identified as
P (X ∈ A ∩ t−1 (C), Y ∈ B) = P (X ∈ A, Z ∈ C, Y ∈ B)
= P ((X, Z) ∈ A × C, Y ∈ B) .
Z
Qx,z (B) d(X, Z)(P )(x, z) = P ((X, Z) ∈ G, Y ∈ B)
G
for all G ∈ E ⊗ H and all B ∈ K. Hence it is concluded that (Qx,z )(x,z)∈X ×Z is the
conditional distribution of Y given (X, Z). 2
Theorem 1.30 Let (Px )x∈X be the conditional distribution of Y given X. Let (Z, H)
be a measurable space and let t : X → Z be an E − H–measurable map. Define
Z = t(X). If an (Z, H)–Markov kernel (Qz )z∈Z on (Y, K) exists such that
P (Z ∈ C, Y ∈ B) = P (X ∈ t−1 (C), Y ∈ B)
Z
= 1t−1 (C) (x)Px (B) dX(P )(x)
Z
= 1C ◦ t(x)Qt(x) (B) dX(P )(x)
Z
= 1C (z)Qz (B) d(t ◦ X)(P )(z)
Z
= Qz (B) dZ(P )(z) .
C
E(X|D) = EX a.s.
(g) If it holds for all n ∈ N that Xn ≥ 0 a.s. and Xn+1 ≥ Xn a.s. with lim Xn = X
a.s., then
lim E(Xn |D) = E(X|D) a.s.
n→∞
and the next theorem gives that φ and x 7→ E(Y | X = x) are almost identical if Y has
finite expectation. In words, the theorem says that any conditional expectation is
almost surely equal to the expectation in the conditional distribution.
Conditional moments 25
Theorem 1.36 Assume that X and Y are random variables defined on (Ω, F, P ) and
with values in (X , E) and (R, B) respectively. Let (Px )x∈X be the conditional
distribution of Y given X.
If E|Y | < ∞, then X(P )(A0 ) = 1, where
Z
A0 = {x ∈ X : |y| dPx (y) < ∞} .
In the last equality we have used extended Tonelli. This shows, that 2) is satisfied for
φ(X). Finally we have for A ∈ E
26 Conditional Distributions
Z Z
φ(X) dP = φ(x) dX(P )(x)
(X∈A) A
Z Z
= y dPx (y) dX(P )(x)
A∩A0
ZZ
= 1A∩A0 (x)y dPx (y) dX(P )(x)
Z
= 1A∩A0 (x)y d(X, Y )(P )(x, y)
Z
= 1A∩A0 (X)Y dP
Z
= Y dP
(X∈A∩A0 )
Z
= Y dP
(X∈A)
In the fourth equality we have used the extended Fubini’s theorem. This shows that
also 3) is fulfilled, such that φ(X) is a conditional expectation of Y given X. 2
The following result can be shown using the proof of Theorem 1.36:
Theorem 1.37 Assume that X and Y are random variables defined on (Ω, F, P ) with
values in (X , E) and (R, B) respectively. If E|Y | < ∞, then E|E(Y | X)| < ∞ and
E(E(Y | X)) = EY
Proof In the proof of Theorem 1.36 we saw that φ(X) = E(Y | X) is integrable, and
that Z Z
φ(X) dP = Y dP
(X∈A) (X∈A)
So for A = X we get
Z Z
E(E(Y | X)) = φ(X) dP = Y dP = EY
Theorem 1.41 Let X and Y be random variables defined on (Ω, F, P ) with values in
(X , E) and (R, B) respectively. If EY 2 < ∞, then
V Y = E V (Y | X) + V E(Y | X) .
as required. 2
Example 1.42 In example 1.26 we studied the situation where
X1 ξ1 Σ11 Σ12
∼ Nr+s , ,
X2 ξ2 Σ21 Σ22
Note: the conditional variance does not depend on x but is different from V (X1 ). 2
Confusing conditional variances and ordinary variances is a quite common mistake –
and that may lead to substantial problems.
Exercises 29
1.7 Exercises
Exercise 1.1 Assume that X1 and X2 are independent random variables that are both
binomially distributed with parameters (n, p). Define the random variable X = X1 + X2 . Find
the conditional distribution of X1 given X.
Exercise 1.2 Let X and Y be random variables defined on (Ω, F, P ). Assume that
(a) X has the binomial distribution with parameters (n, p1 )
(b) Assume that X is uniformly distributed on (0, 1). Assume that the conditional distribution
(Px )x∈(0,1) of Y given X is the exponential distribution with mean value x. Find EY .
Exercise 1.4 Let Y be a finite or countable set, and let K consist of all subsets of Y. Assume
that Y is a random variable defined on (Ω, F, P ) with values in (Y, K). Let p(y) denote the
probability function for Y . Let X be another finite or countable set, and assume that t : Y → X
is some map. Define X = t(Y ).
(b) Show that (Px )x∈X is the conditional distribution of Y given X, where each Px has probability
function
p(y)1{x} (t(y))
qx (y) =
r(x)
P (Y1 = 0) = 1 − p , P (Y1 = 1) = p
t(y1 , . . . , yn ) = y1 + · · · + yn
Define X = t(Y1 , . . . , Yn ).
(a) Realise that X has the binomial distribution with parameters (n, p) and argue that
P (X = x) > 0 for all x = 0, 1, . . . , n.
30 Conditional Distributions
(b) Show that (Px )x=0,...,n is the conditional distribution of Y = (Y1 , . . . , Yn ) given X, where Px
is the uniform distribution on {(y1 , . . . , yn ) ∈ {0, 1}n : y1 + · · · + yn = x}.
Exercise 1.6 Let X1 , X2 and X3 be independent random variables, where each Xi has a
Poisson distribution with parameter λi . Define X = X1 + X2 + X3 and show that the
conditional distribution of (X1 , X2 , X3 ) given X is given by (Px )x∈N0 , where each Px (for
x > 0) is a multinomial distribution with parameters x and (λ1 /λ, λ2 /λ, λ3 /λ), where
λ = λ1 + λ2 + λ3 : For all (x1 , x2 , x3 ) with x1 + x2 + x3 = x it holds that
x1 x2 x2
x! λ1 λ2 λ2
Px {(x1 , x2 , x3 )} =
x1 !x2 !x3 ! λ λ λ
Exercise 1.7 Let X and Y be random variables defined on (Ω, F, P ). Assume that
(a) X has the binomial distribution with parameters (n, p1 ).
Exercise 1.8 Let X and Y be random variables with values in (X , E) and (Y, K) respectively,
such that (Px )x∈X is the conditional distribution of Y given X. Assume that µ and ν are
σ–finite measures on (X , E) and (Y, K). Assume furthermore that X(P ) has density f with
respect to µ, and that for each x ∈ X the probability Px has density gx with respect to ν, such
that (x, y) 7→ gx (y) is E ⊗ K − B–measurable.
(a) Show that Z
`(y) = gx (y)f (x) dµ(x)
(c) Show that the conditional distribution of X given Y exists and is given by (Qy )y∈Y , where Qy
has density with respect to µ given by
gx (y)f (x)
ky (x) =
`(y)
for y ∈ B0 .
Exercise 1.9 Assume that X is Gamma–distributed with parameters (λ, β) and that the
conditional distribution of Y given X is given by (Px )x∈R , where Px is the Poisson distribution
with parameter x.
(a) Show that the marginal distribution of Y is a negative binomial distribution and find the
parameters.
Exercise 1.10 Let X and Y be real valued random variables defined on (Ω, F, P ). Let C ∈ B
be a fixed subset of R. Consider the following game: We are told the value of X, and are based
on this information supposed to guess whether Y ∈ C or not.
It seems natural to expect that we in two different games, where the same value of X is
observed, give the same guess of whether Y ∈ C or not – we know the same in the two
situations. Hence giving a rule for guessing must be the same as indicating a set A: If we observe
X ∈ A then we guess that Y ∈ C, and if we observe X ∈ / A, then we guess that Y ∈ / C.
Obviously, different choices of A may lead to more or less successful guessing rules (we define
a guessing rule to be successful, if it often leads to the right guess...). Let (Px )x∈R be the
conditional distribution of Y given X.
(a) Show that for a given guessing rule, then
Z Z
P (right guess) = Px (C) dX(P )(x) + Px (C c ) dX(P )(x)
A Ac
(b) Show that the optimal guessing rule corresponds to the set
1
A0 = {x ∈ R : Px (C) ≥ }.
2
(b) Find the Markov kernel (Qx )x∈X that is the conditional distribution of 1F given X.
Exercise 1.12 Assume that X is uniformly distributed on (0, 1) and that the conditional
distribution of Y given X = x is a binomial distribution with parameters (n, x) We could say
that Y has a binomial distribution with fixed length n and random probability parameter.
(a) What are the possible values of Y ? Argue that E|Y | < ∞.
(c) Find EY .
(d) Find P (Y = k) for all k being a possible value of Y . What is the marginal distribution of Y ?
Exercise 1.13 Let X and Y be random variables with values in (X , E) and (Y, K) respectively.
Assume that (Px ) is the conditional distribution of Y given X. Let
Z
A0 = {x ∈ X | |y| dPx (y) < ∞}
Z
φ(x) = 1A0 (x) |y| dPx (y) .
Exercise 1.14 Assume that X has the exponential distribution with mean 1, and assume that the
conditional distribution of Y given X = x is a Poisson distribution with parameter x. We could
say that Y is Poisson distributed with random parameter.
(a) Use Exercise 1.13 to argue that E|Y | < ∞.
(c) Find EY .
(d) Find P (Y = k) for all k being a possible value of Y . What is the marginal distribution of Y ?
Exercise 1.15 Let X and Y be independent random variables that both have the uniform
distribution on (0, 1). Define Z = XY .
(a) Find the conditional distribution of Z given X.
(b) What are the possible values of Z? Argue that E|Z| < ∞.
Sd−1 = {x ∈ Rd : ||x|| = 1}
(b) Use this fact to show that the conditional distribution of X given ||X|| = r is uniform on rSd−1 .
Exercise 1.18 The spherical coordinates of a point x = (x1 , x2 , x3 ) ∈ R3 \ {0} are (ρ, φ, θ)
determined as
x1 = r sin φ cos θ, x2 = r sin φ sin θ, x3 = r cos φ,
where r > 0, φ ∈ [0, π), and θ ∈ [0, 2π). Now let (R, F, T ) denote the spherical coordinates of
X, where X ∼ N3 (0, Id ).
(a) Find the joint density of (R, F, T ) w.r.t. Lebesgue measure on R+ × [0, π) × [0, 2π);
(b) Find the conditional distribution of (F, T ) given R and show that these are independent;
Exercises 33
(c) Deduce that if (F, T ) has density g(φ, θ) = sin φ/(4π) w.r.t. Lebesgue measure on
[0, π) × [0, 2π), then
Y = (sin F cos T, sin F sin T, cos T )
is uniform on S2 .
(f) Comment on the result, which is closely related to the Borel–Kolmogorov paradox.
Exercise 1.19 Assume that Y1 , Y2 , . . . is a sequence of independent and identically distributed
random variables such that E|Y1 | < ∞. Assume that N is a random variables with values in N
such that EN < ∞. Assume that N and (Y1 , Y2 , . . .) are independent (we consider
(Y1 , Y2 , . . .) as a random variable with values in (R∞ , B∞ )). Define the random variable Y by
N
X
Y = Yk
k=1
(a) Show that the conditional distribution (Pn )n∈N of Y given N is determined such that Pn is the
distribution of n
P
k=1 Y k . Argue similarly that the conditional distribution (Qn )n∈N of
PN
such that Qn is the distribution of n
P
k=1 |Yk | given N is determined k=1 |Yk |.
for all n ∈ N.
N
!
X
E |Yk | = EN E|Y1 | < ∞
k=1
b) Show that the conditional distribution of Y given X = x is given by the Markov kernel
Px , x > 0 where (
1 − e−y if y < x
Px (Y ≤ y) = .
1 if y ≥ x
c) Identify the joint distribution of (X, Y ), for example by specifying its joint distribution function.
Exercise 1.21 Let f and g be densities for distributions on [0, ∞). Assume that there exists a
constant c > 0 such that
f (x) ≤ cg(x) for all x ∈ [0, ∞)
Think of a situation where we want to simulate random variables with a distribution that has
density f , but where f is so complicated that this is not straightforward to do directly. Suppose
on the other hand that g is a simple well–known density that we actually can simulate from. An
algorithm to produce a random variable X with density f is the acceptance–rejection algorithm:
(i) Generate Y with density g and U uniform on (0, 1) such that Y ⊥
⊥U
(c) Conclude that the algorithm produces a variable X with density f , and discuss which value of c
we should choose.
Exercise 1.22 Think of a situation where we want to estimate the value z that is given by
z = EZ
for some real valued random variable Z with EZ 2 < ∞. Let Z1 , Z2 , . . . , Zn be independent
replications of Z. Then
n
1X
ẑn1 = Zk
n
k=1
is an estimator for z.
(a) Show that ẑn1 is unbiased
E ẑn1 = z
and find the variance V ẑn1 .
A method to improve the estimator could be finding some random variable X and consider the
new variable E(Z | X). Now let (Z1 , X1 ), . . . , (Zn , Xn ) be independent replications of
(Z, X), and define the estimator
n
1X
ẑn2 = E(Zk | Xk )
n
k=1
Apparently this method will improve the estimator no matter which variable X we choose. But
of course some choices may be more clever than others.
(c) What happens, if we use X = 1 (or some other constant), and why is this a bad idea anyway?
We will consider two specific examples of variables Z. In both examples we shall just let n = 1,
since increasing values of n simply makes both variances smaller by a factor 1/n, and thereby
does not change anything in the comparison.
In the first example we shall find estimators for the very well–known value π (although we
already know π much more accurately than we will ever be able to estimate, the example serves
as a very good illustration of what is going on). Let
Z = 4 · 1(U 2 +U 2 ≤1) ,
1 2
where U1 and U2 are independent and both uniform on (0, 1). Define the first estimator ẑ1 = Z.
(d) Show that E ẑ1 = π.
Define the estimator ẑ2 by
ẑ2 = E(Z | U1 )
p
(e) Show that ẑ2 = 4 1 − U12 .
(f) Try to simulate 10000 replications of both ẑ1 and ẑ2 . Compare the variances – and also compare
with the theoretical variance of ẑ1 .
In the next example, the estimation has some real practical use. Assume that X1 and X2 are
independent and has a distribution ν. Assume that X1 , X2 ≥ 0 and that ν has density f with
respect to the Lebesgue measure. Furthermore think of a situation, where the distribution of
S = X1 + X2 is complicated to calculate. We are interested in estimating
z(s) = P (S > x)
The problem is, that if x is very large, then it is very rare that this estimator is non–zero. Even if
we make many replications. Instead we shall try to construct an estimator using conditional
expectations.
Firstly, we try something similar to above. Define
Let
X(1) = min{X1 , X2 } and X(2) = max{X1 , X2 }
(h) Show that the conditional distribution of X(2) given X(1) is determined by the Markov kernel
(Py )y≥0 , where
ν(B ∩ (y, ∞))
Py (B) = .
ν((y, ∞))
Now assume that ν is the Weibull distribution with shape parameter 0.5. Then the density f is
given by
0.5
0.5x−0.5 e−x
for x > 0. And F̄ is
0.5
F̄ (x) = e−x
(j) Simulate 10000 replications of the three estimators (with e.g. x = 20 and x = 50) and compare
the variances.
Exercise 1.23 Let X be a real valued random variable with E|X| < ∞.
(a) Show that the conditional distribution of X given X is given by the Markov kernel (δx )x∈X ,
where δx is the Dirac Measure in x:
1, x ∈ B
δx (B) =
0, x ∈
/B
(c) Assume that Y is another real valued random variable with E|Y | < ∞ and E|XY | < ∞. Show
that E(XY | X = x) = xE(Y | X = x) and E(XY | X) = XE(Y | X).
Exercise 1.24 Let W be the set (0, 1)2 . Assume that we generate N points in W in the
following way: Let N be Poisson distributed with parameter λ and
(U11 , U12 ), (U21 , U22 ), . . . , (UN
1 2
, UN ) be independent and identically distributed such that Uk1 and
Uk are independent and uniformly distributed on (0, 1). This makes each (Uk1 , Uk2 ) uniformly
2
distributed on W .
In this exercise we will show that the collection of points (U11 , U12 ), . . . , (UN 1 2
, UN ) in W is a
Poisson process on W : Define for a subset A ⊆ W the random variable N (A) to be the number
of points in A:
XN
N (A) = 1(U k ,U k )∈A) .
1 2
k=1
Then
Exercises 37
(i) N (A) is Poisson distributed with parameter λm2 (A), where m2 (A) is the area (2–dimensional
Lebesgue measure) of A.
(ii) For disjoint sets A1 , . . . , Am the variables N (A1 ), . . . , N (Am ) are independent.
The result will follow by finding conditional distributions given N
(a) Show that for U1 and U2 independent and uniformly distributed on (0, 1) and A some subset of
W , then
P ((U1 , U2 ) ∈ A) = m2 (A)
(c) Show that N (A1 ), . . . , N (Am ) are independent and that each N (Aj ) is Poisson distributed
with parameter λm2 (Aj ).
Now assume that k : W → [0, 1] is a measurable function that is bounded by 1. Define for each
subset A of W the number
Z
K(A) = k(x, y) m2 (dx, dy)
A
(d) Give a suggestion for how to obtain a collection of points (V11 , V12 ), . . . , (VM
1 2
, VM ) in W , such
that for each subset A of W we have that the number of points in A
M
X
M (A) = 1((V 1 ,V 2 )∈A)
j j
k=1
In this chapter we will work on a general probability space (Ω, F, P ). All events
occurring will silently be assumed to be F-measurable, all σ-algebras occurring will
silently be assumed to be subalgebras of F, and all random variables
X : (Ω, F) → (X , E) will silently be assumed to be F − E measurable. The general
convention is that random variables with names like X or Xi or variations thereof have
values in a generic space (X , E), unless it is explicitly stated that they are real valued
(or integer valued or whatever). Similarly, variables with names like Y or Z will have
values in (Y, K) and (Z, G) respectively.
Recall that (X , E) is a Borel space if it is in bijective, bimeasurable correspondence
with (R, B) or a subspace of this. Such a correspondence enables us to replace X with
R, whenever there is an advantage in that. It turns out that every sensible space has this
property, unless it its very, very huge (non-separable metric spaces, with the σ-algebra
generated by the open sets, say). The above generic X , Y and Z-spaces are always
assumed to be Borel spaces.
P (A | H) = E(1A | H) .
The integrability condition (2.1) will in this case take the form
Z
P (A | H) dP = P (A ∩ H) for all H ∈ H . (2.2)
H
is satisfied for all H-sets H, both those of probability 0 (where there is nothing to
prove) and those of probability 1 (where there is also nothing to prove). Hence (2.3)
translates to
P (A ∩ B) = P (A) P (B) . (2.4)
A priori the formula has an a.s.-qualifier, but as it is a relation between deterministic
numbers, it is either true or false, with no probability involved.
Conditionally independent events 41
Hence we see that conditional independence of two events given a trivial σ-algebra is
simply classical independence of the events. 2
Example 2.3 If C is yet another event, and if H is the σ-algebra generated by that
event,
H = {∅, C, C c , Ω} ,
P (A ∩ C)
P (C)
on C
P (A | H) = a.s
P (A ∩ C c )
on C c
P (C c )
for any event A. If we suppose that H is non-trivial, meaning that P (C) ∈ (0, 1), we
see that (2.3) translates to the two conditions
P (A ∩ B ∩ C) P (A ∩ C) P (B ∩ C)
= ,
P (C) P (C) P (C)
P (A ∩ B ∩ C c ) P (A ∩ C c ) P (B ∩ C c )
c
= .
P (C ) P (C c ) P (C c )
These two conditions cannot be deduced from each other, and they are not related to
(2.4). For instance, the probability table
C Cc
c
B B B Bc
2 1 2 4
A 18 18 A 18 18
4 2 1 2
Ac 18 18 Ac 18 18
C Cc
c
B B B Bc
1 2 2 1
A 12 12 A 12 12
2 1 1 2
Ac 12 12 Ac 12 12
corresponds to a situation where A and B are independent, but where they are not
independent given H. 2
42 Conditional independence
D = {D1 , . . . , Dn }
where the atoms of D (the Di -sets) are pairwise disjoint and unite to the whole of Ω,
the σ-algebra generated by D is the family of all unions,
( )
[
H= Di | I ⊆ {1, . . . , n} .
i∈I
If we let
D∗ = {D ∈ D | P (D) > 0} ,
it is easily checked that
X P (A ∩ D)
P (A | H) = 1D a.s.
∗
P (D)
D∈D
P (A ∩ B ∩ D) P (A ∩ D) P (B ∩ D)
= for all D ∈ D∗ .
P (D) P (D) P (D)
Again, whether this holds or not is very sensitive to the specific atoms. If an atom is
divided into two, there is no telling if A and B are independent on each of the two
subatoms, just because we know if they are independent on the original atom. And
similarly, if two atoms are coalesced, we may loose or create conditional
independence, as the case may be. 2
A⊥
⊥ B|H ⇒ σ(A) ⊥⊥ σ(B) | H .
Conditionally independent σ-algebras 43
Proof A prototypical extension result. We know the theorem to be true for indicator
variables. Hence it is true for simple variables. The monotone convergence theorem for
conditional expectations will show it is true for non-negative variables, and a final
handwaving will dismiss the problems of positive and negative parts. 2
Conditional independence is by its very definition symmetric in the two events, or
more general, in the two classes of events. Rather surprisingly, it turns out that the
most fruitful way of working with the concept is through an asymmetric formulation:
Theorem 2.10 Let A, B and H be σ-algebras. It holds that A ⊥⊥ B | H if and only if
P (A | B ∨ H) = P (A | H) a.s (2.6)
{B ∩ H : B ∈ B, H ∈ H}
Proof Notice that for any three events A ∈ A, B ∈ B and H ∈ H we have that
Z Z Z
P (A | H) dP = 1B P (A | H) dP = E 1B P (A | H) | H dP
B∩H
ZH H
= P (A | H) P (B | H) dP. (2.7)
H
In the second equality we have used the integration property from the definition of
conditional expectations. In the third equality we have used that if X is H–measurable,
then E(XY | H) = XE(Y | H) (we also exploit that for indicator functions we
trivially have E|X| < ∞, E|Y | < ∞ and E|XY | < ∞ so the conditional
expectations are well defined).
Suppose that A and B are conditionally independent given H. Then we can work the
above line of equations one step further to see that
Z Z
P (A | H) dP = P (A ∩ B | H) dP = P (A ∩ B ∩ H) .
B∩H H
Since the events of the form B ∩ H is a generator for the σ-algebra B ∨ H that is stable
under formation of intersections, and as P (A | H) is H-measurable, and thereby in
Conditionally independent σ-algebras 45
Proof If A ⊥
⊥ B | H, we have from Theorem 2.10 that
P (A | B ∨ H) = P (A | H)
almost surely and hence we can let ZA = P (A | H). Conversely, if (2.8) holds, we
have for any H ∈ H ⊆ (B ∨ H) that
Proof Follows from Theorem 2.10 by the same extension technique, that was used to
prove Theorem 2.9. 2
46 Conditional independence
X⊥
⊥ Y |Z instead of σ(X) ⊥⊥ σ(Y ) | σ(Z)
without notification.
for A ∈ E, B ∈ K, C ∈ G.
In other words, (P ~ Q)x is the integration of Q w.r.t. Px . If µ is a probability measure
on X , we may think of µ as a Markov kernel from {0} to X and write the integration λ
of P w.r.t. µ as a combination in this sense
Z
λ(A × B) = Px (B) dµ(x) = (µ ~ P )(A × B).
A
We shall in the following not distinguish between Q and its extension Q̃.
Consider now Markov kernels P and Q as above, and further, a Markov kernel R from
Z to W. We then have
Proposition 2.15 Combination of Markov kernels is associative
(P ~ Q) ~ R = P ~ (Q ~ R)
Proof This is a direct consequence of the extended Tonelli’s Theorem 1.11. From
(2.10) we get
Z
{(P ~ Q) ~ R}x (B × C × D) = Rz (D) d(P ~ Q)x (y, z)
ZB×C
Z
= Rz (D) dQy (z) dPx (y)
ZB C
= (Q ~ R)y (C × D) dPx (y)
B
= {P ~ (Q ~ R)}x (B × C × D)
as desired. 2
Proof The conditional independence statement follows from Theorem 1.30 since then
R̃(y,z) = Rz — which represents the conditional distribution of W given (Y, Z) —
depends on Z only. 2
Suppose now that P is a Markov kernel from X to Y and Q a Markov kernel from X
to Z. We can then extend P and Q to be Markov kernels P̃ and Q̃ from X × Y and
X × Z and hence combine them in both directions as P ~ Q̃ or Q ~ P̃ . And, in fact,
these two combinations are identical:
Proposition 2.17 If P is a Markov kernel from X to Y and Q a Markov kernel from X
to Z the combination of these Markov kernels is commutative and equal to the product
Markov kernel:
(P ~ Q)x = (Q ~ P )x = Px ⊗ Qx .
Proof We have
Z
(P ~ Q)x (B × C) = Q̃(x,y) (C) dPx (y)
B
Z
= Qx (C) dPx (y) = Px (B)Qx (C)
B
P (A | B ∨ C ∨ D) = P (A | D),
P (A | B ∨ C ∨ D) = P (A | C ∨ D).
P (A | B ∨ C ∨ D) = P (A | B ∨ C) = P (A | B)
where we have used Theorem 2.10 in one direction twice. Using it in the other
direction gives
A ⊥⊥ (C ∨ D) | B.
For the intersection (A5) we get
P (A | B ∨ C) = P (A | B) = P (A | C)
where all equalities hold almost surely. Thus P (A | B ∨ C) is almost surely equal to an
A measurable function and almost surely equal to a B measurable function. Hence, by
Lemma A.11, P (A | B ∨ C) is almost surely equal to an B ∩ C-measurable function
and therefore
P (A | B ∨ C) = P (A | B ∩ C)
whereby A ⊥
⊥ (B ∨ C) | B ∩ C. Using Corollary 2.11 completes the proof. 2
Note that if we do not supplement A and B with the σ-ideal of null sets IP , the
corresponding variant of (A5) is not true in general. This is illustrated in the following
example.
Conditional independence revisited 49
Example 2.19 Let Ω = {0, 1}3 and F be the σ-algebra of all subsets of Ω. Define P as
p111 = p000 = 1/2
so that all six other atoms in F have probability zero.
Let Ai = σ(Xi ), i = 1, 2, 3, i.e. the σ-algebras generated by coordinate projections. It
then holds that
A1 ⊥ ⊥ A2 | A3 and A1 ⊥⊥ A3 | A2 .
But A2 ∩ A3 = {∅, Ω} so it is not true that A1 ⊥⊥ (A2 ∨ A3 ) | A2 ∩ A3 . However, from
(A5) we get
A1 ⊥⊥ A2 ∨ A3 | A2 ∩ A3 .
Indeed in this example we have A2 ∩ A3 = F since I consists of all subsets of the six
atoms with probability zero. Hence the last conditional independence is really an
uninteresting tautology. 2
Translating Theorem 2.18 to random variables, we get the following:
Corollary 2.20 Let (Ω, F, P ) be a probability space and X, Y , Z, W random
variables on Ω. Then the following properties hold.
(C1) X ⊥ ⊥ Y | Z =⇒ Y ⊥ ⊥ X | Z (symmetry);
(C2) (X ⊥ ⊥ Y | Z) ∧ (W = φ(Y )) =⇒ X ⊥⊥ W | Z (reduction);
(C3) X ⊥ ⊥ (Y, Z) | W =⇒ X ⊥ ⊥ Y | (Z, W ) (weak union);
(C4) (X ⊥ ⊥ Z | Y ) ∧ (X ⊥⊥ W | (Y, Z)) =⇒ X ⊥⊥ (Z, W ) | Y (contraction);
Proof This follows directly from the definition and Theorem 2.18 by realizing that,
for example, W = φ(Y ) =⇒ σ(W ) ⊆ σ(Y ). 2
When X, Y , and Z are discrete random variables the condition for X ⊥⊥ Y | Z
simplifies as
P (X = x, Y = y | Z = z) = P (X = x | Z = z)P (Y = y | Z = z),
where the equation holds for all z with P (Z = z) > 0. When the three variables admit
a joint density with respect to a product measure µ, we have
Proposition 2.21 Assume that the joint distribution of (X, Y, Z) has density w.r.t. a
σ-finite product measure µ on X × Y × Z. Then we have:
X⊥
⊥ Y | Z ⇐⇒ f (x, y | z) = f (x | z)f (y | z), (2.11)
X⊥
⊥ Y | Z ⇐⇒ f (x, y, z)f (z) = f (x, z)f (y, z), (2.12)
X⊥
⊥ Y | Z ⇐⇒ f (x, y, z) = f (x, z)f (y, z)/f (z) (2.13)
X⊥
⊥ Y | Z ⇐⇒ f (x | y, z) = f (x | z) (2.14)
X⊥
⊥ Y | Z ⇐⇒ f (x, z | y) = f (x | z)f (z | y) (2.15)
X⊥
⊥ Y | Z ⇐⇒ f (x, y, z) = h(x, z)k(y, z) for some h, k (2.16)
X⊥
⊥ Y | Z ⇐⇒ f (x, y, z) = f (x | z)f (y, z). (2.17)
where these equations hold almost surely with respect to P and we have used f as a
generic symbol for the densities involved.
50 Conditional independence
Proof Assume that the variables have density f (x, y, z) > 0 and that X ⊥⊥ Y | Z as
well as X ⊥
⊥ Z | Y . Then (2.16) gives for almost all values of (x, y, z) that
for suitable strictly positive functions g, h, k, l. Thus we have that for almost all
(x, y, z) that
k(x, z)l(y, z)
g(x, y) = . (2.19)
h(y, z)
It is illuminating to consider the special case when all state spaces are discrete. Define
the bipartite graph G + with vertex set V = Y ∪ Z by letting
y ∼+ z ⇐⇒ f (y, z) > 0.
If G + is connected — and H therefore is trivial — we first get from (2.18) that the
marginal distribution of Y and Z satisfies
hence we find
g(x, y2 ) = g(x, y1 )ḡ(y2 )/ḡ(y1 ).
Proceeding in the same way with y2 , z2 , and y3 yields
and if we continue this along the path we get for an arbitrary y that
We can now let π(x) = g(x, y ∗ ) and ρ(y) = ḡ(y)/ḡ(y ∗ ) and proceed as in the proof of
Proposition 2.22. 2
Note in particular that the proof of Proposition 2.23 effectively establishes (C5*) in the
discrete case.
(I4) if, knowing Y , reading the book Z is irrelevant for reading X and even after
having also read Z, reading W is irrelevant for reading X, then reading both of
Z and W is irrelevant for reading X.
Thus one can view the relations (A1)–(A4) as pure formal properties of the notion of
irrelevance. The property (A5) is slightly more subtle. In a certain sense, also the
symmetry (A1) is a somewhat special property of probabilistic conditional
independence, rather than general irrelevance.
It is thus tempting to use the relations such as these as formal axioms for conditional
independence or irrelevance. Indeed, it was conjectured (Pearl, 1988) that the
properties (C1)–(C4) were sound and complete axioms for probabilistic conditional
independence. However, the completeness fails. In fact, finite axiomatization of
probabilistic conditional independence is not possible (Studený, 1992).
A ⊥σ B | C ⇐⇒ α ⊥σ β | C, ∀α ∈ A, β ∈ B.
A⊥
⊥P B | C ⇐⇒ XA ⊥⊥P XB | XC ,
but in general this is not so for an arbitrary P , reflecting that pairwise independence
does not generally imply joint independence. 2
Fundamentally, graphical models exploit that graph separation is an independence
model, and indeed it is a full compositional graphoid.
Example 2.25. (Separation in an undirected graph) A very important example of a
model for the irrelevance axioms above is that of separation in undirected graphs. Let
A, B, and C be subsets of the vertex set V of a finite undirected graph G = (V, E).
Define
A ⊥G B | C ⇐⇒ C separates A from B in G.
Then it is not difficult to see that undirected graph separation ⊥G is a compositional
graphoid. 2
Example 2.26. (Second order independence) Sets of random variables A and B are
partially uncorrelated for fixed C if their residuals after linear regression on XC are
uncorrelated:
Cov{XA − E∗ (XA | XC ), XB − E∗ (XB | XC )} = 0,
where E∗ (XA | XC ) is the linear regression of XA on XC ; this is defined as the affine
function E∗ (XA | XC ) = α + β > XC that minimizes the second moment of the
residual E||XA − (α + β > XC )||2 . In other words we write A ⊥2 B | C if all partial
correlations ρAB·C are equal to zero. The relation ⊥2 satisfies the semigraphoid
axioms (S1)–(S4), composition (S6), and (S5) if there is no non-trivial linear relation
between the variables in V . 2
Example 2.27. (Geometric orthogonality) As another example, consider geometric
orthogonality in Euclidean vector spaces or in Hilbert spaces. Let L, M , and N be
linear subspaces of a Euclidean space V and define
L ⊥ M | N ⇐⇒ (L N ) ⊥ (M N ), (2.21)
where L N = L ∩ N ⊥ . Note that this is not the same as standard orthogonality as
this usually is defined to imply L ∩ M = {0} for orthogonal L and M . If (2.21) is
satisfied, then L and M are said to meet orthogonally in N . Again, it is not hard to see
that the orthogonal meet has the following properties:
(O1) if L ⊥ M | N then M ⊥ L | N ;
(O2) if L ⊥ M | N and U is a linear subspace of L, then U ⊥ M | N ;
(O3) if L ⊥ (M + U ) | N , then L ⊥ M | (N + U );
(O4) if L ⊥ M | N and L ⊥ U | (M + N ), then L ⊥ (M + U ) | N .
(O5) if L ⊥ M | N and L ⊥ N | M , then L ⊥ (M + N ) | (M ∩ N ).
(O6) if L ⊥ M | N and L ⊥ U | N then L ⊥ (M + U ) | N .
The direct analogue of (C5) does not hold in general; for example if M = N we may
have
L ⊥ M | N and L ⊥ N | M,
but if M and N are not orthogonal then it is false that L ⊥ (M + N ). 2
54 Conditional independence
Example 2.28. (Separation in a bidirected graph) There are other notions of graph
separation that determine compositional graphoid independence models. If A, B, and
C are subsets of the vertex set V of a finite bidirected graph B = (V, E), we say that C
b-separates A from B in B and write A ⊥B B | C if all paths from A to B intersect
V \ (A ∪ B ∪ C). This notion is dual to separation in undirected graphs and bidirected
graph separation ⊥B determines a compositional graphoid; see also Theorem 2.31
below. 2
Example 2.29. (Variation independence) Let U ⊆ X = ×v∈V Xv and define for
∗
S ⊆ V and u∗S ∈ XS ∩ U the S-section U uS of U as
∗
U uS = {uV \S : uS = u∗S , u ∈ U}.
i.e. if and only if the S-sections all have the form of a product space. The relation ‡U
satisfies the semigraphoid axioms. Note in particular that A ‡U B | S holds if U is the
support of a probability measure satisfying A ⊥⊥ B | S. 2
In the following we shall consider other interesting special cases, but first we wish to
establish that the independence model ⊥G so defined is indeed a compositional
graphoid:
Theorem 2.31 Let G = (V, E) be a general graph. Then the independence model
A ⊥G B | C determined by g-separation forms a compositional graphoid.
Proof Let G = (V, E) and consider disjoint subsets A, B, C, and D of V . We verify
each of the six properties separately.
Symmetry: If A ⊥G B | C then B ⊥G A | C. This is obvious from the definition.
Decomposition: If A ⊥G (B ∪ D) | C then A ⊥G B | C and A ⊥G D | C. Also
immediate from the definition.
Weak union: If A ⊥G (B ∪ D) | C then A ⊥G B | (C ∪ D). Using decomposition
yields A ⊥G D | C and A ⊥G B | C. Now suppose, for contradiction, that there
exist a connecting walk ω from A to B relative to C ∪ D. Then ω must have at
least one collider section, or it would also be connecting between A and B
relative to C. All collider sections on ω must intersect (C ∪ D) for ω to be
connecting. Also, ω must have a collider section intersecting D but disjoint from
C for else it would also be connecting relative to C. Consider the collider
section ρ which is closest to A on ω and let δ be the point nearest to A on ρ. The
vertices between A and δ on ω are not in B ∪ D and hence the subwalk of ω
consisting of these vertices connects between A and δ relative to C. This
contradicts the assumption that A ⊥G (B ∪ D) | C.
Contraction: If A ⊥G B | C and A ⊥G D | (B ∪ C) then A ⊥G (B ∪ D) | C. Suppose,
for contradiction, that there exists a walk between A and B ∪ D which is
connecting relative to C. Consider a shortest walk of this type and call it ω. This
walk must be between A and D since A ⊥G B | C. In addition, since all collider
sections on ω intersect C. As A ⊥G D | (B ∪ C), ω must have a non-collider
section that intersects B. This contradicts the fact that ω is a shortest walk
between A and B ∪ D which is connecting relative to C.
Intersection: If A ⊥G B | (C ∪ D) and A ⊥G D | (C ∪ B) then A ⊥G (B ∪ D) | C.
Suppose, for contradiction, that there exists a walk between A and B ∪ D that is
connecting relative to C. Consider a shortest walk of this type and call it ω. The
walk ω is either between A and B or between A and D. By symmetry we may
assume that ω is between A and B. Since all collider sections on ω intersect C
and A ⊥G B | (C ∪ D) ω must have a non-collider section that intersects D. This
contradicts that ω is a shortest walk between A and B ∪ D that is connecting
relative to C.
Composition: If A ⊥G B | C and A ⊥G D | C then A ⊥G (B ∪ D) | C. This is obvious
from the definition.
The proof is now complete. 2
Theorem 2.31 implies that we can focus on establishing conditional independence for
pairs of nodes, formulated in the corollary below.
56 Conditional independence
a 1
2 5 6
3 4 7 8 b
S
A ⊥m B | S ⇐⇒ A ⊥(DAn(A∪B∪S) )m B | S.
We then have:
Proposition 2.33 Let A, B and S be disjoint subsets of a directed, acyclic graph G.
Then A ⊥D B | S ⇐⇒ A ⊥m B | S.
Proof Since d-separation is a special instance of g-separation, it follows from
Corollary 2.32 that we only need to consider the case where A and B are singletons a
and b. We show the result by showing that every g-connecting walk between a and b
corresponds to a connecting walk in (DAn(a∪b∪S) )m and vice versa.
Suppose S does not d-separate a from b. Then there is a connecting walk ω from a to b
such as, for example, indicated in Fig. 2.1. This walk must lie proceed entirely within
An(a ∪ b ∪ S). For if some vertex γ ∈ ω is a collider on ω we must have γ ∈ S or the
walk would be blocked; and if γ is neither an ancestor of S nor a collider on the walk,
at least one of the subwalks away from γ would lead to a or b. If γ is a collider,
Conditional independence revisited 57
a 1
2 5 6
3 4 7 8 b
S
pa(γ) ∩ ω = {δ1 , δ2 } as for vertex 7 in Fig. 2.1, the marriage in the moral graph
between δ1 and δ2 means we can similarly replace (δ1 , γ, δ2 ) with (δ1 , δ2 ) and still
have a walk in the moral graph. Continuing in this fashion for all colliders on ω yields
a walk ω ∗ from a to b in (DAn(a∪b∪S) )m , circumventing S.
Suppose conversely that a is not separated from b in (DAn(a∪b∪S) )m . Then there is a
walk ω in this graph that circumvents S. The walk has pieces that correspond to edges
in the original graph and pieces that correspond to marriages. Each marriage edge
(δ1 , δ2 ) connects the parents of some vertex γ. If γ is in S we can simply replace the
piece (δ1 , δ2 ) of the walk with (δ1 , γ, δ2 ) as γ does not block this part of the walk in D.
If γ 6∈ S but has a descendant σ ∈ S, we instead modify the walk by replacing (δ1 , δ2 )
with (δ1 , γ, . . . , σ, . . . , γ, δ2 ), thus extending ω with a walk from γ to its first
descendant σ ∈ S and back again to γ. If neither of these, a or b must be a descendant
of γ since the ancestral set was smallest. In the latter case, a new walk can be created
in the new graph with one collider less, using the line of descent, such as illustrated in
Fig. 2.3. Continuing this substitution process eventually leads to an active walk from a
to b. Thus a is not d-separated from b by S and the proof is complete. 2
The use of Proposition 2.33 for deciding whether two sets A and B are separated by S
is illustrated in the following example.
a 1 a 1
d 2 4 5 d 2 4 5
c 3 6 7 b c 3 6 7 b
S S
a s sb
s? s
s? s y s
?
@
R s S = {x, y}
@
PP
s sc
PP
x q?
P
Example 2.34 Consider the directed acyclic graph in Fig. 2.4 and the problem of
deciding whether a ⊥D b | S.
There are two paths from a to b, one of them passing through y and one of them
avoiding y; the first path is blocked by y, whereas the second path is blocked both by x
and c. Thus we have a ⊥D b | {x, y}. If we consider S ∗ = {x} then the first path (via y)
becomes d-connecting so S ∗ is not d-separating. For S ∗∗ = {y}, the first path is still
blocked both by y and x, whereas the second path is blocked by the collider node c,
and hence it also holds that a ⊥D b | {y}. In this particular case we need only consider
paths and not walks.
The moral graph of the smallest ancestral set containing all the variables involved is
shown to the left in Fig. 2.5. It is immediate that S separates a from b in the graph to
a s sb a s sb a s sb
s s s s s
s s y s s y
@ @
@s S = {x, y} @s S ∗ = {x} S ∗∗ = {y}
x x
F IG . 2.5. The moral graphs of the smallest ancestral sets in the graph of Fig. 2.4
containing all variable involved are shown from left to right. S separates a from b
in the graph to the left, S ∗∗ separates in the graph to the right, wheras S ∗ does not
separate in the graph in the middle.
form that certain graph separations imply conditional independence statements in the
probabilistic independence model. More generally, G-Markov properties are
relationships between an independence model ⊥σ and separation properties in G.
Thus we shall consider the situation where we have a collection of random variables
(Xα )α∈V taking values in Borel spaces (Xα )α∈V . The probability spaces are either
real finite-dimensional vector spaces or finite and discrete sets. For A being a subset of
V we let XA = ×α∈A Xα and further X = XV . Typical elements of XA are denoted as
xA = (xα )α∈A . Similarly XA = (Xα )α∈A . We then use the short notation
A⊥ ⊥ B | C for XA ⊥ ⊥ XB | XC and so on. If we specifically want to emphasize the
dependence of the conditional independence relation on the specific probability
distribution P , we write ⊥
⊥P , but most of the time P will be fixed and given by the
context.
If a graph G = (V, E) is given with vertex set equal to the labels of the random
variables (Xα )α∈V we define
Definition 2.35 P is said to satisfy the global Markov property w.r.t. the graph G if for
all disjoint subsets A, B, S of V
(G) A ⊥G B | S =⇒ A ⊥⊥P B | S.
In other words, separation in the graph G implies conditional independence; or the map
A → XA is an independence homomorphism. We shall also say that X (or P ) is
globally Markov w.r.t. G if (G) holds. Further, we say:
Definition 2.36 P is said to be faithful to the graph G if for all disjoint subsets A, B, S
of V
A ⊥G B | S ⇐⇒ A ⊥⊥P B | S.
Thus a distribution P is faithful to G if and only if the independence models ⊥G and
⊥
⊥P are isomorphic. For a faithful distribution, the graph therefore gives a full picture
of the conditional independence relations among subsets of variables. Note that even
for a faithful distribution, there might be conditional independence relations among
other functions of the random variables than the coordinate projections
X → XA , A ⊆ V .
Whereas the global Markov property and the notion of faithfulness relates universally
to any graph with a separation property, there are a variety of Markov properties that
make reference to special types of graph. We shall discuss these in the following
subsections.
(P) the pairwise Markov property relative to G, if for any pair (α, β) of vertices
α 6∼ β =⇒ α ⊥⊥ β | V \ {α, β};
α ⊥⊥ V \ cl(α) | bd(α);
α⊥
⊥ V \ cl(α) | V \ {α, β}.
Proof We need to show that (P) implies (G), so assume that A ⊥G B | S, (P) holds,
and ⊥ ⊥P satisfies (S1)–(S5). Without loss of generality we may assume that both A
and B are non-empty. The proof is then reverse induction on the number of vertices
n = |S| in S. If n = |V | − 2 then both A and B consist of one vertex and the required
conditional independence follows from (P).
So assume |S| = n < |V | − 2 and that separation implies conditional independence
for all separating sets S with more than n elements. We first assume that
Markov properties 61
V = A ∪ B ∪ S, implying that at least one of A and B has more than one element, A,
say. If α ∈ A then A \ {α} ⊥G B | S ∪ {α} and also α ⊥G B | S ∪ A \ {α}; thus by the
induction hypothesis
A \ {α} ⊥
⊥P B | S ∪ {α} and α ⊥⊥P B | S ∪ A \ {α}.
xa = ya =⇒ ψa (x) = ψa (y).
where C is the set of cliques of G. If P factorizes, we say that P has property (F) and
the set of such probability measures is denoted by MF (G). We have
Proposition 2.40 For any undirected graph G and any probability distribution on X it
holds that
(F) =⇒ (G) =⇒ (L) =⇒ (P).
62 Conditional independence
Proof We only have to show that (F) implies (G) as the remaining implications are
given in Proposition 2.37. Let (A, B, S) be any triple of disjoint subsets such that S
separates A from B. Let à denote the connectivity components in GV \S which contain
A and let B̃ = V \ (Ã ∪ S). Since A and B are separated by S, their elements are in
different connectivity components of GV \S and any clique of G is either a subset of
à ∪ S or of B̃ ∪ S. If CA denotes the cliques contained in à ∪ S, we thus obtain from
(2.24) that
Y Y Y
f (x) = ψc (x) = ψc (x) ψc (x) = h(xÃ∪S )k(xB̃∪S ).
c∈C c∈CA c∈C\CA
where (xa , x∗ac ) is the element y with yγ = xγ for γ ∈ a and yγ = x∗γ for γ 6∈ a. Since
x∗ is fixed, Ha depends on x through xa only. Let further for all a ⊆ V
X
φa (x) = (−1)|a\b| Hb (x).
b:b⊆a
Markov properties 63
From this relation it is also clear that φa depends on x through xa only. Next we can
apply Lemma A.12 (Möbius inversion) to obtain that
X
log f (x) = HV (x) = φa (x)
a:a⊆V
such that we have proved the theorem if we can show that φa ≡ 0 whenever a is not a
complete subset of V . So let us assume that α, β ∈ a and α 6∼ β. Let further
c = a \ {α, β}. If we write Ha as short for Ha (x) we have
X
(−1)|c\b| Hb − Hb∪{α} − Hb∪{β} + Hb∪{α,β} .
φa (x) = (2.26)
b:b⊆c
Let d = V \ {α, β}. Then, by the pairwise Markov property and (2.17), we have
f (xb , xα , xβ , x∗d\b )
Hb∪{α,β} (x) − Hb∪{α} (x) = log
f (xb , xα , x∗β , x∗d\b )
f (xα | xb , x∗d\b )f (xβ , xb , x∗d\b )
= log
f (xα | xb , x∗d\b )f (x∗β , xb , x∗d\b )
f (x∗α | xb , x∗d\b )f (xβ , xb , x∗d\b )
= log
f (x∗α | xb , x∗d\b )f (x∗β , xb , x∗d\b )
f (xb , x∗α , xβ , x∗d\b )
= log
f (xb , x∗α , x∗β , x∗d\b )
= Hb∪{β} (x) − Hb (x).
Thus all terms in the curly brackets in (2.26) add to zero and henceforth the entire sum
is zero. This completes the proof. 2
When (A, B, S) form a decomposition of G the Markov properties decompose
accordingly. This is expressed formally in three propositions below.
Proposition 2.42 Assume that (A, B, S) decompose G = (V, E). Then a probability
distribution P factorizes with respect to G if and only if both its marginal distributions
PA∪S and PB∪S factorize with respect to GA∪S and GB∪S respectively and the
densities f satisfy
Y Y
f (x) = ψc (x) ψc (x) = h(xA∪S )k(xB∪S ).
c∈A c∈B\A
where Z
k̄(xS ) = k(xB∪S )µB (dxB ),
and similarly with the other marginals. This gives (2.27) as well as the factorizations of
both marginal densities.
Conversely, assume that (2.27) holds and that fA∪S and fB∪S factorize. Then let
1
if fS (xS ) 6= 0
ψS (xS ) = fS (xS )
0 otherwise.
Since fS is obtained from integration of f , the latter must also be almost everywhere
zero when fS is. Hence
where S are the separators of G with multiplicities ν(S), C the set of cliques of G, and
fA , A ∈ C ∪ S are the marginal densities of XA , A ∈ C ∪ S.
consider a DAG with n + 1 vertices so that (O) holds for ⊥σ and let v ∗ = n + 1. Then
for any α ≤ n the inductive assumption implies
and hence the inductive assumption ensures that the recursive combinations are
identical. 2
Remark: We may therefore without ambiguity omit the specific topological ordering
and write P = ~v∈V P v .
Definition 2.47 The Bayesian network (D, P ) generated by D and (P v )v∈V is the
recursive combination P = ~v∈V P v of (P v )v∈V w.r.t. D.
Markov properties 67
For a DAG D we say that P admits a recursive kernel factorization (R) if there exists a
a system (P v )v∈V of Markov kernels that are adapted to D in the sense that each P v is
a Markov kernel from Xpa(v) to Xv and P = ~v∈V P v . We first note
Proposition 2.48 If P admits a recursive kernel factorization according to the
directed, acyclic graph D and A is an ancestral set, then the marginal distribution PA
admits a recursive factorization according to GA .
Proof For any ancestral set A there is a topological ordering of V so that α < β for
all α ∈ A and β ∈ V \ A. Hence we may write
where the assigments are made according to a topological ordering of the vertices of a
DAG D and Uv are independent and uniformly distributed on (0, 1). Then, by
Corollary 1.25, this defines a system of Markov kernels that is adapted to D and the
recursive combination of these Markov kernels represents the distribution of
Xv , v ∈ V . 2
In fact, by Theorem 1.28, any adapted system of Markov kernels and thus any
Bayesian network can be represented by a system of structural equations as above.
68 Conditional independence
Generally, a Bayesian network defined by stuctural equations may not have a density
w.r.t. any product measure. But if it has, the results above can be strengthened. We say
that a probability distribution P admits a recursive density factorization according to
D, if there exist non-negative functions, henceforth referred to as kernels,
k α (·, ·), α ∈ V defined on Xα × Xpa(α) , such that
Z
k α (yα , xpa(α) )µα (dyα ) = 1
We then also say that P has property (F). It is an easy induction argument to show that
Proposition 2.51 P admits a recursive density factorization if and only if the kernels
k α (·, xpa(α) ) are densities for the conditional distribution of Xα , given
Xpa(α) = xpa(α) .
Proof Left to the reader as Exercise 2.8. 2
m
Also it is immediate that if we form the undirected moral graph D (marrying parents
and deleting directions) such as described towards the end of Section B.1, we have
Lemma 2.52 If P admits a recursive density factorization according to the directed,
acyclic graph D, it factorizes according to the moral graph Dm and therefore obeys
the global Markov property relative to Dm .
Proof The factorization follows from the fact that, by construction, the sets
{α} ∪ pa(α) are complete in Dm and we can therefore let ψ{α}∪pa(α) = k α . The
remaining part of the statement follows from the fact that (F) implies (G) in the
undirected case; see Proposition 2.40. 2
Generally, if P admits a recursive density factorization it also admits a recursive kernel
factorization.
We may now extend Theorem 2.49 to
Theorem 2.53 Let D be a directed, acyclic graph. For a probability distribution P on
X which has density with respect to a product measure µ, the following conditions are
equivalent:
(F) P admits a recursive density factorization according to D;
(R) P admits a recursive kernel factorization according to D;
(G) P obeys the directed global Markov property, relative to D;
(L) P obeys the directed local Markov property, relative to D;
(O) P obeys the ordered Markov property, relative to D.
Proof This follows as (R) and (F) are equivalent when the joint distribution have a
density w.r.t. a product measure, cf. Theorems 1.18 and 1.19. 2
Markov properties 69
α β γ α β γ α β γ α β γ
F IG . 2.6. Four Markov equivalent graphs. Their associated independence models are
in all cases α ⊥G γ | β.
independence models are the same although the graphs are different. This also means
that any probability distribution P which satisfies the global Markov property for any
of them, automatically satisfies the global Markov property for all of them. We
formally define
Definition 2.54 Two graphs G1 and G2 are Markov equivalent if and only if their
independence models coincide, i.e. if A ⊥G1 B | S ⇐⇒ A ⊥G2 B | S.
Generally, independence models based on directed acyclic graphs are different from
those based on corresponding undirected graphs, but occasionally, as in Figure 2.6,
they are identical. More precisely we first define:
Definition 2.55 A directed acyclic graph D is said to be perfect if all parents of
common children are married, i.e. if for any triple α, β, γ with α → γ ← β, we have
α ∼ β.
Perfect DAGs are Markov equivalent to their skeleton. More precisely:
Proposition 2.56 A directed acyclic graph D is Markov equivalent to its skeleton
G = ske(D) if and only if D is perfect.
Proof The proof is by induction on the number of vertices |V | of D. For |V | ≤ 3 the
only non-perfect DAG is a triple α, β, γ with α → γ ← β and α 6∼ β, where then
α ⊥D β is the only independence whereas, for the skeleton, the only independence is
α ⊥G β | γ.
For |V | > 3, consider a triplet A, B, S and let v ∗ be a terminal vertex outside
A ∪ B ∪ S. If this does not exist, we have An(A ∪ B ∪ S) = V and we have
A ⊥m B | S ⇐⇒ A ⊥G B | S where G = ske(D) is the skeleton of D. Else remove v ∗
and use the induction hypothesis.
For the converse, the inductive assumption implies that we only have to consider the
case where a terminal vertex v ∗ has unmarried parents α and β. These are then
separated in the skeleton by V \ {α, β} but not d-separated as the walk α → v ∗ ← β is
active relative to V \ {α, β}. 2
In general, the question of Markov equivalence of two directed acyclic graphs is
slightly more subtle. Before we explore this further, we need a few lemmas.
Lemma 2.57 Let D = (V, E) be a directed acyclic graph. Then for α 6= β it holds
that α 6∼ β if and only if there exists S ⊆ V \ {α, β} such that α ⊥D β | S.
70 Conditional independence
Proof If α ∼ β, the walk (α, β) connects α and β given any S and hence we do not
have α ⊥D β | S.
Conversely, if α 6∼ β we let A = An(α, β) be the smallest ancestral set containing
{α, β} and subsequently S = A \ {α, β}. It is also true that α 6∼ β in the moral graph
(DA )m as α and β have no common children in A: since all elements of A are
ancestors of α or β a directed path from a common child to either of them would create
a cycle. Hence α ⊥m β | S and thus, by Proposition 2.33 α ⊥D β | S. 2
Note that the same result is trivially true for an undirected graph G, where we can use
S = V \ {α, β}. Indeed it is true for any general graphical independence model ⊥G as
defined earlier, but we refrain from showing the lemma in this generality here.
Further we define
Definition 2.58 An arrow α → β is covered in a DAG D if pa(β) = pa(α) ∪ α.
Note that if D∗ is obtained from D by replacing the arrow α → β with β → α then
β → α is covered in D∗ if and only if α → β is covered in D. Covered edges can be
reversed without changing the independence model, as the next lemma says.
Lemma 2.59 Let D be a DAG and let D∗ be obtained from D by replacing the edge
α → β with β → α. Then D∗ is a DAG which is Markov equivalent to D if and only if
α → β is covered.
Proof Assume first that the arrow α → β is covered. To show that D∗ is a DAG we
assume for contradiction that there is a directed cycle in D∗ which then must include
the arrow β → α since D was a DAG. Let this cycle be
ω ∗ = (α1 → · · · → γ → β → α → · · · → α1 ).
ω = (α1 → · · · → γ → α → · · · → α1 )
ω = (u ∼ · · · ∼ γ1 ∼ α → β ∼ γ2 · · · ∼ v).
ω 0 = (u ∼ · · · ∼ γ1 ∼ α = γ2 ∼ · · · ∼ v)
ω 00 = (u ∼ · · · ∼ γ1 = γ2 ∼ · · · ∼ v)
Markov properties 71
ω 000 = (u ∼ · · · ∼ γ1 → β ← γ2 · · · ∼ v)
connects. Every time the walk includes α → β we modify the walk as above and
eventually obtain a walk ω̃ which connects in both D and D∗ .
If β 6∈ S it is never a collider on ω. If now γ̃1 ∈ pa(β) we modify ω as
ω̃ 0 = (u ∼ · · · ∼ γ̃1 → β → γ̃2 · · · ∼ v)
and this walk will still be connecting. Working through all the appearances of α → β
eventually yields a walk that is connecting in both D and D∗ .
For the converse we consider an edge α → β which is not covered. Then there is a
γ ∈ pa(β) \ pa(α) with γ 6= α or a γ ∈ pa(α) \ pa(α). Consider the former case: If
α → γ, reversing α → β creates a cycle (α → γ → β → α) and thus D∗ is not
acyclic. Hence we may assume that α 6∼ γ and thus by Lemma 2.57 there is an S such
that α ⊥D γ | S. Then β 6∈ S for else would (α → β ← γ) connect. But then
(γ → β → α) connects in D∗ and thus D and D∗ are not Markov equivalent.
If γ ∈ pa(α) \ pa(β) we argue similarly, just reversing the role of D and D∗ . This
completes the proof. 2
We define an unshielded collider tripath to be an induced subgraph of the form
α → γ ← β, i.e. arrows meet head-to-head at γ but α 6∼ β. Such structures are
preserved under the operation of reversing a covered edge:
Lemma 2.60 Let D be a DAG and let D∗ be obtained from D by replacing a covered
edge α → β with β → α. Then D and D∗ have the same skeleton and the same
unshielded collider tripaths.
Proof The skeleton is clearly unchanged by any edge reversal. Also, none of the
edges involved in an unshielded collider tripath α → γ ← β are covered as then α is a
parent of γ but not a parent of β. 2
Further we have
Lemma 2.61 If two directed acyclic graphs D1 = (V, E1 ) and D2 = (V, E2 ) with
D1 6= D2 have the same skeleton ske(D1 ) = ske(D2 ) and the same unshielded
collider tripaths, then there exists a covered edge α → β in E1 \ E2 .
Proof The proof is constructive and gives a simple algorithm for identifying such an
edge. First we consider a topological ordering of D1 and let β be the minimal element
of this ordering satisfying pa1 (β) \ pa2 (β) 6= ∅. Further, let α be the maximal element
of pa1 (β) \ pa2 (β). We shall argue by contradiction that α → β is indeed covered.
So assume for contradiction that there exists a vertex γ ∈ pa1 (β) \ pa1 (α) with
γ 6= α. Then we must have α → γ in E1 for else we would have an unshielded collider
tripath contradicting that α → β ∈ E1 \ E2 . But then either α → γ is in E1 \ E2 or
γ → β must be in E1 \ E2 for else D2 would contain a directed cycle. But the former
contradicts the minimality of β and the latter the maximality of α.
72 Conditional independence
If there were a vertex γ ∈ pa1 (α) \ pa1 (β) we would have γ ∈ pa2 (α) since β was
chosen to be minimal. Since α → β cannot be part of an unshielded collider tripath,
there must be an edge β → γ in E1 which would create a cycle.
Hence we conclude that α → β is covered. 2
We are then ready to show the main result about Markov equivalence of directed
acyclic graphs.
Theorem 2.62 Two directed acyclic graphs D1 = (V, E1 ) and D2 = (V, E2 ) are
Markov equivalent if and only if they have the same skeleton ske(D1 ) = ske(D2 ) and
the same unshielded collider tripaths.
Proof From Lemma 2.57 it follows that two Markov equivalent DAGs must have the
same skeleton. If we have two DAGs D1 and D2 with the same skeleton and the same
unshielded colliders, Lemma 2.61 yields that we can find a covered edge in E1 \ E2 .
Reversing this edge yields a new DAG D10 with E10 \ E2 having one element less.
Lemma 2.60 ensures that also D10 and D1 have the same skeleton and same unshielded
collider tripaths and Lemma 2.59 ensures D10 is Markov equivalent to D1 . Continuing
in this matter eventually transforms D1 to D2 and every step preserves Markov
equivalence, hence D1 is Markov equivalent to D2 .
For the converse we simply realise that if α → γ ← β is an unshielded collider tripath
in D1 which is not unshielded in D2 , any set S which satisfies α ⊥D1 β | S cannot
include γ where as it must include γ to ensure α ⊥D2 β | S. 2
Note that it follows from the proof that if D1 and D2 are Markov equivalent, there is a
sequence of covered arrow reversals transforming D1 into D2 .
Exercises 73
2.7 Exercises
Exercise 2.1 Let Y and Z be real valued random variables such that EY 2 < ∞ and
EZ 2 < ∞. Let X be a random variable with values in the measurable space (X , E). Define the
conditional covariance between Y and Z given X by
x − B = {x − y : y ∈ B}
Qx (B) = Px (x − B)
Rx (A × B) = Px (A ∩ (x − B))
for A, B ∈ B.
(b) Show that (Rx )x∈R is the conditional distribution of (X1 , X2 ) given X1 + X2 .
.
74 Conditional independence
X1 ⊥
⊥ X2 | X1 + X2 + X3 .
.
Exercise 2.3 Assume that X is a real random variable and that (Px )x∈R is the conditional
distribution of Y given X, where Px is the exponential distribution with mean |x|.
(b) Assume that X ∼ N (0, 1). Simulate 10000 independent replications of (X, Y ), and plot the
points (Xn , Yn )n=1,...,10000 .
(c) Find E(Y | X = x) and V (Y | X = x) theoretically and use this to explain the plot.
Exercise 2.4 Assume that U1 , U2 and U3 are independent and identically distributed according
to the uniform distribution on (0, 1). Define the real random variables X, Y and Z as follows:
X = U12
Y = −X log(1 − U2 )
Z = −2X log(1 − U3 )
(a) Find the conditional distribution of Y given X and the conditional distribution of Z given X.
(g) Let U4 be another uniformly distributed random variable independent of (U1 , U2 , U3 ), and
define Z2 = −2U42 log(1 − U3 ). Argue that Y ⊥ ⊥ Z2 . Simulate 10000 replications of (Y, Z)
and (Y, Z2 ), plot these replications in two plots and explain the difference.
Exercise 2.5 Prove Proposition 2.21.
Exercise 2.6 Show that if the distribution of X | Z is degenerate so that X in effect is a
deterministic function of Z, then X ⊥⊥ Y | Z for all possible random variables Y .
Exercise 2.7 Let (X, Y, Z) be random variables with a discrete and finite state space.
(a) Show that if (X, Y, Z) are all binary, it holds that
X⊥
⊥ Y and X ⊥
⊥ Y | Z =⇒ (X, Z) ⊥
⊥ Y or X ⊥
⊥ (Y, Z);
Exercises 75
(b) Find a counterexample to the analogous result when state spaces are discrete but may have more
than two states.
Exercise 2.8 Prove Proposition 2.51.
Exercise 2.9 Let X = (X1 , X2 , X3 )> ∼ N3 (0, Σ) be a multivariate Gaussian distribution.
(a) Show that X1 ⊥
⊥ X3 | X2 if and only if σ13 σ22 = σ12 σ23 ;
(b) Use this to show that for multivariate Gaussian variables it holds that
X1 ⊥
⊥ X3 and X1 ⊥
⊥ X3 | X2 =⇒ (X1 , X2 ) ⊥
⊥ X3 or X1 ⊥
⊥ (X2 , X3 ).
(a) Write down all conditional independence statements for this graph corresponding to the pairwise
Markov property;
(b) Write down all conditional independence statements for this graph corresponding to the local
Markov property;
(c) Write down some of the conditional independence statements for this graph which follow from
the global Markov property and which are not listed above.
P (U = 1) = P (Z = 1) = P (U = 0) = P (Z = 0) = 1/2,
W = U , Y = Z, and X = W Y . Show that this distribution satisfies (L) but not (G) w.r.t. the
graph below.
s s s s s
U W X Y Z
76 Conditional independence
Exercise 2.15 Consider the distribution over four binary variables which gives probability 1/8
to all of the 8 configurations displayed in the figure below:
1 r r1
1 r r1
r1 r1 1 r r1
1 r r0 0 r r1
1 r r0 0 r r1
1 r r0 0 r r1
0 r r0 0 r r0
1 r r0 0 r r1
0 r r0
0 r r0
Note that there are only four variables. The only reason that the graph (four-cycle) is repeated is
to see the obvious pattern in the configuration.
Show that this distribution satisfies (G) with respect to the four cycle, but the distribution does
not factorize with respect to this graph, i.e., it does not satisfy (F).
Hint: Assume that it factorizes and show that if it is positive on these configurations, it must be
positive on all 16 possible configurations of the four binary variables.
Exercise 2.16 Let the joint distribution of (X, Y ) have density f (x, y) w.r.t. a product measure
ν ⊗ µ. The conditional entropy H(X | Y ) is defined as the average entropy in the conditional
distribution
h i
H(X | Y ) = E E {− log f (X | Y ) | Y }
Z Z
= −f (x | y) log f (x | y)ν(dx) f (y) µ(dy).
y x
H(X | Y ) ≤ H(X),
X⊥
⊥ Y | Z ⇐⇒ H(X, Y, Z) + H(Z) = H(X, Z) + H(Y, Z).
Exercise 2.17 Let ⊥σ be an independence model on a finite set V and let M ⊆ V . The
marginal independence model ⊥σM is simply the restriction of ⊥σ to triples (A, B, S) with
Exercises 77
A ⊥M
σ B | S ⇐⇒ A ⊥σ B | (S ∪ M ).
(a) Show that ⊥σM and ⊥M σ inherit the properties of ⊥σ , such that, e.g., if ⊥σ is a compositional
graphoid, so are its marginal and conditional;
(b) Show that for a probability distribution P with associated independence model ⊥
⊥P , the
independence model of the marginal distribution PM is indeed the marginal of ⊥⊥P ;
(c) Show that for a probability distribution P with associated independence model ⊥
⊥P , the
independence model of the conditional distributions (PxM ) of XV \M given XM is indeed the
conditional model of ⊥⊥P ;
(d) Show that if ⊥ ⊥P is globally Markov w.r.t. an undirected graph G, then the conditional
distributions (PxM ) of XV \M given XM are globally Markov w.r.t. the induced subgraph
GV \M ;
(b) List all conditional independence relations corresponding to the local, directed Markov property;
(d) Which of the following separation statements are true? For those that are not true, identify an
active walk.
(a) 2 ⊥D 4 | 5;
(b) 2 ⊥D 7 | 5,
(c) 1 ⊥D 7 | 5, 6;
(d) 1 ⊥D 4 | 6;
Exercise 2.19 Consider the following directed acyclic graphs, and in each case, list all DAGs in
their Markov equivalence class and verify in every single case whether they are Markov
equivalent to an undirected graph.
(a) 1 → 2, 3 → 2, 2 → 4, 4 → 5, 2 → 5;
(b) 1 → 2, 2 → 3, 2 → 4, 4 → 5, 6 → 5;
(c) 1 → 2, 2 → 3, 2 → 4, 4 → 5, 5 → 6;
Exercise 2.20 Consider a directed acyclic graph D with arrows
A → B, B → D, B → E, C → E, D → E, D → F, E → F .
78 Conditional independence
(b) Assume P satisfies the local directed Markov property with respect to D. Which of the
following statements can be concluded? Explain your reasoning.
C⊥
⊥ D | B, A⊥
⊥ C | E, B⊥
⊥ F | {E, A}.
(c) Consider the following directed acyclic graphs obtained from D by reversing arrows:
(i) D1 has reversed the arrow from A → B, i.e. it has arrows
B → A, B → D, B → E, C → E, D → E, D → F, E → F ;
(ii) D2 has reversed the arrow from D → E, i.e. it has arrows
A → B, B → D, B → E, C → E, E → D, D → F, E → F .
(iii) D3 has reversed the arrow from C → E, i.e. it has arrows
A → B, B → D, B → E, E → C, D → E, D → F, E → F .
Which of these directed acyclic graphs are Markov equivalent to D?
(d) Which of the directed acyclic graphs above are Markov equivalent to an undirected graph?
3
LOCAL COMPUTATION
The potentials φC (x) depend on xC = (xv , v ∈ C) only. The basic task is to calculate
the marginal probability X
p(x∗E ) = p(x∗E , yV \E )
yV \E
for E ⊆ V and fixed x∗E , but this sum has too many terms if V is large as then X is
huge and has cardinality at least 2|V | . A second purpose of the computation is to get
the prediction p(xv | x∗E ) = p(xv , x∗E )/p(x∗E ) for v ∈ V . We first consider a simple
example:
80 Local computation
and assume each of X, Y , Z, and W has, say, 100 states. The joint state space has thus
108 states, and to calculate p(x) directly from p(x, y, z, w) by brute force involves 106
terms in the sum for every x, hence 108 arithmetic operations are needed. This is
possible, but time consuming, and in networks with many variables, direct calculation
becomes impossible.
Instead, we may use the factorization p(x, y, z, w) = φ(x, y)ψ(y, z)η(z, w) as follows:
1. Calculate η ∗ (z) = w η(z, w), with 10000 additions;
P
Now the marginal p∗ (x) is equal to φ∗ (x) so we calculated our quantity of interest
with only 50000 operations. Note in particular that we never explicitly formed the
product p(x, y, z, w) = φ(x, y)ψ(y, z)η(z, w). The product only appears conceptually,
guiding the specific computations. 2
Y
φC (xC ) = kv (xv | xpa(v) );
v:Cv =C
with the usual convention that the product over the empty set is equal to 1 so we get
φC ≡ 1 for cliques C that have no node assigned. We also assign potentials to
separators, initially φS ≡ 1 for all S ∈ S, where S is the set of separators in the
junction tree.
We now define the joint potential of the junction tree as
Q
Y φC (xC )
κ(x) = f (x) = kv (xv | xpa(v) ) = QC∈C . (3.1)
v∈V S∈S φS (xS )
and emphasize that only the clique potentials are actually computed whereas the
product above is a conceptual quantity.
From Bayes’ formula in Corollary 1.21 we also note that the conditional density of
XV \E given XE = x∗E is determined as
f (x | x∗E ) = κ(x)/p(x∗E ).
Formally, we shall incorporate evidence XE = x∗E by multiplying the clique potentials
with appropriate indicator functions, i.e.
φCv (x) ← φCv (x)1{x∗v } (xv ), v ∈ E.
We shall see below that the expression on the right-hand side of (3.1) will remain
invariant under the message passing process.
For simplicity we shall in the following assume that all state spaces Xv are discrete and
finite and densities are always expressed w.r.t. counting measure.
φ↓A ↓A
X
B (x) = φB (xA ) = φB (y)
yB :yA∩B =xA∩B
The distributivity ensures that we can move factors in a sum outside of the summation
sign.
[Link] Local control: Allow clique to send message if and only if it has already
received message from all other neighbours. Such messages are live.
Using this protocol, there will be one clique who first receives messages from all its
neighbours. This is effectively the root R in C OLLECT E VIDENCE and
D ISTRIBUTE E VIDENCE.
Additional messages never do any harm (ignoring efficiency issues) as κ is invariant
under message passing.
Exactly two live messages along every branch is needed.
φ↓A
B (x) = max φB (y)
yB :yA∩B =xA∩B
This also satisfies consonance and distributivity and C OLLECT E VIDENCE yields
maximal value f . Further, D ISTRIBUTE E VIDENCE yields configuration with maximum
probability.
Since (3.1) remains invariant under both kinds of message passing, one can switch
freely between max- and sum-propagation.
3.2.8 An example
To illustrate the previous developments, we consider in detail a simple example. More
precisely, consider the directed acyclic graph in Fig. 3.1. and consider the Bayesian
B D B D
A F A F
C E C E
F IG . 3.1. A directed acyclic graph to be used as base for a Bayesian network and its
moral graph.
network with all variables taking values in {0, 1} and conditional probabilities
Probability propagation 85
P (A = 1) = 3/4;
P (B = 1 | A = 1) = 3/4; P (B = 1 | A = 0) = 1/4;
P (C = 1 | A = 1) = 2/3; P (C = 1 | A = 0) = 1/2;
P (D = 1 | B = 1) = 3/4; P (D = 1 | B = 0) = 1/2;
P (E = 1 | C = 1) = 3/5; P (E = 1 | C = 0) = 1/2;
P (F = 1 | B, C) = (B + C)/2.
ABC BC BCF B BD
CE
F IG . 3.2. Junction tree for the moral graph of the Bayesian network in Fig. 3.1.
EC, and F to BCF which yields the clique potentials in Table 3.1, whereas the
separator potentials all are initialized with values 1.
We have now initialized the system so we can calculate any conditional probability of
interest.
To obtain P (B = 1 | E = 1, F = 1), we first incorporate the information that
E = F = 1 into the tables and obtain the updated tables in Table 3.2. This is simply
done by replacing entries corresponding to values of E = 0 or F = 0 by zero.
We are now ready for message passing, but need to choose a root clique; if we only
want to get P (B = 1 | E = 1, F = 1), we can make things easy for ourselves by
choosing a root clique containing B, for example BD. Then we can avoid
D ISTRIBUTE E VIDENCE as C OLLECT E VIDENCE to BD alone yields the correct BD
marginal. D ISTRIBUTE E VIDENCE is only needed if we wish to calculate more
probabilities.
86 Local computation
TABLE 3.1. Initial clique potentials for the junction tree in Fig. 3.2.
Clique State Potential
ABC 1 1 1 3/4 × 3/4 × 2/3 = 3/8
1 1 0 3/4 × 3/4 × 1/3 = 3/16
1 0 1 3/4 × 1/4 × 2/3 = 1/8
1 0 0 3/4 × 1/4 × 1/3 = 1/16
0 1 1 1/4 × 1/4 × 1/2 = 1/32
0 1 0 1/4 × 1/4 × 1/2 = 1/32
0 0 1 1/4 × 3/4 × 1/2 = 3/32
0 0 0 1/4 × 3/4 × 1/2 = 3/32
BCF 1 1 1 1
1 1 0 0
1 0 1 1/2
1 0 0 1/2
0 1 1 1/2
0 1 0 1/2
0 0 1 0
0 0 0 1
BD 1 1 3/4
1 0 1/4
0 1 1/2
0 0 1/2
CE 1 1 3/5
1 0 2/5
0 1 1/2
0 0 1/2
Probability propagation 87
TABLE 3.2. Revised clique potentials for the junction tree in Fig. 3.2 after incorporat-
ing information that E = F = 1.
Clique State Potential
ABC 1 1 1 3/8
1 1 0 3/16
1 0 1 1/8
1 0 0 1/16
0 1 1 1/32
0 1 0 1/32
0 0 1 3/32
0 0 0 3/32
BCF 1 1 1 1
1 1 0 0
1 0 1 1/2
1 0 0 0
0 1 1 1/2
0 1 0 0
0 0 1 0
0 0 0 0
BD 1 1 3/4
1 0 1/4
0 1 1/2
0 0 1/2
CE 1 1 3/5
1 0 0
0 1 1/2
0 0 0
88 Local computation
For C OLLECT E VIDENCE we now first send messages from ABC to BCF and from
CE to BCF . We find the separator potential on BC by marginalizing the ABC
potential over A and similarly for the separator C. We obtain the separator potentials
in Table 3.3.
TABLE 3.3. Separator potentials after sending messages from ABC to BCF and from
CE to BCF .
Sep State Pot Sep State Pot Sep State Pot
BC 1 1 3/8 + 1/32 = 13/32 C 1 3/5 B 1 1
1 0 3/16 + 1/32 = 7/32 0 1/2 0 1
0 1 1/8 + 3/32 = 7/32
0 0 1/16 + 3/32 = 5/32
The clique potentials in clique BCF then changes after message passing from ABC
to BCF and from CE to BCF as in Table 3.4.
TABLE 3.4. Clique potential for BCF after incorporating E = F = 1 and sending
messages from ABC to BCF and from CE to BCF .
Clique State Potential
BCF 1 1 1 1 × 13/32 × 3/5 = 39/160
1 1 0 0
1 0 1 1/2 × 7/32 × 1/2 = 7/128
1 0 0 0
0 1 1 1/2 × 7/32 × 3/5 = 21/320
0 1 0 0
0 0 1 0
0 0 0 0
Finally, C OLLECT E VIDENCE is completed after sending the last message from BCF
to BD, yielding the separator potentials in Table 3.5 and the clique potentials in
Table 3.6.
TABLE 3.5. Separator potentials after completion of C OLLECT E VIDENCE to the root
BD.
Sep State Pot Sep State Pot Sep State Pot
BC 1 1 13/32 C 1 3/5 B 1 39/160+7/128=191/640
1 0 7/32 0 1/2 0 21/320
0 1 7/32
0 0 5/32
Probability propagation 89
TABLE 3.6. Clique potentials for the junction tree in Fig. 3.2 after incorporating infor-
mation that E = F = 1 and C OLLECT E VIDENCE to the root BD.
Clique State Potential
ABC 1 1 1 3/8
1 1 0 3/16
1 0 1 1/8
1 0 0 1/16
0 1 1 1/32
0 1 0 1/32
0 0 1 3/32
0 0 0 3/32
BCF 1 1 1 39/160
1 1 0 0
1 0 1 7/128
1 0 0 0
0 1 1 21/320
0 1 0 0
0 0 1 0
0 0 0 0
BD 1 1 3/4 × 191/640 = 573/2560
1 0 1/4 × 191/640 = 191/2560
0 1 1/2 × 21/320 = 21/640
0 0 1/2 × 21/320 = 21/640
CE 1 1 3/5
1 0 0
0 1 1/2
0 0 0
The root clique BD now contains the correct (unnormalized) marginal potential and
the normalizing constant can be obtained by adding clique potentials in clique BD to
yield
The conditional probability we were looking for is then obtained by normalizing the
clique potential of BD and adding appropriate entries
640
P (B = 1 | E = 1, F = 1) = (573/2560 + 191/2560) = 191/233 ≈ 0.81974
233
90 Local computation
and the BCF clique is then updated by the ratio of the new potential to the old, to
yield Table 3.7; note that indeed this does not change the BCF potential as the original
BD potential was not modified, so the BD clique has nothing new to report to BCF .
We next calculate separator potentials associated with messages from BCF to ABC
and CE and display these in Table 3.8.
Note that all separator potentials add up to the general normalizing constant 233/640.
Probability propagation 91
Finally, updating the clique potentials in ABC and CE yields the potentials in
Table 3.9.
TABLE 3.9. Final clique potentials after incorporating information that E = F = 1,
C OLLECT E VIDENCE, and subsequent D ISTRIBUTE E VIDENCE.
Clique State Potential
ABC 1 1 1 3/8 × 39/160 × 32/13 = 9/40
1 1 0 3/16 × 7/128 × 32/7 = 3/64
1 0 1 1/8 × 21/320 × 32/7 = 3/80
1 0 0 1/16 × 0 = 0
0 1 1 1/32 × 39/160 × 32/13 = 3/160
0 1 0 1/32 × 7/128 × 32/7 = 1/128
0 0 1 3/32 × 21/320 × 32/7 = 9/320
0 0 0 0
BCF 1 1 1 39/160
1 1 0 0
1 0 1 7/128
1 0 0 0
0 1 1 21/320
0 1 0 0
0 0 1 0
0 0 0 0
BD 1 1 573/2560
1 0 191/2560
0 1 21/640
0 0 21/640
CE 1 1 3/5 × 99/320 × 5/3 = 99/320
1 0 0
0 1 1/2 × 7/128 × 2/1 = 7/128
0 0 0
Again we note that all clique potentials add up to 233/640 and if we wish to calculate,
say P (A = 1 | E = 1, F = 1), we simply add up and normalize
640
P (A = 1 | E = 1, F = 1) = (9/40 + 3/64 + 3/80) = 198/233 ≈ 0.84979.
233
Suppose we instead wish to identify the most probable configuration of the variables
A, B, C, D given E = 1 and F = 1. This can be found by using maximum in the
marginalizations instead of sums. We do not need to start afresh, as the current
92 Local computation
potentials in the junction tree have all information needed. For a change, we might now
choose the clique BCF as root and the first step is then to send messages from all the
other cliques to BCF yielding new separator potentials as displayed in Table 3.10.
Next, for D ISTRIBUTE E VIDENCE, we send max-messages away from BCF to obtain
the final separator potentials, displayed in Table 3.12.
The final step is incorporating the messages in the other cliques, the results being
displayed in Table 3.13
Note again that all clique and separating potentials have the same maximal value
which is the probability of the most likely configuration jointly with the evidence
P (A = B = C = D = E = F = 1) = 27/160 ≈ .16875
and hence
3.3 Exercises
Exercise 3.1 Consider the DAG D with arrows
A → C, B → C, B → D, C → E, D → F, E → G, E → H, F → G, G → J, I → J.
(a) Find the moral graph Dm of D;
(b) Find a minimal chordal cover G of Dm , i.e. a chordal graph G ⊃ Dm with the property that
removal of any edge in G which is not an edge in Dm will not be chordal;
where θ 6= 0.
(a) Find the dependence graph of P determined as the smallest graph G so that P is Markov
(pairwise, local, and globally) w.r.t. G and identify its cliques;
For a |d| × |e| matrix A = {aγµ }γ∈d,µ∈e we let [A]Γ denote the matrix obtained from
A by filling up with zero entries to obtain full dimension |Γ| × |Γ|, i.e.
(
Γ
aγµ if γ ∈ d, µ ∈ e
[A] γµ =
0 otherwise.
When matrix operations are combined with forming submatrices, we use the
convention that the matrix operation is performed first, i.e.
A−1 −1
d = A d
.
96 Multivariate normal models
[Link] Exact results Using (D.1), we get the likelihood function, expressed in the
parameter K as
n
Y
L(K) = (2π)−n|Γ|/2 (det K)n/2 exp {−hy ν , Ky ν i/2}
ν=1
( n
)
X
n/2 ν > ν
∝ (det K) exp − (y ) K(y )/2
ν=1
We have let y be the n × |Γ| matrix with (y ν )> as rows. For later use we introduce the
matrix of sum of squares and products W as
n
X
w= y ν (y ν )> = y > y.
ν=1
.
To maximize the likelihood function, we choose to take advantage of the theory of
exponential models. Although it is unnecessary in this particular case, it turns out to be
convenient when we later discuss graphical models with conditional independence
restrictions.
The expression (4.1) identifies the statistical model determined by the family of
multivariate normal distributions with unknown concentration matrix K as an
exponential model. To see this, we first recall from (C.5) that
hA, Bi = tr(A> B)
defines an inner product on the vector space of matrices of any fixed dimension, in
particular also on the subspace S|Γ| of symmetric |Γ| × |Γ| matrices.
We define the canonical parameter as θ = K, the base measure µ as Lebesgue measure
on Rn×|Γ| , and the canonical statistic as t(y) = −w/2. Then the exponent in (4.1) can
be written as
− tr(Kw/2) = hθ, t(y)i.
The cumulant function is found as
ψ(K) = log{(2π)n|Γ|/2 (det K)−n/2 } = (n|Γ|/2) log(2π) − (n/2) log det K. (4.2)
Basic facts and concepts 97
w = y> y
is positive definite. This happens with probability one if n ≥ |Γ| and never when
n < |Γ|. When the estimate exists it is given as
Yγ ⊥
⊥ Yµ | YΓ\{γ,µ} ⇐⇒ kγµ = 0,
for all γ ∈ Γ. Let further C = {cαβ }α,β∈Γ be the matrix obtained by scaling K to have
all diagonal elements equal to one,
kγµ
cγµ = p .
kγγ kµµ
Then cγµ , the off-diagonal elements in C, are equal to the negative partial correlation
coefficients
Cov(Yγ , Yµ | YΓ\{γ,µ} )
ργµ | Γ\{γ,µ} = = −cγµ .
V(Yγ | YΓ\{γ,µ} )1/2 V(Yµ | YΓ\{γ,µ} )1/2
and
−kγµ
Cov(Yγ , Yµ | YΓ\{γ,µ} ) = .
kγγ kµµ − (kγµ )2
Note that it also holds that
2 2 det Σ det ΣΓ\{γ,µ}
ργµ | Γ\{γ,µ} = (cγµ ) = 1 − . (4.5)
det ΣΓ\{γ} det ΣΓ\{µ}
Covariance selection models 99
and
kµµ
det ΣΓ\{µ} = det ΣΓ\{γ,µ} V(Yγ | YΓ\{γ,µ} ) = det ΣΓ\{γ,µ} ,
kγγ kµµ − (kγµ )2
which both are easy consequences of (1.7). From Example 1.20 we have that the
conditional distribution of Yγ given YΓ\{γ} = yΓ\{γ} is univariate normal. Writing the
conditional expectation as
X
ξγ + βγµ | Γ\{γ} (yµ − ξµ )
µ∈Γ\{γ}
4.1.4 Interaction
It is illuminating to investigate the additive terms in the logarithm of the normal
density, thereby highlighting the analogy to interaction expansions of discrete models.
Using the expression (D.1) for the multivariate normal density we get
1X X
log f (y) = c − hy, K(y)i/2 = c − kγγ yγ2 − kγµ yγ yµ (4.6)
2
γ∈Γ {γ,µ}
where {γ, µ} in the sum above represent all unordered pairs of elements of Γ, and c is
a constant.
The expansion shows that the logarithm of the density is additively composed of
quadratic main effects with coefficients −kγγ /2and quadratic interactions with
coefficients −kγµ . We will sometimes use the terms interactions and main effects
referring directly to the coefficients and also omit the negative signs and the division
by two. So, for example, we will refer to kγγ as the quadratic main effect of the
variable γ, although this, strictly speaking, should refer to −kγγ yγ2 /2.
We emphasize that the interaction terms of highest order in (4.6) involve pairs of
variables, and there are no terms involving groups of variables with three or more
elements. This is in contrast to the discrete case and it follows in particular that within
the normal distribution there are no hierarchical interaction models which are not
conformal.
Let S(G) denote the set of symmetric matrices A satisfying for all γ, µ ∈ Γ that
γ 6∼ µ =⇒ aγµ = 0
and S + (G) those elements of S(G) that are positive definite. Then the covariance
selection model for Y can be compactly described as
For an arbitrary matrix A, we let A(G) denote the matrix with entries
(
0 if γ 6∼ µ
A(G)γµ =
aγµ otherwise.
The restriction which is imposed on the distribution of Y by the model is linear in the
canonical parameter K. Hence the hypothesis K ∈ S + (G) is an affine hypothesis and
it follows that a covariance selection model is itself a regular exponential model with
canonical statistic equal to −w(G)/2. The following result about maximum likelihood
estimation then follows directly.
Covariance selection models 101
Theorem 4.3 In the covariance selection model, the maximum likelihood estimate of
the unknown covariance matrix exists if
w = y> y
is positive definite. If n ≥ |Γ| this happens with probability one. When the estimate
exists it is determined as the unique solution to the system of equations
leaving all other entries of K unchanged. This operation is clearly well defined if wcc
is positive definite. If we let a = Γ \ c and exploit (C.2) we find
−1
(K −1 )cc = Σcc = Kcc − Kca (Kaa )−1 Kac
, (4.10)
Tc Σ = Σ − Σ[H]Γ Σ
hence Tc K does indeed adjust the marginals. From (4.9) it is seen that the pattern of
zeros in K is preserved, i.e. Tc K is in S(G) if K is, and applying Lemma C.1 to (4.11)
shows that it stays positive definite. Hence the adjusted concentration matrix Tc K is in
S + (G) if K is.
In fact, it is not difficult to see that the operation Tc also scales proportionally in the
sense that
f (yc | wcc /n)
f {y | (Tc K)−1 } = f (y | Σ) .
f (yc | Σcc )
This clearly demonstrates the analogy to the procedure used for hierarchical log–affine
models.
Next we choose any ordering (c1 , . . . , ck ) of the cliques in G. Choose further an
arbitrary starting value K0 ∈ S + (G) and define recursively for r = 0, 1, . . .
Then we have
Theorem 4.4 Consider a sample from a covariance selection model with graph G and
assume that w is such that the maximum likelihood estimate K̂ of K exists. Then
K̂ = lim Kr .
r→∞
Decomposable models 103
Proof We must realize that this is a special instance of iterative partial maximization,
discussed in Section A.4. To do this, we let
Θ0 = K ∈ S + (G) | L(K) ≥ L(K0 ) ,
X Γ
X Γ
K = Σ−1 = [KC ] − ν(S) [KS ]
C∈C S∈S
Xh iΓ X h iΓ
−1 −1
= (ΣC ) − ν(S) (ΣS )
C∈C S∈S
as well as Q
C∈Cdet ΣC
det Σ = Q . (4.15)
S∈S (det ΣS )ν(S)
Using the alternative expression where the separators and cliques are not numbered
and the expression for the determinant (4.15), we also get
Proposition 4.5 In a decomposable covariance selection model with graph G, the
maximum likelihood estimate of the mean vector and concentration matrix exists with
probability one if and only if n > maxC∈C |C|. It is then given as
( )
Xh iΓ X h iΓ
−1 −1
ξˆ = ȳ, K̂ = n (wC ) − ν(S) (wS ) , (4.17)
C∈C S∈S
where C is the set of cliques of G and S the separators with multiplicities ν(S). The
determinant of the estimate can be calculated as
Q ν(S)
(det wS )
det K̂ = n|Γ| S∈S
Q . (4.18)
C∈C det wC
where S = W/n. There are efficient methods for solving this problem, using lasso
regression and techniques from convex optimization. The maximizing value K̂ λ will
The graphical lasso 105
λ
typically have k̂uv = 0 for several uv and will thus identify an independence graph. In
that way, the graphical lasso is often used for graphical model selection.
It is important to realize that the graphical lasso is not scale-invariant. More precisely,
if we let Y = A−1 X, where A is a diagonal matrix, then Y has covariance
ΣY = A−1 ΣX A−1 and SY = A−1 SX A−1 ; similarly, the concentration matrix of Y is
K Y = AK X A. Thus
X
2`pen (K Y )/n = 2 log au + log det K X
− tr(AK X AA−1 SA−1 ) − λ||AK X A||1
= const + log det K X − tr(K X SX ) − λ||AK X A||1
∼ 2`pen (K X )/n − λ(||AK X A||1 − ||K X ||1 ).
Data are therefore often first scaled by using the empirical correlation matrix R as
input instead of the covariance matrix S = W/n, yielding a scale-invariant procedure.
λ∗ (||K ∗ ||1 − c) = 0; S − Σ∗ + λ∗ Γ∗ = 0
S − Σ + λ∗ Γ = 0
Algorithm 4.1 G RAPHICAL LASSO for maximizing the penalized Gaussian likelihood
Input: Empirical covariance matrix S; penalty parameter λ;
Output: Glasso estimate K̂ λ ; concentration graph Ĝ λ .
1. Initialize Σ ← S + λI; βuv ← 0, u, v ∈ V .
2. Repeat for v ∈ V until convergence
(a) For u ∈ V \ v until convergence:
P
βuv ← T suv − w6=v σuw βwv ; λ /σvv ;
P
(b) For u ∈ V \ {v} do σuv ← w6=v σuw βwv ;
3. For v ∈ V do:
P
(a) kvv ← 1/(σvv − w6=v σvw βwv )
(b) For u ∈ V \ v do kuv ← −βuv kvv .
4. Return K and incidence graph of K.
An alternative algorithm for maximizing the penalized likelihood is just modifying IPS
updates on 2 × 2 matrices. More precisely, we are simply iteratively maximizing the
penalized likelihood over Kcc for c = {u, v}, keeping (Kca , Kaa ) fixed, where
The graphical lasso 107
Algorithm 4.2 Modified 2 × 2 IPS algorithm for computing K̂ λ with lasso penalty.
Input: Graph G = (V, E), sample covariance matrix S, penalty parameter λ.
Output: Glasso estimate K̂ λ ; concentration graph Ĝ λ .
and further
∗
suv + λ if suv + λ < suv
s̃uv = suv − λ if suv − λ > s∗uv
∗
suv otherwise.
and further
!
suu s̃uv ˜ = (S̃cc )−1 − (Σcc )−1
S̃cc = , ∆
s̃uv svv
˜ H = {∆
Update Kcc = Kcc + ∆; ˜ −1 + (Σcc )−1 }−1 ; Σ − Σ[H]Γ Σ
3. Return K, Σ, and incidence graph of K.
a = V \ c, and then cycling through all pairs c until convergence. This algorithm is
again a special case of iterative partial maximization and it is described in more detail
in Algorithm 4.2.
To see that this algorithm is convergent, we just need to verify that each update
depends continuously on its input and use Proposition A.15, since the algorithm is a
special case of Iterative Partial Maximization.
108 Multivariate normal models
4.5 Exercises
Exercise 4.1 Show that any independence model generated by a regular Gaussian distribution is
a compositional graphoid.
Exercise 4.2 A positive definite symmetric matrix K is an M-matrix (after Minkowski) if all
off-diagonal elements are non-positive, i.e. kαβ ≤ 0 for all α 6= β. Let Σ = K −1 .
Show that if K is a M-matrix, all off-diagonal elements of Σ are non-negative i.e. σαβ ≥ 0 for
all α 6= β.
Y1 ← X1 , Y2 ← X2 + Y1 , Y3 ← 2X3 + Y2 , Y4 ← X4 + Y3 , Y5 ← X5 + 2Y4 .
Exercise 4.4 Consider a Gaussian distribution N5 (0, Σ) with K = Σ−1 satisfying the
conditional independence restrictions of the graph G = (V, E) with V = {1, 2, 3, 4, 5} and
E = {{1, 2}, {1, 3}, {1, 4}, {1, 5}}.
(a) Show that the determinant of Σ satisfies
5
Y 5
Y
det Σ = σii (1 − ρ21j )
i=1 j=2
(b) Express the covariance σ23 in terms of the variances σ11 , σ22 , σ33 , σ44 , σ55 and the covariances
σ12 , σ13 , σ14 , σ15 .
Exercise 4.5 Consider a Gaussian distribution N4 (0, Σ) with K = Σ−1 satisfying the
conditional independence restrictions of the graph G = (V, E) with V = {1, 2, 3, 4} and
E = {{1, 2}, {2, 3}{1, 4}{3, 4}}.
(a) Find two equations of degree 3 in σ13 and σ24 expressing these in terms of σ11 , σ22 , σ33 , σ44
and the covariances σ12 , σ13 , σ14 , σ15 ;
Hint: Express the appropriate inverse element of the covariance matrix as a cofactor;
(b) Consider the likelihood equations based on observing a Wishart matrix W = w with
W ∼ W(n, Σ). Use the answer under (a) to establish an equation of degree 5 for the maximum
likelihood estimate of σ13 .
(c) Assume next that σ11 = σ22 = σ33 = σ44 = 1 and σ12 = σ23 = σ34 = ρ and σ14 = −ρ.
Show that then ρ2 < 1/2.
Exercises 109
Exercise 4.6 Consider a Gaussian distribution N4 (0, Σ) with K = Σ−1 satisfying the
conditional independence restrictions of the graph G = (V, E) with V = {1, 2, 3, 4} and
E = {{1, 2}, {2, 3}, {3, 4}, {1, 4}}. Assume that the following Wishart matrix has been
observed, with 10 degrees of freedom:
5 1 4 4
1 10 2 5
.
4 2 10 2
4 5 2 8
(a) Perform one full cycle of the IPS algorithm to find the MLE of the concentration matrix, starting
with K = I.
(b) Assume next that K = Σ−1 satisfies the conditional independence restrictions of the graph
G ∗ = (V, E ∗ ) with V = {1, 2, 3, 4} and E ∗ = {{1, 2}, {2, 3}, {3, 4}}. Find the maximum
likelihood estimate of the concentration matrix.
110 Multivariate normal models
APPENDIX A
SOME MATHEMATICAL PREREQUISITES
Let (X , E) and (Y, K) be two measurable spaces. Then we can consider the product
space (X × Y, E ⊗ K). Here the product σ–algebra E ⊗ K is generated by the system
of all product sets
D = {A × B : A ∈ E, B ∈ K}
Note that D is stable under intersections. If λ and λ̃ are two measures on
(X × Y, E ⊗ K) that are equal on product sets
λ(A × B) = λ̃(A × B)
X −1 (A) = (X ∈ A) ∈ F
σ(X) = {(X ∈ A) : A ∈ E}
Theorem A.9 Assume that X is a random variable with values in (X , E) and that Z
is a real–valued random [Link] Z is σ(X)–measurable if and only if there
exists a measurable function φ : (X , E) → (R, B) such that Z = φ ◦ X.
We further need the following concept. Let (Ω, F) be a measurable space.
Definition A.10 A subset I ⊆ F is a σ-ideal in F if
i) ∅ ∈ I;
S∞
ii) A1 , . . . , An , . . . ∈ I =⇒ 1 Ai ∈ I;
iii) A ∈ I, F ∈ F =⇒ A ∩ F ∈ I.
Note that {∅} is always a σ-ideal, the trivial σ-ideal. We shall in particular be
interested in the σ-ideal IP of P -null sets where
I = IP = {F ∈ F : P (F ) = 0}
which clearly is a σ-ideal. We shall typically write I for IP when it is clear from the
context.
The null-extension A is the smallest σ-algebra generated by A and I. We have the
following Lemma.
Lemma A.11 Assume that X is a random variable on (Ω, F, P ) and A and B are
sub-σ-algebras of F. If there is an A-measurable random variable Y and a
B-measurable Z so that X = Y = Z almost surely, then there is a random variable W
so that X = W almost surely and W is A ∩ B-measurable.
Proof We have X = Y = Z except on the set D = DY ∪ DZ where DY and DZ are
null-sets. Now define W = X(1 − 1D ) = Y (1 − 1D ) = Z(1 − 1D ). Clearly, W is
A ∩ B-measurable and W = X almost surely. 2
The latter sum is equal to zero unless a \ c = ∅, i.e. if c = a, because any finite,
non-empty set has the same number of subsets of even as of odd cardinality. The proof
of (1) =⇒ (2) is performed analogously. 2
The Abelian group referred to in the lemma can be the real numbers, but often also just
the additive group of a real vector space L, the vector space of linear maps on L or a
vector space S of symmetric matrices, etc. More general versions of the lemma exist
that relate to general lattices rather than the lattice of subsets of a set; see for example
Aigner (1979).
Thus the empty set is convex and any singleton set is convex. Convexity of sets is
closed under intersection so ∩α∈A Cα is convex if all Cα are convex.
A real-valued function f : C → R, defined on a convex set C is said to be convex if it
for all x1 , x2 ∈ C satisfies the inequality
f (tx1 + (1 − t)x2 ) ≤ tf (x1 ) + (1 − t)f (x2 ) ∈ C for all t with 0 < t < 1. (A.2)
We say that f is if the inequality in (A.2) is strict unless x1 = x2 . The real functions
f (x) = |x| and f (x) = x2 are examples of strictly convex functions. For any convex
function it holds that the level sets
Ca = {x : f (x) ≤ a}, a ∈ R
are all convex sets. Note that the converse to this statement is false in general unless
L = R.
It can be practical to define f for all x ∈ V by letting f (x) = ∞ for x 6∈ C; the
inequality (A.2) is then satisfied for all x1 , x2 ∈ V . If we do not explicitly say
otherwise, we shall always consider f extended in this way. The domain of f is the set
of points where f is finite.
Suppose V is a Euclidean space with inner product h·, ·i and that f is convex with
dom f open and f is differentiable for all x ∈ dom f . It then holds for all
x, y ∈ dom f that
f (y) ≥ f (x) + h∇f (x), y − xi (A.3)
where the gradient ∇f (x) is determined as
∂
f (x + tu) = h∇f (x), ui.
∂t t=0
∂2
f (x + su + tv) = hu, Hf (x)vi.
∂s∂t s=t=0
minimize f (x)
subject to gi (x) ≤ 0, i = 1, . . . , k, (A.5)
hi (x) = 0, j = 1, . . . , l,
maximize f (x)
subject to gi (x) ≥ 0, i = 1, . . . , k, (A.6)
hi (x) = 0, j = 1, . . . , l,
116 Some mathematical prerequisites
where f and gi are concave and hi affine. Clearly any concave problem can be
modified into a convex problem by appropriate sign changes. The domain of the
problems is in both cases the convex set D where
k
\
D = dom f dom gi .
i=1
A point x ∈ D is feasible if it satisfies all the constraints. The set F of feasible points
is convex. The problem is said to be feasible if F is non-empty. Thus, in a convex
optimization problem we are minimizing the convex function f over the convex set F.
The optimal value of the problem is
f ∗ = inf{f (x) | x ∈ F}
The dual function is concave and may in principle take the value −∞. Also, if λi ≥ 0
for all i we have for any feasible point x ∈ F that L(x, λ, ν) ≤ f (x) so then
maximize d(λ, ν)
subject to λi ≥ 0, i = 1, . . . , k. (A.9)
This optimization problem is the dual problem to (A.5) which is then called the primal
problem. The pair (λ, ν) is said to be dual feasible if λi ≥ 0 for all i and
d(λ, ν) > −∞. A pair (λ∗ , ν ∗ ) that is optimal for (A.9) is dual optimal and the the
optimum value shall be denoted d∗ . We thus always have
d∗ ≤ f ∗ .
For most, but not all, convex problems we also have f ∗ = d∗ and this phenomenon is
referred to as strong duality. Strong duality is ensured by what is known as Slater’s
condition (Slater, 1950). A feasible point x ∈ F is said to be strictly feasible if for all
non-affine gi , i = 1, . . . , k it holds that gi (x) < 0, i.e. the inequality constraints are
strict.
Theorem A.13. (Slater) If there is an x ∈ ri D which is strictly feasible, then there is
a dual optimum (λ∗ , ν ∗ ) with
−∞ < d(λ∗ , ν ∗ ) = d∗ = f ∗ .
Proof See Section 5.3.2 in Boyd and Vandenberghe (2004). 2
Next we need to know how we can recognize optima for the dual and primal problems.
If x is primal feasible and (λ, ν) are dual feasible, then we always have
f (x) − f ∗ ≤ f (x) − d(λ, ν)
and the upper bound on the right hand side is known as the duality gap associated with
x and (λ, ν). If this gap is equal to zero, then x is primal optimal and (λ, ν) is dual
optimal. Such pairs of primal-dual optima are characterized by what is known as the
Karush–Kuhn–Tucker conditions (KKT conditions). More precisely:
Theorem A.14. (Karush–Kuhn–Tucker) Consider a convex optimization problem
satisfying Slater’s condition. Then (x∗ , λ∗ , ν ∗ ) is a primal-dual optimal pair with zero
duality gap if and only if x∗ and (λ∗ , ν ∗ ) are feasible and satisfy:
λ∗i gi (x∗ ) = 0 for all i = 1, . . . , k, (A.10)
k
X l
X
0 ∈ ∂f (x∗ ) + λ∗i ∂gi (x∗ ) + νj∗ ∂hj (x∗ ). (A.11)
i=1 j=1
where the last equality holds if and only if (A.10) holds since hj (x∗ ) = 0, λ∗i ≥ 0, and
gi (x∗ ) ≤ 0. Hence the KKT conditions are satisfied if and only if the duality gap
f (x∗ ) − d(λ∗ , ν ∗ ) is equal to zero. 2
118 Some mathematical prerequisites
The conditions (A.10) are referred to as complementary slackness as they express that
at most one of the constraints gi (x) ≤ 0 and λi > 0 is active. The condition (A.11) is
stationarity of the Lagrangian.
The above result is the basis of a class of algorithms used to maximize likelihood
functions. Sections are chosen appropriately such that the partial maximization
problems are relatively simple. A starting value θ0 is found and is iteratively changed
by partial maximization over sections. In all cases the existence, uniqueness and
necessary continuity properties will be established separately, but convergent
algorithms necessarily appear.
120 Some mathematical prerequisites
APPENDIX B
SOME GRAPH THEORY
α β γ β γ α
In most cases our graphs are simple, i.e. there are no multiple edges between endpoints
and they have no loops. For simple graphs we can identify the edge set E with the set
of its endpoints and represent the graph as the ordered pair G = (V, E).
If the graph has only undirected edges it is an undirected graph, if all edges are
directed, the graph is said to be directed, and if all if all edges are bidirected, it is a
bidirected graph.
A graph G 0 with vertex set V 0 and edge set E 0 is a subgraph of a graph G with vertices
V and edges E if V 0 ⊆ V , E 0 ⊆ E, and every edge in E 0 has the same endpoints in G 0
as in G. If A ⊆ V is a subset of the vertex set, it induces a subgraph GA = (A, EA ),
where the edge set EA consists of the edges in E with both endpoints in A. Similarly, a
subset F ⊆ E induces a subgraph GF = (VF , F ), where VF are the endpoints of edges
in F .
A graph is complete if all vertices are adjacent. A subset is complete if it induces a
complete subgraph. A complete subset that is maximal (with respect to inclusion ⊆) is
called a clique.
122 Some graph theory
β β
α δ χ α δ χ
γ φ γ φ
(a) (b)
A path is a walk with no repeated vertex, i.e. a path does not intersect itself. An
n-cycle is a path of length n with the modification that it begins and ends in the same
point, i.e. as (α, e1 , . . . , en , α). If π1 = (α, e1 , . . . , en , β) and
π2 = (β, en+1 , . . . , en+m , γ) are paths, their combination ω12 = π1 ◦ π2 is the walk
ω12 = (α, e1 , . . . , ep , δ, eq , . . . , en+m , γ), where δ is the first node of π1 which is on
both paths and an endpoint of both ep and eq . If δ = β then ω12 is simply the
concatenation (α, e1 , . . . , en+m , γ) of the two paths. In general, the concatenation of
two paths will be a walk and not a path as the paths may intersect in more than one
point.
Two vertices α and β are said to connect in G if there is a walk or, equivalently, a path
from α to β in G in which case we write α β. Clearly, is an equivalence relation
and the corresponding equivalence classes [α] where
β ∈ [α] ⇐⇒ α β
α γ α γ
β δ φ β δ φ
D Dm
B.2.2 Decomposition
In this subsection we study decompositions and decomposable graphs. Since the
notion is fundamental, we state formally
Definition B.1 A triple (A, B, C) of disjoint subsets of the vertex set V of an
undirected, graph G is said to form a decomposition of G if V = A ∪ B ∪ C,
A ⊥G B | C, and C is a complete subset of V .
When this is the case we say that (A, B, C) decomposes G into the components GA∪C
and GB∪C . Note that we allow any of the sets in (A, B, C) to be empty. If the sets A
and B in (A, B, C) are both non-empty, we say that the decomposition is proper. A
graph is said to be prime if no proper decomposition exists. Fig. B.4 shows an example
of a prime graph and an example of a decomposition is shown in Fig. B.5. It holds that
2 4
1 5 7
3 6
any finite undirected graph can be recursively decomposed into its uniquely defined
prime components (Wagner, 1937; Tarjan, 1985; Diestel, 1987; Diestel, 1990), as
illustrated in Fig. B.6.
A decomposable graph is one that can be successively decomposed into its cliques or,
in other words, a graph with only cliques as its prime components. Again we choose to
state this formally through a recursive definition as
Undirected graphs 125
2 4 2 2 4
1 5 7 1 5 5 7
3 6 3 6
2 2 4
2 4
1 5 5 7
1 5 7 5 7
3
3 6 6
both A and B. But, because C separates A from B, such a cycle must intersect C at
least twice. But then it contains a chord because C is complete.
Then (ii) =⇒ (iii). Let C be a minimal (α, β)-separator. If C has only one vertex, it is
complete. If not it contains at least two, γ1 and γ2 , say. Since C is a minimal separator,
there will be paths from α to β via γ1 and back via γ2 . The sequence
(α, . . . , γ1 , . . . , β, . . . , γ2 , . . . , α)
forms a cycle, with the modification that it can have repeated points. These, and chords
other than a link between γ1 and γ2 , can be used to shorten the cycle, still leaving at
least one vertex in the component [α]V \C and one in [β]V \C . This produces a cycle of
length at least 4, which must have a chord. Hence we get γ1 ∼ γ2 . Repeating the
argument for all pairs of vertices in C gives that C is complete.
And finally that (iii) =⇒ (i). Suppose that every minimal (α, β)-separator is
complete. If G is complete there is nothing to show. Else it has at least two
non-adjacent vertices α and β. Let C be a minimal (α, β)-separator and partition the
vertex set into [α]V \C , [β]V \C , C, and the set of remaining vertices D. Then, since C
is complete, the triple (A, B, C), where A = [α]V \C ∪ D, and B = [β]V \C , form a
decomposition of G. But each of the subgraphs GA∪C and GB∪C must be
decomposable. For if C1 is a minimal (α1 , β1 )-separator in GA∪C , it is contained in a
minimal (α1 , β1 )-separator in G which is complete by assumption and C1 is therefore
itself complete. The inductive assumption implies then that GA∪C is decomposable,
and similarly with GB∪C . Thus we have decomposed G into decomposable subgraphs
and the proof is complete. 2
The smallest graph that is not decomposable is therefore a 4-cycle and shown in Fig.
B.7.
1 2
4 3
bd(B) B bd(B) B
(a) (b)
Hj = B 1 ∪ · · · ∪ B j , Rj = Bj \ Hj−1 , Sj = Hj−1 ∩ Bj .
is a perfect sequence of sets. Note that this implies that the sets Bj are all complete.
Perfect sequences and numberings play important roles in the understanding and
manipulation of decomposable graphs, partly because, as we shall see in
Proposition B.10, their existence is a characteristic for decomposable graphs, but also
because they form the basis for recursive computational procedures. Before we show
the characterization results, we need the following lemmas:
Lemma B.6 Let B1 , . . . , Bk be a perfect sequence of sets which contains all cliques
of an undirected graph G. Then for every j, Sj separates Hj−1 \ Sj from Rj in GHj
and hence (Hj−1 , Rj , Sj ) decomposes GHj .
Proof Let p be the highest number such that Bp is a clique. Then Hp = V and hence
Rj = ∅, so the separation is trivial for j > p. Next we must show that Sp separates
Hp−1 \ Sp from Rp in G. But suppose there were an edge between α ∈ Rp and
β ∈ Bj \ Sp for some j < p. Then {α, β} must be subset of some clique of G. But this
128 Some graph theory
cannot be Bp , as β 6∈ Bp and not Bi for some i < p as α 6∈ Hp−1 . Since all cliques are
in the sequence, the edge can therefore not exist and Sp must separate Hp−1 \ Sp from
Rp .
Now B1 , . . . , Bp−1 is a perfect sequence of sets that contains all cliques of GHp−1 . For
Sp ⊆ Bi for some i < p and hence, if Rp = ∅ then Bi = Bp is a clique. If Rp 6= ∅ the
subgraph GHp−1 has one clique fewer. We repeat the argument and continue until the
sequence is reduced to a single set. 2
If a perfect sequence of sets does not contain all cliques, the sets Sj may not separate;
see Fig. B.9.
1 2
4 3
F IG . B.9. A perfect sequence of sets that does not decompose the graph.
Lemma B.7 Let C1 , . . . , Cp be the cliques of G and assume that they form a perfect
sequence. Next let the vertices of G be numbered with first those in C1 , then those in
R2 , R3 and so on. The numbering α1 , . . . , αk so obtained is perfect.
Proof This is immediate. 2
The ‘converse’ to Lemma B.7 is false in the sense that the sequence of cliques induced
by a perfect numbering of the vertices might not be perfect. The induced sequence is
here formed by numbering the cliques according to their highest numbered vertex. A
counterexample is provided in Fig. B.10.
1 2 3 4
F IG . B.10. A perfect vertex numbering that does not induce a perfect clique num-
bering. The numbering of the vertices is perfect, but the cliques, numbered as
({1, 2}, {3, 4}, {2, 3, 5}), do not form a perfect sequence of sets.
Sp = Cp ∩ (C1 ∪ · · · ∪ Cp−1 ) ⊇ Cp ∩ Ct = Ct
Undirected graphs 129
but also that Sp ⊆ Ck for some k < p from the running intersection property. Hence
Ct ⊆ Sp ⊆ Ck .
S ∗ = Cp ∩ Ht−1 ⊆ Sp = Ct ,
S ∗ = (Cp ∩ Ht−1 ) ∩ Ct = St .
For k > p the separators in the new sequence are trivially identical to those in the
original sequence. 2
Perfect sequences of vertices contain all cliques as stated below.
Lemma B.9 Let α1 , . . . , αk be a perfect numbering of the vertices of an undirected
graph G. Then the sets Bj = cl(αj ) ∩ {α1 , . . . , αj } form a perfect sequence that
contains all cliques of G.
Proof The sequence B1 , . . . , Bk is perfect by definition. Bk is necessarily a clique.
An induction argument now gives the result, as α1 , . . . αk−1 is a perfect numbering of
the vertices of GV \{αk } and the cliques of G consist of Bk and those cliques of
GV \{αk } that are not subsets of Bk . 2
We now have a way of constructing a perfect sequence of cliques from a perfect
sequence of vertices by thinning, i.e. simply by using Lemma B.8 to remove redundant
sets from the sequence constructed in Lemma B.9. As a consequence we obtain a
recursive characterization of decomposable graphs:
Proposition B.10 For an undirected, graph G, the following conditions are equivalent
(i) The graph G is decomposable.
(ii) For any α ∈ V , the vertices of G admit a perfect numbering with α1 = α;
(iii) The vertices of G admit a perfect numbering;
(iv) The cliques of G can be numbered to form a perfect sequence;
Proof That (i) implies (ii) is seen by induction on the number of vertices as follows.
If G is decomposable, then by Lemma B.5 G has a simplicial vertex other than α and
130 Some graph theory
we can label this as αk . The induction assumption gives us a perfect numbering of the
remaining k − 1 vertices with α1 = α.
Clearly, (ii) implies (iii).
Also (iii) implies (iv) by using Lemma B.9 and the thinning procedure described in
Lemma B.8. That (iv) implies (i) follows by Lemma B.6 and the definition of
decomposability. 2
A perfect numbering of the vertices of G induces a linear ordering of these and
therefore a directed acyclic version G < of G with arrows pointing from vertices with
low numbers to vertices with high numbers. Since this graph is clearly perfect, G < is
called a perfect directed version of G.
Proposition B.10 implies that an undirected graph is chordal if and only if it has a
perfect directed version. It follows that the skeleton ske(D) of a perfect directed
acyclic graph D is chordal.
The statement (ii) in Proposition B.10 can be strengthened and also perfect sequences
of cliques can be arranged to begin anywhere. More precisely we have the useful
lemma below.
Lemma B.11 Let C ∗ be a clique in a chordal graph G. Then the cliques of G can be
ordered as a perfect sequence C1 , . . . , Ck with C1 = C ∗ .
Proof We use induction on the number of vertices n = |V | of G. For n ≤ 2 the
statement is obvious. Assume then the lemma to hold for all graphs with n ≤ p and let
G have p + 1 vertices. If G is complete the lemma is obviously true. Otherwise, by
Dirac’s Lemma B.5, G has at least two non-adjacent simplicial vertices, i.e. one of
them, say α, is not in C ∗ . This vertex must be a member of exactly one clique Cα . The
cliques of G 0 are the cliques of G except Cα , possibly with Cα \ {α} adjoined. The
inductive assumption implies that the cliques of G 0 = GV \{α} admit a perfect
numbering C1 , . . . , Ck−1 or C1 , . . . , Ck−1 , Ck0 with C1 = C ∗ . Letting Ck = Cα we
obtain a perfect numbering of the cliques of G with the desired property. 2
B.3 Hypergraphs
B.3.1 Basic concepts
A hypergraph is a collection H of subsets of a finite set H, the base set. The elements
of H are called hyperedges. In most cases of interest to us, the base set will be the
union of the hyperedges, i.e. H = ∪h∈H h. This will henceforth be assumed to be the
case, when not otherwise explicitly stated.
A typical hypergraph is a set of complete subsets of a graph G, for example the set of
cliques C(G) of the graph, denoted the clique hypergraph of G. A hypergraph is simple
if it has only one hyperedge. A simple hypergraph is the clique hypergraph of a
complete graph.
If all hyperedges in H are pairwise incomparable in the sense that none is a subset of
the other, we say that H is reduced. The examples above are reduced hypergraphs. The
operation red H produces a reduced hypergraph from H by removing all hyperedges
that are contained in other hyperedges. If we define join and meet operations for two
hypergraphs as
Hypergraphs 131
H1 ∨ H2 = red(H1 ∪ H2 )
H1 ∧ H2 = red{h1 ∩ h2 | h1 ∈ H1 , h2 ∈ H2 },
the class of reduced hypergraphs forms a distributive lattice with the partial order
H1 H2 ⇐⇒ for all h1 ∈ H1 there exists an h2 ∈ H2 with h1 ⊆ h2 .
Two arbitrary hypergraphs are equivalent if their reductions are equal:
(H1 H2 and H1 H2 ) ⇐⇒ red(H1 ) = red(H2 ).
The join H = H1 ∨ H2 of two hypergraphs is said to be direct if their meet is simple,
i.e. if H1 ∧ H2 = {h}. Note that then necesssarily h = H1 ∩ H2 .
B.3.2 Graphs and hypergraphs
As mentioned above, each undirected graph G has an associated clique hypergraph
C(G), but conversely with any hypergraph H we can associate its graph
G(H) = (V, E), where V = H and
(α, β) ∈ E ⇐⇒ {α, β} ⊆ h for some h ∈ H.
Clearly we have
G {C(G)} = G and H C {G(H)} .
If it also holds that H contains the cliques of G(H),
C {G(H)} H,
we say that the hypergraph H is conformal. Then the reduced hypergraph red(H)
consists exactly of the cliques of G(H). It obviously holds that
H1 H2 =⇒ G(H1 ) ⊆ G(H2 )
G1 ⊆ G2 =⇒ C(G1 ) C(G2 ).
Further, one readily verifies from the definitions that
G(H1 ∨ H2 ) = G(H1 ) ∪ G(H2 ) (B.1)
G(H1 ∧ H2 ) = G(H1 ) ∩ G(H2 ) (B.2)
C(G1 ∩ G2 ) = C(G1 ) ∧ C(G2 ), (B.3)
whereas in general
C(G1 ∪ G2 ) C(G1 ) ∨ C(G2 ). (B.4)
In the case of direct joins and decompositions we have
Lemma B.12 If H is the direct join of hypergraphs H1 and H2 , then the triple
(H1 \ H2 , H2 \ H1 , H1 ∩ H2 ) is a decomposition of G(H). If conversely (A, B, C) is
a decomposition of the graph G, then
C(G) = C (GA∪C ∪ GB∪C ) = C (GA∪C ) ∨ C (GB∪C ) (B.5)
and the join is direct.
132 Some graph theory
Consider an arbitrary forest F with the hyperedges H as vertex set and two hyperedges
h1 and h2 which are adjacent in F. If the link between h1 and h2 is removed, then the
tree containing these two hyperedges disconnects. Let H1 be the set of hyperedges that
are still connected to h1 and let H2 denote the set of remaining hyperedges in H. The
key to the relation between decomposability and junction trees and forests is the
following lemma.
Lemma B.15 If F is a junction forest for a reduced hypergraph H then for any
neighbours h1 and h2 in F, H is the direct join of the components H1 and H2 .
Proof Choose two neighbours h1 and h2 in F and define H1 and H2 as above. We
recall that
H1 ∧ H2 = red{a ∩ b | a ∈ H1 , b ∈ H2 }.
Assume first that F is a junction forest for H. For any a ∈ H1 and b ∈ H2 with
a ∩ b 6= ∅, both h1 and h2 are on the unique path between a and b in F. Hence, by the
junction property (B.6),
a ∩ b ⊆ h1 ∩ h2
and hence
H1 ∧ H2 = {h1 ∩ h2 },
whereby H is the direct join of H1 and H2 . 2
Proposition B.16 A reduced hypergraph H is decomposable if and only if there is a
junction forest F for H.
Proof The proof is by induction on the number of hyperedges in H. The statement is
trivial for a simple hypergraph. Assume then that the statement holds for any
hypergraph with at most n hyperedges and let H have n + 1 hyperedges.
First let H be decomposable. Then it is the direct join of reduced hypergraphs H1 and
H2 where both of these have fewer hyperedges. As the join is direct we can choose
h1 ∈ H1 and h2 ∈ H2 such that
H1 ∧ H2 = {h1 ∩ h2 }.
The inductive assumption gives two junction forests F1 and F2 for H1 and H2 . Form
now F from F1 and F2 by taking their union and adding an edge between h1 and h2 if
h1 ∩ h2 6= ∅. We must show that F is a junction forest for H. So let a, b ∈ H. If both
are in H1 or both in H2 and h is on the path between a and b, (B.6) follows from the
fact that F1 and F2 were junction forests. Else we might assume that a ∈ H1 and
b ∈ H2 . Since H is the direct join of H1 and H2 we have
a ∩ b ⊆ h1 ∩ h2 .
on the path between a and b it is either on the path from a to h1 or from b to h2 . In the
former case we find
a ∩ b ⊆ a ∩ h1 ∩ h2 ⊆ a ∩ h1 ⊆ h,
where the junction property of F1 has been used to give the last inclusion. If h is on
the path from b to h2 we argue analogously. Hence the junction property for F is
established.
Assume conversely that F is a junction forest for H. By Lemma B.15, H is the direct
join of hypergraphs H1 and H2 that both have fewer hyperedges. Clearly, the induced
subgraphs F1 = FH1 and F2 = FH2 are junction forests. Hence H1 and H2 are
decomposable by the inductive assumption. As H is the direct join of decomposable
hypergraphs it is itself decomposable. 2
Let now F be a junction forest for the clique hypergraph C of a decomposable graph G
and let S denote the set of intersections of pairs of neighbours in F
S = {Ci ∩ Cj : Ci ∼ Cj }.
Further, let Fi , Fj be the base sets of the components Ci and Cj as in Lemma B.15. We
then have
Corollary B.17 Every set Sij = Ci ∩ Cj separates Fi \ Sij from Fj \ Sij in G and
thus (Fi \ Sij , Fj \ Sij , Sij ) forms a decomposition of G.
Proof Lemma B.15 yields that C is the direct join of Ci and Cj ; the statement now
follows from Lemma B.12. 2
In fact, although there in general are many possible junction forests for C, the set
S = SF of separators in the junction tree does not depend on the particular junction
forest chosen. Also, if we let νF (S) = |{ij ∈ E(F) : S = Ci ∩ Cj }| denote the
number of times S occurs in SF we have:
Proposition B.18 If F and F 0 are two junction forests for C then SF = SF 0 and
νF (S) = νF 0 (S) for all S ⊆ V .
Proof The proof is induction after the cardinality of C. For two cliques this is
obviously true. Let L be a leaf in F with associated separator S ∈ SF . Then
L ∩ C ⊆ S for all C ∈ C− = C \ {F } and hence L is also a leaf in F 0 and S a
separator in SF 0 . Using the inductive assumption on C− with associated junction
forests F− and F− 0
yields the result. 2
Thus it makes sense to say that S is the set of separators of C or of G(C) and
νF (S) = ν(S) are the multiplicities of S.
Corollary B.19 For each S, the multiplicity ν(S) is equal to the number of times S
occurs in any perfect sequence.
Proof This again follows by induction as any leaf of a junction tree can be the last
clique in some perfect sequence. 2
The multiplicities ν(S) satisfy a number of combinatorial identities. More precisely,
we have
Hypergraphs 135
where |F| denotes the number of trees in any junction forest for C.
Proof We use induction on the number |C| of hyperedges. For |C| = 2 this is
obviously true. Let L be a leaf in F with associated separator SL ∈ S. Let
C ∗ = C \ {L}, with base set V ∗ and let S ∗ , and ν ∗ denote the separators and
multiplicities for C ∗ . Using now the inductive assumption we have
X X X
|C| = |L| + |C| = |L| + |V ∗ | + |S|ν ∗ (S).
C∈C C∈C ∗ S∈S ∗
Proof Consider bi for i > 1 and assume this to be part of the tree T in F with chosen
root R. All sets on the path from R to bi must be among b1 , . . . bi−1 or the numbering
would not be compatible. Let b∗ be the hyperedge on this path which is nearest to bi .
Suppose bl for 1 < l < i − 1 is in a different tree. Then bi ⊆ bl = ∅. Else b∗ is on the
path between bl and bi . The junction property thus implies bl ∩ bj ⊆ b∗ and therefore
bi ∩ (b1 ∪ · · · ∪ bi−1 ) ⊆ b∗ ,
which shows that we can choose bj = b∗ and have the running intersection property.
2
In this way there is a simple relation between all possible perfect orderings of the
cliques of a decomposable graph and all junction forests for such graphs.
B.4 Algorithms
B.4.1 Identifying chordal graphs
There are several algorithms for identifying chordal graphs. The most straight-forward
algorithm is a greedy algorithm for checking chordality based on the fact that chordal
graphs are those that admit perfect numberings:
Algorithm B.1 G REEDY ALGORITHM for checking chordality of a graph and identify-
ing a perfect numbering
Input: An undirected graph G.
Output: If V is chordal: a perfect numbering of V ; FALSE if V is not chordal.
1. Look for a vertex v ∗ with bd(v ∗ ) complete
2. If no such vertex exists return FALSE
3. Number v ∗ as v ∗ = |V | and let G = GV \v∗
4. If V 6= ∅ go to 1
5. Else return numbering.
5
t t t t t t
@ @ @ @ 6 @ @ 6
t @t @t t @t @t t @t @t
@ @ @ @ @ @
@t @t @t @t @t @t
7 7 7
F IG . B.11. The greedy algorithm at work. This graph is not chordal, as there is no
candidate for number 4.
5 5
t t t t
@ @ 6 3 @ @ 6
t @t @t t @t @t
@ @ @ @
@t @t @t @t
4 7 4 7
5 1 5
t t t t
3 @ 2 @ 6 3 @ 2 @ 6
t @t @t t @t @t
@ @ @ @
@t @t @t @t
4 7 4 7
* 1
s s s s
@ * @ *
s @s @s s @s @s
@ @
@s @s @s @s
@ @ @ @
2 1 2 1
s s s s
* @ ** @ * * @ 3 @ **
s @s @s s @s @s
@s @s @s @s
@ @ @ @
* *
2 1 2 1
s s s s
* @ 3 @ 4 * @ 3 @ 4
s @s @s s @s @s
@s @s @s @s
@ @ @ @
* ** * 5
2 1 2 1
s s s s
6 @ 3 @ 4 6 @ 3 @ 4
s @s @s s @s @s
@s @s @s @s
@ @ @ @
** 5 7 5
Bλ = bd(λ) ∩ {1, . . . , λ − 1}
and πλ = |Bλ |. Say that λ is a ladder vertex if λ = |V | or if πλ+1 < πλ + 1 and let Λ
be the set of ladder vertices.
It then holds that the cliques of G are Cλ = {λ} ∪ Bλ , λ ∈ Λ. For a proof of this
assertion see e.g. Cowell et al. (1999, page 56).
Example B.25 For the MCS ordering in Fig. B.14 we find πλ = (0, 1, 2, 2, 2, 1, 1)
yielding the ladder nodes {3, 4, 5, 6, 7} and the corresponding cliques
C = {{1, 2, 3}, {1, 3, 4}, {3, 4, 5}, {2, 6}, {6, 7}}.
A junction tree can be constructed directly from the MCS ordering Cλ , λ ∈ Λ. More
precisely, since
Bλ = bd(λ) ∩ {1, . . . , λ − 1}
Algorithms 139
2 1
t t
6 @ 3 @ 4
t @t @t
@ @
@t @t
7 5
F IG . B.14. MCS numbering for a chordal graph. The algorithm runs essentially as in
the non-chordal case.
is complete for all λ ∈ Λ it holds that
for some λ∗ < λ. A junction tree is now easily constructed by attaching Cλ to any Cλ∗
satisfying the above. Although λ∗ may not be uniquely determined, Sλ is. Indeed, the
sets Sλ are the minimal complete separators and the numbers ν(S) are
ν(S) = |{λ ∈ Λ : Sλ = S}|. Junction trees can be constructed in many other ways as
well (Jensen and Jensen, 1994).
The inverse on the left-hand side exists if and only if the inverses on the right-hand
side exist. Here F = D−1 C, and G = BD−1 . Performing the multiplication shows the
correctness. Finally, we shall make use of the following formula — known as
Harville’s variant of the Woodbury matrix identity — valid for a non-singular
symmetric matrix M of order m, a symmetric matrix ∆ of order d, and C being any
m × d matrix:
This formula is useful when M has previously been inverted and d is much smaller
than m. To see that (C.3) is correct, we let Q = (I + C > M −1 C∆) and multiply the
right-hand side with (M + C∆C > ) from the left to get
We write VX = Σ. Note that the covariance, as well as any other bilinear form, is
determined from its values on the diagonal Σ(u, u), for the bilinearity gives
1
Σ(u, v) = {Σ(u + v, u + v) − Σ(u − v, u − v)} .
4
To any such bilinear form there is a linear operator, which we also denote by Σ, such
that
Σ(u, v) = hu, Σvi.
This is referred to as the covariance operator of X. If (e1 , . . . , ep ) is an orthonormal
basis of V , we let
The p × p-matrix of these numbers is the covariance matrix of X and we also denote
this by VX = Σ. So the same symbol is used to refer to the covariance, the covariance
operator and the covariance matrix, and the context will determine the exact meaning
of the symbol.
The covariance Σ is called regular if Σ(u, u) > 0 for all u 6= 0. In this case its matrix
is positive definite and the covariance determines an inner product on V which we
shall denote as h·, ·iΣ , i.e.
When the covariance is regular, the inverse operator K = Σ−1 is called the
concentration operator and its matrix with respect to a chosen basis is called the
concentration matrix. The concentration operator determines a symmetric bilinear
form as usual by
K(u, v) = hu, Kvi.
This bilinear form is called the concentration of the distribution.
The concentration operator K is equivalently defined through the relation
Note that the concentration and the covariance operator depend on the given inner
product on V , and the covariance and concentration matrices further depend on a
chosen orthonormal basis. A fully invariant approach to random vectors and the
normal distribution on vector spaces avoids introducing the first inner product, but we
have chosen not to proceed to this level of abstraction.
144 Linear algebra and random vectors
In most cases the space V will be Rn with the usual inner product and standard
orthonormal basis, but we also frequently deal with the space Rn×p of n × p-matrices
with inner product
hA, Bi = tr(A> B) (C.5)
and canonical basis formed by the matrices Eij with ij-th entry equal to one and the
remaining entries equal to zero. In the case where n = p, an interesting subspace is
formed by the set Sp of symmetric p × p matrices where the transpose in (C.5)
becomes unnecessary. An orthonormal basis for this space consists of the symmetric
matrices √
Ẽii = Eii , Ẽij = (Eij + Eji ) / 2 for i 6= j. (C.6)
If V = Rn , the mean vector is of the form ξ = (ξ1 , . . . , ξn )> and we have
These formulae indicate how the notation conforms with that used in most statistical
literature.
Suppose we have two Euclidean spaces V and W where to avoid confusion we denote
their inner products by h·, ·iV and h·, ·iW respectively. Let A be a linear map from V to
W and b an element of W . Then Y = AX + b is a random vector in W . Its mean and
covariance are given below.
Proposition C.4 If the random vector X has mean ξ and covariance Σ, then the mean
and covariance operator of Y are
EY = Aξ + b, VY = AΣA> .
In the special case of V = Rn and W = Rm , the same expressions hold for matrices.
Proof Direct calculation gives
which gives the covariance operator. We abstain from repeating the calculations in the
matrix case. 2
Random vectors 145
ψ(v) = Eeihv,Xi ,
determines the distribution. Here i is the complex unit, i.e. i2 = −1. This result can be
found in Cramér (1946). That this is equivalent to the statement in Proposition C.5
follows from the uniqueness of the Fourier transform in the case where V = R.
146 Linear algebra and random vectors
APPENDIX D
THE MULTIVARIATE NORMAL DISTRIBUTION
The exposition of the multivariate normal distribution and derived distributions is close
to that given in Eaton (1983). Proofs not given here can be found there or in Anderson
(1984).
Adding two independent normal random vectors gives a normal random vector. More
accurately:
Proposition D.2 If X1 ∼ NV (ξ1 , Σ1 ) and X2 ∼ NV (ξ2 , Σ2 ) are independent, then
X1 + X2 ∼ NV (ξ1 + ξ2 , Σ1 + Σ2 ).
Proof For v ∈ V it holds that
hv, X1 + X2 i = hv, X1 i + hv, X2 i.
The terms on the right-hand side are independent and univariate normal. Hence the sum
is univariate normal. Definition D.1 implies that X1 + X2 is a normal random vector
and the expressions for mean and covariance follow by direct calculation. 2
Another important fact about the normal distribution is that an affine transformation of
a normal random vector is itself a normal random vector. We consider a situation
analogous to that in Proposition C.4.
Proposition D.3 If A is a linear map from V to W , b an element of W , and
X ∼ NV (ξ, Σ), then
Y = AX + b ∼ NW (Aξ + b, AΣA> ).
Proof The mean and covariance of Y have been given in Proposition C.4. What
remains to be established is that Y follows a normal distribution. But for all w ∈ W
we have
hw, Y iW = hw, AX + biW = hA> w, XiV + hw, biW .
Since X has a normal distribution, hA> w, XiV is univariate normally distributed. This
is not changed by adding the constant hw, biW . Definition D.1 then establishes the
result. 2
A special case of this result is of interest. Suppose V = Rn and assume the random
vector X partitioned into components X1 and X2 , where X1 ∈ Rp and X2 ∈ Rq with
p + q = n. The mean vector and covariance matrix can then be partitioned accordingly
into blocks as ! !
ξ1 Σ11 Σ12
ξ= and Σ =
ξ2 Σ21 Σ22
such that Σ11 has dimensions p × p and so on. If A in Proposition D.3 is the linear map
that sends X into X2 , we obtain:
Proposition D.4 Let X be distributed as Nn (ξ, Σ), where X, ξ and Σ are partitioned
as above. Then the marginal distribution of X2 is Nq (ξ2 , Σ22 ).
Proposition D.5 Let X be distributed as Nn (ξ, Σ), where X, ξ and Σ are partitioned
as above. Then X1 and X2 are independent if and only if Σ12 = 0. If Σ is regular, this
holds if and only if K12 = 0.
Proof The first statement follows directly from the expression for the conditional
mean ξ1|2 in Example 1.20. The second statement then follows from (1.6). 2
REFERENCES
density lasso
recursive, 68 graphical, 104
recursive, 67 line, 121
faithful, 59
Fisherian model, 15 Möbius inversion, 63, 113
forest, 123 Markov equivalence, 69
junction, 132 Markov kernel, 1
Fubini’s theorem, 112 combination, 46
Fubini, extended, 8 Markov property
directed
Gaussian graphical model, 100 global, 65
generalized inverse, 143 local, 65
generating system for σ-algebra, 111 ordered, 64
graph, 121 global, 59
bidirected, 121 undirected, 100
chordal, 125 decomposition, 63
complete, 121 factorization, 61, 62
decomposable, 124 global, 60
directed, 121 local, 60
moral, 123 pairwise, 60, 62
rigid circuit, 125 positive, 62
simple, 121 mean, 142
triangulated, 125 mixture, 4
undirected, 121
graphical lasso, 104 neighbour, 122
graphoid, 52 node, 121
compositional, 52 non-descendant, 123
normal distribution, 147
history, 127 concentration, 147
hyperedge, 130 conditional independence, 97
hypergraph, 130 covariance, 147
clique, 130 density, 147
conformal, 131 marginal, 148
decomposable, 132
reduced, 130 optimization
simple, 130 convex, 114
ordering
independence model, 52 topological, 64
integration
of Markov kernel, 3 parent, 122
uniqueness, 5 partial correlation coefficient, 98
integration, the, 3 partial regression coefficient, 99
interaction, 99 path, 123
IPS-algorithm, 101 perfect, 69
iterative partial maximization, 103, 118 DAG, 123
iterative proportional scaling directed version, 130
covariance selection model, 101 numbering, 127
sequence, 127
join potential, 81
direct, 131 predecessor, 64
junction
forest, 132 residual, 127
property, 132 running intersection property, 127, 135
tree, 132
saturated model
Lagrangian, 116 Gaussian, 96
Index 155