Graphical Markov Models Lectures

PhD Program in Statistics

Author

Affiliation

Giovanni M. Marchetti

DISIA, University of Florence

Published

April 20, 2026

1 Probability and Independence

1.1 Basic ideas

Graphical Markov Models discuss a particular structure of multivariate distributions based on independencies among a set of variables. The independence structure is not as straightforward as it might seem at first glance, especially when considering marginal and conditional independencies.

Graphical models define precisely what is the independence structure of a multivariate model using graphs where the nodes are the variables and the edges (lines or arrows) present or missing define the associations or the independencies.
These notes are partly based on Cox and Wermuth (1996), Evans (2025), Højsgaard et al. (2012) and Whittaker (1990).
This chapter starts with a discussion of conditioning and marginalizing in multivariate distributions with examples from two classical distributions like the Gaussian and the Multinomial.
As usual we start from a vector of random variables denoted by X_V = (X_1, X_2, \dots, X_d)^T representing a multivariate population with d components. The suffix V indicates just the set V = \{1, 2,\dots, d\}.
To simplify the notation we often omit the subscript V by writing X instead of X_V. Also we use the simpler notation for the variables like X, Y, Z and so on.
We will assume that the population can be either multivariate Gaussian or Bernoulli and that we observe an i.i.d. sample X_V^{(i)} \equiv (X^{(1)}, \dots, X^{(n)})^T.

1.2 Marginal and conditional densities

Distribuzioni marginali

Given two variables (X, Y) the marginal density of X is defined by p(x) = \begin{cases} \int_{\mathcal{X}} p(x, y) dy & \text{continuous case}\\ \sum_{x \in \mathcal{X}} p(x,y) & \text{discrete case}. \end{cases}
Remember that marginalizing implies considering a set of variables, but ignoring the others. For instance, by observing a single variable in a population means including implicitly all the other possible features.

This concept is essential when in a specific study there are some variables that can be observed and other variables that are unobserved.

Distribuzioni condizionate

Invece, a differenza della marginalizzazione, l’operazione di condizionamento consente di capire come si trasforma la distribuzione data se si seleziona una sotto-popolazione.
A conditional density of X given Y is defined by any function p(x|y) such that p(x,y) = p(y) \cdot p(x|y) The conditional density p(x|y) is undefined if p(y) = 0. If p(y) >0 we get the usual definition p(x|y) = \frac{p(x,y)}{p(y)}.

We use a simple but imprecise notation for p(y) and p(x|y) instead of p_Y(y) and p_{X|Y}(x|y).

Notation

The marginal and conditional distributions are denoted using a subset notation instead of the whole variables.
With (X_1, X_2, X_3) the marginal density of (X_1, X_3) is denoted by

p(x_1, x_3)\quad \text{ or } \quad p(x_a) \text{ where } a = \{1,3\}. In this case it is common to say: we marginalize over X_2.
The density of X_2 \mid (X_1, X_3) is denoted by

p(x_2\mid x_1, x_3)\quad \text{ or } \quad p(x_b | x_a) \text{ where } a = \{1, 3\} \text{ and } b = \{2\}.

In this case it is common to say: we condition on (X_1, X_3).

Example with Gaussian distributions

A d\times 1 random vector X\in \mathbb{R}^d has a multivariate Gaussian distribution N(0, \Sigma) with mean zero and covariance matrix \Sigma if it has a density p(x) = \frac{1}{(2\pi)^{d/2} |\Sigma|^{1/2}} \exp\Big \{ - \textstyle\frac{1}{2} x^T\Sigma^{-1}x\Big \} with a support \mathbb{R}^d. The general Gaussian Y \sim N(\mu, \Sigma) with mean \mu is obtained by the transformation Y = \mu + X.
The Gaussian distributions satisfy two important properties.
1. The marginal distribution of any subset X_a of the random vector X is Gaussian
2. The conditional distribution of any subset X_b given a disjoint subset X_a of X is Gaussian.
This implies that the family of multivariate Gaussian distributions is closed under marginalization and conditioning.
Specifically, assume that X has 5 components with a = \{1, 2\} and b = \{3, 4, 5\}.

Then, by marginalizing X = (X_a, X_b) over X_b we get X_a \sim N(\mu_a, \Sigma_{aa}) where \mu_a = \begin{pmatrix} \mu_1 \\ \mu_2 \end{pmatrix}, \quad \Sigma_{aa} = \begin{pmatrix} \sigma_{11} & \cdot \\ \sigma_{21} & \sigma_{22} \end{pmatrix}

By conditioning X_b on X_a we get X_{b} \mid X_a \sim N(\mu_{b|a}, \Sigma_{bb|a}) where \begin{align*} \mu_{b|a} &= \mu_b + B(X_a -\mu_a), \text{ with } B = \Sigma_{ba}\Sigma_{aa}^{-1} \\ \Sigma_{bb|a} &= \Sigma_{bb} - \Sigma_{ba}\Sigma_{aa}^{-1}\Sigma_{ab} \end{align*}

Therefore the conditional expectation E(X_b \mid X_a) is a linear function of X_a and the conditional covariance matrix does not depend on X_a.

1.3 Types of independence

Now we start to discuss the structure of independencies in a multivariate distribution by making a distinction between marginal and conditional independencies.

Marginal independence

Two random variables X and Y wth supports \mathcal{X} and \mathcal{Y} are said marginally independent, denoted by X \;\perp \hspace{-2.2ex}\perp\;Y, if

p(x, y) = p(x) p(y)

for all (x, y) \in \mathcal{X} \times \mathcal{Y}. Remember that the last condition is essential.

Exercise Let (X,Y) be a random vector with uniform density on the support \{(x,y) : -1 \le x \le 1,\; 0 \le y \le 1 - x^2\}. Are X and Y independent?

Conditional independence

Suppose that X,Y are two random variables defined on a product space \mathcal{X} \times \mathcal{Y}, and that there is a third random variable Z so that the distribution is p(x, y, z).

Then X and Y are said conditionally independent given Z if p (x| y, z) = p(x|z) for all (x, y, z) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z} such that p(y, z) > 0.
The interpretation is that if we study the conditional distribution of X given Y and Z, the variable Y is irrelevant when we condition on Z.

Basic theorem

Let X, Y, Z be random variables on a Cartesian product space \mathcal{X} \times \mathcal{Y} \times \mathcal{Z}. Then the following are equivalent.

\begin{align*} 1.\; & p(x | y, z) = p(x | z) \text{for all } x, y, z \text{ such that } p(y, z) > 0\\ 2.\; & p(x, y | z) = p(x | z) \cdot p(y | z) \text{ for all } x, y, z \text{ such that } p(z) > 0\\ 3.\; & p(x, y, z) = p(y, z) \cdot p(x | z) \text{ for all } x, y, z \\ 4.\; & p(z) \cdot p(x, y, z) = p(x, z) \cdot p(y, z) \text{ for all } x, y, z \\ 5.\; & p(x, y, z) = f(x, z) \cdot g(y, z) \text{ for some functions } f, g \text{ and all } x, y, z. \end{align*}

1.4 Properties of conditional independence

Conditional independence satisfies the following implications called semigraphoid properties:

X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z \implies Y \;\perp \hspace{-2.2ex}\perp\;X \mid Z (symmetry)
X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \mid Z \implies X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z (decomposition)
X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \mid Z \implies X \;\perp \hspace{-2.2ex}\perp\;W \mid (Y,Z) (weak union)
X \;\perp \hspace{-2.2ex}\perp\;W \mid (Y,Z) \; \& \; X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z \implies X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \mid Z (contraction)

The essential property

Note that the converse to (4. contraction) follows from (2. decomposition) and (3. weak union). Thus we can combine the two properties as the rule X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \mid Z \iff X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z \;\&\; X \;\perp \hspace{-2.2ex}\perp\;W \mid (Y,Z)

Thus, the semigraphoid properties reduce to the above property plus the symmetry property.

Intersection property

There is an additional property called intersection (that is the reverse of weak union)

If p(x,y,z,w) > 0 then $X W (Y,Z) ; ;&; XY (W,Z) X (Y,W) Z.

The intersection property however doesn’t generally hold if the distribution is not positive.

The rules from 1. to 5. define the so called graphoid properties.

Examples of independence for binary data

Marginal independence

Let X_1, X_2 be a binary random variables with joint probabilities \pi_{ij}>0. When X_1 \;\perp \hspace{-2.2ex}\perp\;X_2? The answer is if \pi_{ij} = \pi_{i+}\pi_{+j}, \quad \text{ for all } (i,j) \in \mathcal{I}_2. Equivalently, X_1\;\perp \hspace{-2.2ex}\perp\;X_2 \iff \pi_{00}\pi_{11} - \pi_{01}\pi_{10} = 0 \iff \text{OR} = \frac{\pi_{00}\pi_{11}}{\pi_{01}\pi_{10}} = 1. The OR, called odds-ratio (or cross product ratio), is an association measure for binary variables, taking values > 0.

Conditional independence

Consider now three binary variables X_1, X_2, X_3 with joint probabilities \pi_{ijk}>0. The probabilities can be stored in a 2\times 2\times 2 table. The conditional independence requires that for each k = 0,1 the conditional odds-ratio of the tables (X_1, X_2) \mid X_3 = k are all equal to 1. Formally

X_{1} \;\perp \hspace{-2.2ex}\perp\;X_{2} \mid X_3 \iff \frac{\pi_{00k}\pi_{11k}}{\pi_{01k}\pi_{10k}} = 1, \quad \text{ for all } k = 0,1.

Marginal independence does not imply a conditional independence

X_1 and X_2 are not independent conditionally on X_3 (divide the counts by 100) \begin{array}{cc|cc|cc} & X_3 & 0 & 0 & 1 & 1 \\ X_1 & X_2 & 0 & 1 & 0 & 1 \\ \hline 0 & & 37 & 8 & 9 & 38 \\ 1 & & 3 & 2 & 1 & 2 \\ \hline & & \text{OR}= 3.08 & &\text{OR}= 0.47 & \\ \end{array}

But X_1 and X_2 are independent if we marginalize over X_3 \begin{array}{cc|cc} X_1& X_2& 0 & 1\\ \hline 0 & & 46 & 46 \\ 1 & & 4 & 4\\\hline & &\text{OR}= 1 & \\ \end{array} > Notice that the conditional association are positive and negative.

Conditional independence and marginal independence

X_1 and X_2 are independent conditionally on X_3 (divide the counts by 1000)

\begin{array}{cc|cc|cc} & X_3 & 0 & 0 & 1 & 1 \\ X_1 & X_2 & 0 & 1 & 0 & 1 \\ \hline 0 & & 384 & 96 & 40 & 360 \\ 1 & & 16 & 4 & 10 & 90 \\ \hline & & \text{odr}= 1 & &\text{odr}= 1 & \\ \end{array}

But X_1 and X_2 are dependent if we ignore X_3 \begin{array}{cc|cc} X_1& X_2& 0 & 1\\ \hline 0 & & 424 & 456 \\ 1 & & 26 & 94\\\hline & &\text{odr}= 3.36 & \\ \end{array}

1.5 Computational advantages of conditional independence

Consider X, Y and Z on a product space with joint density p_\theta(x,y,z) = g_\tau(x,y) h_\xi(y, z) for some functions g_\tau(), h_\xi() with \theta = (\tau, \xi) variation independent.
Then, to find the MLE of \theta we can maximize separately the factors \max_{\tau} \prod_{i= 1}^n g_\tau(x_i, y_i), \qquad \max_\xi \prod_{i=1}^n h_\xi(y_i, z_i), by considering the two marginal distribution of (X,Y) and (Y, Z).

Computations

Even moderatedly sized contingency table will cause statistical problems due to the curse of dimensionality.
If we have d binary variables the contingency table has 2^d cells. For example with d = 15 we have 32768 cells, most of them probably empty unless you have a quite large number of individuals.
But conditional independence can help: if we have the independence X_A \;\perp \hspace{-2.2ex}\perp\;X_B \mid X_C, with V = A\cup B \cup C this implies that

p(x_V) = p(x_C) \cdot p(x_A \mid x_C) \cdot p(x_B\mid x_C)

and we can store each factor in computer memory separately wich means

2^{|A|} + 2^{|A|+|C|} + 2^{|B|+|C|} = 2^{|C|} (1 + 2^{|A|} + 2^{|B|})\quad \text{cells}

that represent a considerable saving with respect to 2^{|A|+|B| + |C|}.

If d = 15 with A = 5, |C| = 2 and |B| = 8, the total number of cells is 4 ( 1 + 32 + 256) = 1156. instead of 32768.

1.6 Multivariate Bernoulli

When the variables X_V = (X_1, \dots, X_d)^T are all binary with levels \{0,1\} the joint distribution is called a multivariate Bernoulli with probabilities p(x_V) = \Pr(X_1 = x_1, \dots, X_d = x_d), \quad x \in \mathcal{I} = \{0,1\}^d with p(x) >0 and \sum_{x \in \mathcal{I}} p(x) = 1.

The parameters are \pi = (p_V(x), x \in \mathcal{I}), a (2^d\times 1) vector taking value in a simplex of dimension (2^d-1).

For example for d = 3 a multivariate Bernoulli is

\begin{array}{cccc} 1 & 2 & 3 & \pi \\ \hline 0 & 0 & 0 & 0.38 \\ 1 & 0 & 0 & 0.01 \\ 0 & 1 & 0 & 0.07 \\ 1 & 1 & 0 & 0.01 \\ 0 & 0 & 1 & 0.42 \\ 1 & 0 & 1 & 0.02 \\ 0 & 1 & 1 & 0.08 \\ 1 & 1 & 1 & 0.01 \\ \hline \end{array}

where \pi is a 2^3-vector of the joint probabilities p(x_1, x_2, x_3).

An i.i.d sample of size n = 100 from this Bernoulli is obtained using random sample from a Multinomial with size 1 and probabilities \pi.

R code

set.seed(111)
n <- 100
p <- c(0.38, 0.01, 0.07, 0.01,
       0.42, 0.02, 0.08, 0.01)
X <- expand.grid(X1 = factor(0:1),
                 X2 = factor(0:1),
                 X3 = factor(0:1))
Z <- rmultinom(n, size = 1, prob = p)
cell <- apply(Z, 2, function(x) which(x==1))
data <- X[cell,]
rownames(data) <- 1:n

The result is an n \times 3 binary matrix. The first rows are shown below:

head(data)

When the data frame is cross-tabulated we obtain the frequencies that are the number of units who have a specific response pattern. Here it is:

df<- as.data.frame(table(data))
df

  X1 X2 X3 Freq
1  0  0  0   43
2  1  0  0    2
3  0  1  0    9
4  1  1  0    1
5  0  0  1   38
6  1  0  1    1
7  0  1  1    6
8  1  1  1    0

In this case the vector of counts has a multinomial distribution with index n and probability vector \pi.
Notice that some combinations of levels can have frequency zero if the sample size is small.

Log-linear parameterization

The vector of the probabilities \pi > 0 is written in a lexicographical order.
The 2^d parameters \pi must satisfy the constraint \sum \pi_i = 1 and its parameter space is a simplex of dimension 2^d -1.

Reparametrization

There is a 1-1 map from \pi to a parameter \lambda that can vary in a real space of dimension 2^{d}-1.
I show first the map for two variables.
- Define a matrix with a Kronecker product L = \begin{pmatrix*}[r] 1 & 0\\ -1 & 1 \\ \end{pmatrix*} \otimes \begin{pmatrix*}[r] 1 & 0\\ -1 & 1 \\ \end{pmatrix*} = \begin{pmatrix*}[r] 1 & 0 & 0 & 0\\ -1 & 1 & 0 & 0\\ -1 & 0 & 1 & 0\\ 1 & -1 & -1 & 1\\ \end{pmatrix*}
- Define \lambda = L \log \pi as the log-linear parameters.
- The 3 components of \lambda excluding the first are variation independent.
Inversely, we get the probabilities from \lambda with \pi = \exp(G \lambda) where G = L^{-1} that is G = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}

R example

Let (X_1, X_2) two binary variables. If \lambda = (0, 1/2, -1/4, 1/10) the joint distribution is as follows.

lambda <- c(0, 1/2, -1/4, 1/10)
g <- matrix(c(1, 0,
              1, 1), byrow = TRUE, 2, 2)
G <- g %x% g
p <- exp(G %*% lambda) 
p <- p/sum(p)
p

          [,1]
[1,] 0.2063307
[2,] 0.3401817
[3,] 0.1606905
[4,] 0.2927971

Log-linear parameters

The joint probability distribution can be written as p(x_1, x_2) = \exp\{\lambda_0 + \lambda_1 x_1 + \lambda_2 x_2 + \lambda_{12}x_1 x_2\} where \lambda_0 is function of the other variation independent parameters
The components of \lambda are denoted (\lambda_0, \lambda_1, \lambda_2, \lambda_{12})^T corresponding to the all the subsets of the variables in the same lexicographic order of \pi.
In general the log-linear parameters for p(x_V)>0 are defined by the relation p(x_V) = \exp\Big(\sum_{A\subseteq V} \lambda_A x_A\Big) or in matrix form \pi = \exp(G\lambda) where G equals the Kronecker product of d matrices \begin{pmatrix} 1 & 0\\ 1 & 1 \end{pmatrix}.

Conditional independence in log-linear models

When the log-linear parametrization defines a conditional independence X_2 \;\perp \hspace{-2.2ex}\perp\;X_3 \mid X_1?
The joint distribution for a binary r.v. (X_1, X_2, X_3) is p(x_1, x_2, x_3) = \exp(\lambda_0 + \lambda_1 x_1 + \lambda_2 x_2 + \lambda_{12}x_1 x_2 + \lambda_3 x_3 + \lambda_{13}x_1 x_3 + \lambda_{23}x_2 x_3 + \lambda_{123}x_1 x_2 x_3)

Proposition: p>0 satisfies X_2 \;\perp \hspace{-2.2ex}\perp\;X_3 \mid X_1 if and only if \lambda_{23} = \lambda_{123}= 0.

Proof \begin{align*} p(x_1, x_2 x_3) &= \exp(\lambda_0 + \lambda_1 x_1 + \lambda_2 x_2 + \lambda_{12}x_1 x_2 + \lambda_3 x_3 + \lambda_{13}x_1 x_3 ) \\ &=\exp(\lambda_0 + \lambda_{1}x_1 + \lambda_2 x_2 + \lambda_{12}x_1 x_2) \cdot \exp(\lambda_3 x_3 + \lambda_{13}x_1 x_3) \end{align*} so that p(x_1, x_2, x_3) = \psi_{12}(x_1, x_2) \cdot \psi_{13}(x_1, x_3).

In general, we have this theorem.

Theorem: If p >0 is distribution for d binary variables, with associated parameters \lambda_C for C\subseteq V then the conditional independence X_i \;\perp \hspace{-2.2ex}\perp\;X_j \mid X_{V \setminus \{i,j\}} holds if an only if \lambda_{ij} = 0 \qquad \text{for all } \{i,j\} \subseteq C \subseteq V.

Proof. See Evans (2025).

1.7 Multivariate Gaussian

Marginal independence for the Gaussian

It is well-known that in a Gaussian distribution X \sim N(\mu, \Sigma) two variables X_i and X_j are independent if and only if \sigma_{ij} = 0.
This rule can be extended to a random vector X = (X_a, X_b, X_c) where a and b and c define a partition of V.

The covariance matrix has a block structure \Sigma = \begin{pmatrix} \Sigma_{aa} & \cdot & \cdot\\ \Sigma_{ba} & \Sigma_{bb} & \cdot \\ \Sigma_{ca} & \Sigma_{cb} & \Sigma_{cc} \end{pmatrix} where the dot means a block that is symmetric.

Proposition. X_a \;\perp \hspace{-2.2ex}\perp\;X_b \iff \Sigma_{ab} = \Sigma_{ba} = 0.

The proof is based on the decomposition of the quadratic form in the exponent of the density of the marginal p(x_a, x_b) x_a^T \Sigma_{aa}^{-1}x_a + x_b^T \Sigma_{bb}^{-1}x_b.

Conditional independence for the Gaussian

Assume X \sim N(0, \Sigma). An important reparametrization for the Gaussian is the inverse of the covariance matrix \Sigma that is called the concentration matrix K = \Sigma^{-1} = \begin{pmatrix} \kappa_{11} & \cdot & \cdots & \cdot \\ \kappa_{21} & \kappa_{22} & & \cdot \\ \vdots & \vdots & & \vdots \\ \kappa_{d1} & \kappa_{d2} & \cdots & \kappa_{dd} \end{pmatrix}.
Often we partition of the variables in two sets X_a and X_b. Then the covariance and the concentration matrix can be written as \Sigma= \begin{pmatrix} \Sigma_{aa} & \cdot \\ \Sigma_{ba} & \Sigma_{bb} \end{pmatrix}, K = \begin{pmatrix} K_{aa} & \cdot \\ K_{ba} & K_{bb} \end{pmatrix}
The conditional distribution of X_b \mid X_a is Gaussian with mean \mu_{b|a} = BX_a with B = \Sigma_{ba}\Sigma_{aa}^{-1} and covariance matrix \Sigma_{aa|b} = \Sigma_{aa} - \Sigma_{ab}\Sigma_{bb}^{-1}\Sigma_{ba}.
Using the formula of the block inverse of \Sigma we find that
- B = - K_{bb}^{-1}K_{ba}
- \Sigma_{bb|a} = K_{bb}^{-1}
In other words the conditional covariance matrix \Sigma_{bb|a} is equal to the inverse of the block K_{bb} of the concentration matrix.

A special case happens if a = \{1,\dots, d-1\} and b = \{d\}:
- \beta_{j} = \displaystyle -\frac{\kappa_{jd}}{\kappa_{dd}}
- \sigma_{dd|a} = \displaystyle \frac{1}{\kappa_{dd}}
Specifically, if an element of the concentration matrix \kappa_{rs} = 0 then X_r and X_s are uncorrelated (and thus independent) after conditioning on all the other variables.

Proposition. If X_V \sim N(\mu, \Sigma) with concentration matrix K,

X_r \;\perp \hspace{-2.2ex}\perp\;X_s \mid X_{V \setminus{i,j}} \iff \kappa_{rs}= 0.

Appendix: composition property for Gaussian variables

We have seen that in general from the decomposition property
X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \implies X \;\perp \hspace{-2.2ex}\perp\;Y \text{ and } X \;\perp \hspace{-2.2ex}\perp\;W. Gaussian distributions satisfy also the reverse implication so that the following equivalence holds X \;\perp \hspace{-2.2ex}\perp\;(Y,W) \iff X \;\perp \hspace{-2.2ex}\perp\;Y \text{ and } X \;\perp \hspace{-2.2ex}\perp\;W called the composition property. Notice that this property is not shared by discrete distributions.

Example: You can verify that the two marginal tables (X_1, X_2) and (X_1, X_3) are uniform, implying the two independencies X_1\;\perp \hspace{-2.2ex}\perp\;X_3 and X_2 \;\perp \hspace{-2.2ex}\perp\;X_3. However surprisingly the joint independence X_1 \;\perp \hspace{-2.2ex}\perp\;(X_2, X_3) does not hold. \begin{array}{ccccccc} \hline &X_3 &0 & 0 & 1 & 1 & \\ X_1 & X_2 & 0 & 1 & 0 & 1 & \text{sum} \\ \hline 0 & & 0.20 & 0.05 & 0.05 & 0.20 & 0.5 \\ 1 & & 0.15 & 0.10 & 0.10 & 0.15 & 0.5 \\ \hline \text{sum} & & 0.35 & 0.15 & 0.15 & 0.35 & 1.0 \\ \end{array}

2 Graphs and Markov properties

2.1 Introduction

One of the central notions of statistical thinking is the distinction between the association of two variables, regarded as an undirected dependence of two features of equal standing, and a directed dependence in which one variable is a response and the other an explanatory variable. – David Cox and Nanny Wermuth.

Undirected dependence: Systolic blood pressure, Diastolic blood pressure
Directed dependence: The distinction between responses and explanatory variables is determined by the time. Features at later time points are possible responses to features at earlier time points.
Often the direction may be given by a provisional working hypothesis
However, the central idea of graphical models is that of independence.

Representation by graphs

To represent both concepts we introduce graphs where
- the variables are the nodes
- the edges indicate kind undirected or directed dependence.
- The missing edges and the separation between groups of nodes reflects a specific independence.
The edges joining nodes u, v can be of different types: directed u \longrightarrow v, undirected u -\!\!\!- v or bidirected u \longleftrightarrow v.

Types of independence graphs

There are three types of simple graphs with edges of the same type (and without multiple edges or self-loops).
Directed graphs
Undirected graphs
Bidirected graphs

Next we discuss mixed graphs with edges of different types. For example:

The interpretation of each graph requires a specific rule for identifying the independencies implied from the graph. These set of rules is called a Markov property.

2.2 Directed acyclic graphs

Here are 3 directed graphs.

The above 3 graphs are directed, but we will focus primarily on graphs that do not contain directed cycles. The directed graphs without cycles like the second and the third are called directed acyclic graphs (DAG).

Definitions for DAGs

A directed acyclic graph \mathcal{G} is a pair (V, E) where

V is the finite set of d nodes
E is a collection of edges that are ordered pairs of nodes (u, v) \in V\times V and there are no cycles, i.e. it is not possible starting from one node following the direction of the arrows and returnig to the original node.
The pairs (u,v) are represented by arrows u \to v or v \leftarrow u and we say that u is a parent of v or that v is a child of u.
The set of parents of a node v is \mathrm{pa}_\mathcal{G}(v). In that case we still say that u and v are adjacent.
The adjacency matrix of \mathcal{G} is a d \times d Boolean matrix B = (b_{uv}) with b_{uv} = \begin{cases} 1 & \text{if } u \to v\\ 0 & \text{otherwise} \end{cases}

Example. The following graph is a DAG in 5 nodes

Its adjacency matrix is

  A C B E D
A 0 1 0 0 0
C 0 0 0 1 0
B 0 1 0 0 0
E 0 0 0 0 0
D 0 0 1 1 0

If the number of nodes is high and the DAG is sparse we usually code B as a sparse marix.
The number of DAGs with d nodes is growing quickly with d, (see link) \begin{array}{lr} d & \text{Number of DAGs}\\ \hline 1 & 1\\ 2 & 3\\ 3 & 25\\ 4 & 543\\ 5 & 29281 \end{array}
A nice characterization of an adjacency matrix of DAG is the following (see McKay et al. 2004)

Theorem. The matrix B is an adjacency matrix of a DAG if and only if B + I_d is a Boolean matrix with all eigenvalues being real and strictly greater than zero.

Paths

A path is a sequence of adjacent nodes without repetition.

the two paths from A to D are A \to C \to E \leftarrow D \qquad \text{ or } \qquad A \to C \leftarrow B \to D

A path is directed if all the arrow point away from the start. For instance B \to C \to E is a directed path from B to E.
A path of length 0 is a single node
A directed cycle is a directed path from i to j\ne i, together twith j \to i, like the first graph at the beginning of this section.
As we said, directed graphs with no directed cycle are called directed acyclic graphs.

Well-ordering of the nodes

The nodes of a DAG can always be well-ordered such that if a node i \in \mathrm{pa}_\mathcal{G}(j) then i < j. This ordering is also called topological ordering.
In a DAG there is always at least one topological ordering.

Example. Given the previous DAG there are 3 possible well-orderings:

[[1]]
[1] "A" "D" "B" "C" "E"

[[2]]
[1] "D" "A" "B" "C" "E"

[[3]]
[1] "D" "B" "A" "C" "E"

Predecessors

Given a specific well-ordering of the nodes, the set \mathrm{pre}(i) denotes all nodes that precede i.
For instance, if in the previous DAG we choose the well-ordering (A, D, B, C, E)

Thus, e.g. \mathrm{pre}(B) = \{A, D\}.

Further definitions

Ancestors and descendants

We say that a node a is an ancestor of v if either a = v or there is a directed path a\to\cdots \to v.
Example. In the previous DAG the ancestors of E are A, B, C, D, E.
We say that a node i is a descendant of v if either i = v or there is a directed path v \to \cdots \to i.
Example. The descendants of E is just E.
The non-descendants of v are \mathrm{nd}_\mathcal{G}(v) \equiv V \setminus \mathrm{de}_\mathcal{G}(v) where \mathrm{de}_\mathcal{G}(v) are the descendants of v.
Example. The non-descendants of E are A, B, C, D.

2.3 DAG Markov properties

We associate a probabilistic model to each DAG via various Markov properties. The fundamental MP are the following.
- The factorization property
- The ordered Markov property
- The directed local Markov Property
- The directed global Markov property

The factorization property

Given three variables X, Y, and Z we can always factorize their joint distribution in a specific order p(z, x, y) = p(z) \cdot p(x|z) \cdot p(y|x,z). Then we can associate to this factorization the DAG

where the parents of the variables are \mathrm{pa}(Z) = \emptyset, \quad \mathrm{pa}(X) = \{Z\},\quad \mathrm{pa}(Y) = \{Z, X\}.

Now consider three possible situations

Suppose that the variables concern

Z = gender
X = field of qualification
Y = successful job placement

and assume that job placement is independent of gender given the field of qualification, i.e., Y \;\perp \hspace{-2.2ex}\perp\;Z \mid X so that

p(y| x, z) = p(y|x) \text{ for all } x,y,z \text{ such that } p(x,z) >0.

Therefore the factorization simplifies: p(z, x, y) = p(z) \cdot p(x|z) \cdot p(y|x)

where p(y|x) depends only by X. This justifies that the conditional independence implies the removal of the edge Z \to Y and the generation of the graph below

Now assume instead that the variables are
- Z = Genetic marker
- X = Eye color
- Y = Hair color

and that eye color and hair color are independent given a genetic marker, that is X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z so that

p(y | x, z) = p(y|z), \text{ for all } x,y,z \text{ such that } p(x,z) > 0.

The factorization and the graph change into

p(z, x, y) = p(z) \cdot p(x|z) \cdot p(y|z).

so that

Finally, let the variables be
- Z = Maternal smoking
- X = Maternal malnutrition
- Y = Low birth weight
in some populations, and maternal smoking and maternal malnutrition are marginally independent, i.e., Z \;\perp \hspace{-2.2ex}\perp\;X and p(x|z) = p(x). Therefore the joint distribution factorizes

p(z, x, y) = p(z) \cdot p(x) \cdot p(y|x,z).

In this case in the DAG the missing edge Z \to X is implied by a marginal independence.

Notice that in the three situations above the factorization is always

p(z, x, y) = p(z) \cdot p(x|\mathrm{pa}(x)) \cdot p(y\mid \mathrm{pa}(y)

where when the factor specifies a conditioning on no parents the factor is interpreted as a marginal distribution.

Then we give a definition of factorization according to a DAG:

Definition. We say that the density of X_V = (X_1, \dots, X_d), p(x_V), factorizes with respect to the DAG \mathcal{G} if in any ordering,

\begin{align*} p(x_V) &= p(x_1) \cdot p(x_2|\mathrm{pa}(x_2)) \cdots p(x_d|\mathrm{pa}(x_d)) \\ &= \prod_{i \in V} p(x_i \mid x_{\mathrm{pa}(i)}). \end{align*}

This means that in the factorization, each factor only depends upon the parents.

Ordered Markov property

If the factorization property holds you can verify that p(x_i\mid x_{\mathrm{pre}(i)}) = p(x_i \mid x_{\mathrm{pa}(i)})

that implies a conditional independence X_i \;\perp \hspace{-2.2ex}\perp\;X_{\mathrm{pre}(i) \setminus \mathrm{pa}(i)} \mid X_{\mathrm{pa}(i)}

that leads to the so called ordered Markov property.

Definition. The probability distribution p_V is said to obey the ordered Markov property with respect to \mathcal{G} with a chosen topological order if X_i \;\perp \hspace{-2.2ex}\perp\;X_{\mathrm{pre}(i) \setminus \mathrm{pa}(i)} \mid X_{\mathrm{pa}(i)} \qquad \text{for every } i \in V.

Notice that the factorization property implies the ordered Markov property.

Example. Continuing the previous example, with a DAG in the ordering (A, D, B, C, E), which I repeat below for convenience

we get the factorization p(x_V) = p(a)\cdot p(d) \cdot p(b\mid d)\cdot p(c \mid a, b) \cdot p(e \mid c, d) and the ordered MP gives \begin{align*} A \;\perp \hspace{-2.2ex}\perp\;& D \\ B \;\perp \hspace{-2.2ex}\perp\;& A \mid D \\ C \;\perp \hspace{-2.2ex}\perp\;& D \mid (A,B) \\ E \;\perp \hspace{-2.2ex}\perp\;& (A, B) \mid (C, D) \end{align*}

The directed local Markov property

Definition. The probability distribution p_V is said to obey the directed local Markov property with respect to the DAG \mathcal{G} if X_i \;\perp \hspace{-2.2ex}\perp\;X_{\mathrm{nd}(i) \setminus \mathrm{pa}(i)} \mid X_{\mathrm{pa}(i)} \qquad \text{for every } i \in V.

For the previous DAG the directed local MP implies the conditional independencies (with some redundancy) \begin{align*} A \;\perp \hspace{-2.2ex}\perp\;& (B, D)\\ B \;\perp \hspace{-2.2ex}\perp\;& A \mid D\\ C \;\perp \hspace{-2.2ex}\perp\;& D \mid (A, B)\\ D \;\perp \hspace{-2.2ex}\perp\;& A \\ E \;\perp \hspace{-2.2ex}\perp\;& (A,B) \mid (C, D) \end{align*}

As the predecessors of a node i are always included in the non-descendants of i for every well-ordering it follows that \text{directed local MP} \implies \text{ordered MP} In fact it turns out that also the converse is true so that the two Markov properties are equivalent.

Essentially if the distribution is ordered Markov for a given well-ordering then it is ordered Markov with respect to all well-orderings. See Roverato (2017).

Marginalization and conditioning again

Suppose that we have again the three DAGs

They contain just one path with a single inner node. We call them V configurations
Let’s try to condition on and marginalize over the inner node of each V configuration

Transition V: p(z,x,y) = p(z) \cdot p(x|z) \cdot p(y|x)

Conditioning on X we know that Z and Y are independent
Marginalizing on X instead Z and Y are associated

Example. The table gives the joint distribution of Sex, Field of qualification and Job placement
\begin{array}{lll|ll} \hline & \text{History} & & \text{C. Science} & \\ \text{Job placement} & F & M & F & M \\ \hline \text{no} & 18 & 12 & 2 & 8 \\ \text{yes} & 12 & 8 & 8 & 32 \\ \hline \%\, \text{yes} & 40\% & 40\% & 80\% & 80\% \\\hline \end{array}
Job \;\perp \hspace{-2.2ex}\perp\; Sex \mid History and Job \;\perp \hspace{-2.2ex}\perp\; Sex \mid Computer. But, ignoring the field of qualification, the marginal table
\begin{array}{lll} \hline \text{Job placement} & F & M \\ \hline \text{no} & 20 & 20 \\ \text{yes} & 20 & 40 \\ \hline \%\,\text{yes} & 50\% & 66.7\% \\ \hline \end{array}
shows an association because the percentage of successful job placement is 66.7% for the males.

Source V: p(z, x, y) = p(z) \cdot p(x|z) \cdot p(y|z)

Conditioning on Z we know that X and Y are independent
Marginalizing on Z instead X and Y are associated

Example. Here is the table gives the joint distribution of the presence of a Gene and the color of the Eyes and Hair

\begin{array}{l|rr|rr} \hline \text{Gene} & \text{absent} & & \text{present} & \\ \text{Eyes} & \text{light} & \text{dark} & \text{light} & \text{dark} \\ \text{Hair} & & & & \\ \hline \text{light} & 1 & 9 & 64 & 16 \\ \text{dark} & 9 & 81 & 16 & 4 \\ \hline \%\, \text{yes} & 90\% & 90\% & 20\% & 20\% \\\hline \end{array}

The situation is the same of the previous example: Eyes \;\perp \hspace{-2.2ex}\perp\; Hair \mid Gene present, Eyes \;\perp \hspace{-2.2ex}\perp\; Hair \mid Gene absent,
However, ignoring the Gene the color of Eyes and Hair is associated:

\begin{array}{l|rr}\hline \text{Eyes} & \text{light} & \text{dark} \\ \text{Hair} & & \\ \hline \text{light} & 65 & 25\\ \text{dark} & 25 & 85 \\ \hline \%\,\text{dark} & 27.8\% & 77.2\% \\ \hline \end{array}

In the first case, the middle node is an intermediate node (a mediator), whereas in this case it is a source node (a common cause)

Collision V: p(z,x,y) = p(z)\cdot p(x) \cdot p(y|z,x). In this case the effect of conditioning and marginalizing is totally reversed:

Marginalizing on Y we know that X and Z are independent
Conditioning on Y, instead X and Z are associated.
Example. The table

\begin{array}{l|rr|rr} \hline \text{Malnutrition} & no & & yes & \\ \text{Smoke} & no & yes & no & yes \\ \text{Low Weight} & & & & & \\ \hline no & 437 & 315 & 35 & 5 \\ yes & 13 & 135 & 15 & 45 \\ \hline \%\, yes & 2.9\% & 30\% & 30\% & 90\% \\ \hline \end{array}

shows that the effect on Low weight at birth changes:

if there are no risk factors low birth weight is rare (about 3%).
If smoking is the only risk factor, the risk rises to 30%.
If malnutrition is the only risk factor the risk rises to 30%.
If both are present, the risk raises to 90%.

However Malnutrition is marginally independent of Low birth weight!

\begin{array}{l|rr} \hline \text{Malnutrition} & no & yes \\ \text{Smoke} & & \\ \hline no & 450 & 50 \\ yes & 450 & 50 \\ \hline \end{array}

If we select only babies with low weight, you will notice a negative association between smoking and malnutrition. If a child has low weight and we know that the mother does not smoke, it becomes much more likely that the cause is malnutrition.
This is sometimes called the Berkson paradox: if you analyze only hospital cases involving low birth weight, you will find that smoking and malnutrition () appear to be inversely associated. Smokers seem to be less nutritionally deficient and vice versa, but this is merely a selection bias.

An extended situation of the collision V

If there is a node W that is descendant of the collision node Y this is called an extended collider.
In this DAG originally X and Z are independent. But if you cannot directly observe Y, and you condition on its descendant W, this produces the same type of selection bias generated by the collision V.

Example. The factorization is p(z,x,y,w) = p(z)\cdot p(x) \cdot p(y|x,z) \cdot p(w|y) - Suppose that we consider the training routine
of a weightlifter and its consequences.

X: (Genetics): Muscle strength
Z: (Training): Hours spent at the gym
Y: (Strength): Result of a weightlifting test
W: Winning a medal (yes/no)

Define the marginal and conditional distributions:

X and Z are two independent standard normals
Y is a linear regression depending by X and Z
W is a linear logistic model depending on Y

\begin{align*} X &\sim N(0,1) \;\perp \hspace{-2.2ex}\perp\;Z \sim N(0,1) \\ Y &= X + Z + \varepsilon\text{ with } \varepsilon\sim N(0, 1/4) \\ W &\sim \text{Bernoulli}(p), \text{ with } p(w|y) = \text{expit}(-4 + 1.5 Y) \end{align*}

A simulation shows that \mathrm{corr}(X, Z \mid W = 1) is negative while the maginal correlation \mathrm{corr}(X, Z) \simeq 0.

n = 1000
X = rnorm(n)
Z = rnorm(n)
Y = X + Z + rnorm(n, 0, sd = 0.25)
W = rbinom(n, size = 1, prob = plogis(-4 + 1.5 * Y))
cor(X,Z)

[1] 0.02207246

cor(X[W == 1], Z[W==1])

[1] -0.4001025

The directed global Markov property

This discussion is propedeutical to the directed global Markov property that requires the introduction of a type of separation between the nodes called d-separation.

Differences

The directed local MP emphasizes the immediate relationship between a node and its predecessors. Every node is independent of its non-descendants (all nodes it cannot reach by following the arrows) given the set of its parents.

Everything that came before (but is not a parent) becomes irrelevant.
The directed global MP applies to any subset of nodes in the graph, regardless of their proximity.
The criterion of d-separation determines whether information can “flow” between two set of nodes. If the paths are blocked by a third set C, the two sets are independent given C
The paths are blocked or open depending on the various types of connections (chains, forks, or collisions).

Types of inner nodes. Consider a path in the DAG \mathcal{G}.

An inner node t is a collider if the edges adjacent to t meet as \bullet\to t \leftarrow \bullet.
An inner node t is said a non-collider (or a transmitter) if t is such that \bullet \to t \to \bullet (a transition node) or \bullet \leftarrow t \to \bullet (a source node).

Definition of open. A path from a to b is said open conditional on a set C \subseteq V \setminus \{a,b\} if:

all transmitters are outside C (i.e., no transmitters on the path are in C) and
every collider is an ancestor of something in C.

A path which is not open is said to be blocked by C.

Definition of blocked. A path from a to b is said blocked by a set of nodes C if either

the path contains a transmitter that belongs to C or
the path contains a collider that does not belong to C and has no descendants that belong to C.

Summary

Z \to X \to Y is open ignoring X, but is blocked by X \begin{matrix} Z & & & & Y \\ & \searrow & & \nearrow & \\ & & X & & \\ \end{matrix} \implies Z \;\perp \hspace{-2.2ex}\perp\;Y \mid X, \qquad Z \not{}\!\!\!\;\perp \hspace{-2.2ex}\perp\;Y
X \leftarrow Z \to Y is open ignoring Z but is blocked by Z \begin{matrix} X & & & & Y \\ & \nwarrow & & \nearrow & \\ & & Z & & \\ \end{matrix} \quad \implies X \;\perp \hspace{-2.2ex}\perp\;Y \mid Z, \qquad X \not{}\!\!\!\;\perp \hspace{-2.2ex}\perp\;Y
Z \to Y \leftarrow X is closed but is open ignoring X \begin{matrix} Z & & & & X \\ & \searrow & & \swarrow & \\ & & Y & & \\ \end{matrix} \implies Z \not{}\!\!\!\;\perp \hspace{-2.2ex}\perp\;Y \mid X,\qquad Z \;\perp \hspace{-2.2ex}\perp\;X
Z \to Y \leftarrow X is closed by W but is open ignoring both Y and W \begin{matrix} Z & & & & X \\ & \searrow & & \swarrow & \\ & & Y & & \\ & & \downarrow & & \\ & & W & & \\ \end{matrix} \implies Z \not{}\!\!\!\;\perp \hspace{-2.2ex}\perp\;X \mid W, \qquad Z \;\perp \hspace{-2.2ex}\perp\;X.

d-separation

Definition. Let A, B, C be disjoint sets of vertices in a DAG \mathcal{G} (C may be empty). We say that A and B are d-separated given C in \mathcal{G} (and write A \perp_d B \mid C) if every path from a \in A to b \in B is blocked by C.

Definition. The probability distribution p(x_V) is said to obey the directed global Markov property with respect to the DAG \mathcal{G} if for any triple of pairwise disjoint subsets A, B, C such that A \perp_d B \mid C \implies X_A \;\perp \hspace{-2.2ex}\perp\;X_B \mid X_C.

The global Markov property says that d-separation implies conditional independence
d-separation is complete: that is any triple not d-separated is generally not independent.

Therefore d-separation gives all independencies implied by the model.

Some examples

Example. Consider the DAG \begin{matrix} x & \rightarrow & \color{red} u & \color{red}\leftarrow & \color{red}v& \color{red}\rightarrow & \color{red}w & \color{red} \leftarrow &\color{red} y\\ & & \downarrow & & & & \downarrow & & \\ & & s & & & & t & & \\ \end{matrix} and the path \color{red} u,v,w,y.

Then, how is the path

given w? open
given v? blocked
given v,w? blocked
is u \;\perp \hspace{-2.2ex}\perp\;t \mid w? Yes. Why?
is x\;\perp \hspace{-2.2ex}\perp\;y \mid t? Yes. Why ?

Example. Consider the following DAG and let study all the paths from T to W.

Without conditioning, all 4 paths are blocked since they contain colliders.

     paths                   open   
[1,] "T -> X -> Y <- W"      "FALSE"
[2,] "T -> X <- Z -> W"      "FALSE"
[3,] "T -> Y <- W"           "FALSE"
[4,] "T -> Y <- X <- Z -> W" "FALSE"

Given Y things change:

     paths                   open  
[1,] "T -> X -> Y <- W"      "TRUE"
[2,] "T -> X <- Z -> W"      "TRUE"
[3,] "T -> Y <- W"           "TRUE"
[4,] "T -> Y <- X <- Z -> W" "TRUE"

is open because Y is the only collider
is open because Y is a descendant of X that is a collider on the path
is open because Y is the only collider
is open because Y is the only collider

Given the conditioning set C = \{Z,Y\} things change again:

     paths                   open   
[1,] "T -> X -> Y <- W"      "TRUE" 
[2,] "T -> X <- Z -> W"      "FALSE"
[3,] "T -> Y <- W"           "TRUE" 
[4,] "T -> Y <- X <- Z -> W" "FALSE"

is open because there is a transmitter X outside C and is Z is a collider in C
is blocked because Z is a transmitter in C
is open because there is a single collider Y in C
is blocked because Z is a transmitter in C.

Equivalence of the four directed Markov Properties

Equivalences

It can be shown the following

Theorem: Given a DAG \mathcal{G}= (V, E) if the distribution p_V admits a density, then

the factorization property,
the ordered MP
the directed local MP
and the global Markov properties

are all equivalent.

knitr::knit_exit()

References

Cox, R., D., and N. Wermuth. 1996. Multivariate Dependencies. Models, Analysis and Interpretation. Chapman & Hall.

Evans, R. J. 2025. Graphical Models. Lecture notes, University of Oxford. https://www.stats.ox.ac.uk/~evans/gms/lecturenotes_25.pdf.

Højsgaard, S., D. Edwards, and S. Lauritzen. 2012. Graphical Models with r. Use r! Springer: New York. https://books.google.it/books?id=em5QdpWmljAC.

McKay, Brendan D., Frédérique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M. Wanless, and Herbert S. Wilf. 2004. “Acyclic Digraphs and Eigenvalues of (0,1)-Matrices.” Journal of Integer Sequences 7 (3): Art. 04.3.3, 5 pp. (electronic). https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.

Roverato, A. 2017. Graphical Models for Categorical Data. Cambridge University Press.

Whittaker, J. 1990. Graphical Models in Applied Multivariate Statistics. John Wiley & Sons.