Equations defining probability tree models
Eliana Duarte
Otto Von Guericke Universität Magdeburg, Germany

arXiv:1802.04511v1 [] 13 Feb 2018

Christiane Görgen
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany

Abstract
Coloured probability tree models are statistical models coding conditional independence between
events depicted in a tree graph. They are more general than the very important class of contextspecific Bayesian networks. In this paper, we study the algebraic properties of their ideal of
model invariants. The generators of this ideal can be easily read from the tree graph and have
a straightforward interpretation in terms of the underlying model: they are differences of odds
ratios coming from conditional probabilities. One of the key findings in this analysis is that the
tree is a convenient tool for understanding the exact algebraic way in which the sum-to-1 conditions on the parameter space translate into the sum-to-one conditions on the joint probabilities
of the statistical model. This enables us to identify necessary and sufficient graphical conditions
for a staged tree model to be a toric variety intersected with a probability simplex.
Keywords: Algebraic Geometry; Algebraic Statistics; Graphical Models; Staged Trees

1. Introduction
Graphical statistical models are of great practical importance and their methodological foundations have now been well developed (Lauritzen, 1996; Cowell et al., 2007). The characterisation
of decomposable graphical models, and more generally of regular exponential families, as toric
varieties has made an important contribution to linking properties of these models to well-known
structures in algebraic geometry (Pistone et al., 2001; Geiger et al., 2006). This link can be used
for model selection (Geiger et al., 2001).
The term graphical model usually refers to conditional independence models represented by
acyclic digraphs. A more recent statistical model which can be represented by coloured probability trees is the staged tree, sometimes called a chain event graph (Collazo et al., 2018). Staged
tree models are curved exponential families. They do not rely on pre-specified problem variables but do contain both discrete models represented by acyclic digraphs and context-specific
Bayesian networks as a special case.

Email addresses: eliana.duarte@ovgu.de (Eliana Duarte), goergen@mis.mpg.de (Christiane Görgen)
URL: https://emduart2.github.io (Eliana Duarte), https://sites.google.com/view/goergen
(Christiane Görgen)
Preprint submitted to Elsevier

14th February 2018

In contrast to decomposable graphical models, in the algebro-geometric description of staged
trees the sum-to-1 conditions on the parameter space cannot be ignored. These hence constitute a
wider class of models with new and exciting algebraic properties. In this paper we define a system
of polynomial equations and inequalities whose solution set is equal to the set of probability
distributions which factorise according to a staged tree. These equations are given by differences
of odds ratios and hence allow for a very straightforward interpretation in terms of the underlying
model. They can also be easily read from any tree graph representation and are equivalent for any
two statistically equivalent staged trees. These results are presented in Section 3. In Section 4,
we state a full characterisation of staged tree models using the language of commutative algebra,
and we investigate the geometric behaviour of these models. These results pave the way for the
analysis conducted in Section 5, leading to the main result of this paper in Theorem 10 where
we give necessary and sufficient graphical conditions for a staged tree to represent a toric model.
These conditions are formally stated in terms of the algebraic and combinatorical properties of
the staged tree. However, centrally, they have a straightforward interpretation in terms of the
statistical properties of the staged tree, as seen in Theorem 11. We illustrate these results in
a long example developed over Section 6, stressing how they advance the current literature on
algebraic characterisations of standard graphical models such as Bayesian networks.
2. Staged tree models
Following the formalism developed by Görgen and Smith (2017), we always let T = (V, E)
denote a directed rooted tree graph where every vertex has either no or at least two emanating
edges. The set of these emanating edges is then denoted E(v) ⊆ E for every vertex v ∈ V. To
every edge e ∈ E we assign a positive probability θ(e) ∈ (0, 1) such that the labels of all edges
P
emanating from the same vertex sum to one, e∈E(v) θ(e) = 1. We call such a labelled tree graph a
probability tree. Probability trees have been shown to provide a powerful framework to transform
a problem description given in natural language into a valid statistical model (Collazo et al.,
2018) and as representational tools in causal inference (Shafer, 1996). The positivity assumption
in probability trees precludes issues related to validity assumptions as present for instance in
Bayesian networks. The local sum-to-1 conditions ensure that the multiplication rule of edge
labels along root-to-leaf paths in a probability tree induces a well-defined probability distribution
Q
over the graph. We denote this distribution as pθ (λ) = e∈E(λ) θ(e) where E(λ) ⊆ E denotes the
edge set of a root-to-leaf path λ in the tree, and the index θ = (θ(e) | e ∈ E) denotes the vector of
all edge labels. A probability tree model is the set of all probability distributions pθ which can
be written in this form, for varying values of edge labels:

M T = p θ | θ ∈ ΘT .

(1)

The parameter space ΘT of a probability tree model MT is simply a product of probability
simplices ΘT = ×v∈V ∆◦#E(v)−1 , one for each vertex, where
∆◦r−1

n

r

= x∈R |

r
X

xi = 1 and 0 < xi < 1 for all i = 1, . . . , r

i=1

o

always denotes the r − 1-dimensional probability simplex, for some positive integer r. The
probability tree model (1) is itself a subset of the probability simplex ∆◦n−1 where n denotes the
2

numer of root-to-leaf paths, or atomic events. In particular, it is the image of a parametrisation
Y

ψT : ΘT → ∆◦n−1 , θ 7→
θ(e)
(2)
e∈E(λ)

λ

where ψT (ΘT ) = MT .
We henceforth denote the vector of all probabilities attached to a vertex v ∈ V in a probability
tree by the bold character θv = (θ(e) | e ∈ E(v)). A staged tree is then a probability tree together
with an equivalence relation on the vertex set such that two vertices are in the same stage if
and only if their emanating edges have the same attached probabilities: in symbols, v ∼ w if
and only if θv = θw , possibly up to a permutation of the components of these vectors. See
Fig. 1 for an illustration. A staged tree model is therefore simply a probability tree model where
some probability simplices in the parameter space have been identified with each other. Staged
trees can be thought of as probability trees together with conditional independence information
on the depicted events. Given that a unit in the population modelled by the tree arrives at a
vertex then its immediate future unfoldings are independent of whether the unit arrived at that
particular vertex or any other vertex in the same stage. In this sense, stages identify historical
developments across a tree. In particular, if a tree depicts the product state space of a discrete
vector of random variables, then every vertex corresponds to a random variable conditional on
specific values taken by its ancestors, and an identification of emanating probabilities amounts to
identifying rows of conditional probability tables. As a consequence, staged tree models include
discrete and context-specific Bayesian networks as a special case (Smith and Anderson, 2008;
Collazo et al., 2018).
Because staged trees often encode a lot of symmetry, we will in Section 5.2 introduce the
concept of positions which are stages with identical future developments. Remarkably, we find
in Theorem 10 and Theorem 11 in that section that if all stages are positions then the parametrisation (2) behaves like a monomial parametrisation. As a consequence, sum-to-1 conditions on
the parameter space can be ignored and the resulting model is a toric variety inside a probability
simplex: see also Theorem 3 in the next section.
Staged trees have now been successfully employed over a whole range of applications (Freeman and Smith,
2011; Barclay et al., 2013, 2015; Collazo and Smith, 2015). Their mathematical properties have
only recently been analysed for the first time, by Görgen and Smith (2017). In that article, the
authors characterise all different staged tree parametrisations of the same discrete model using
symbolic nested representations of a polynomial generating function. This provides a framework to define two graphical operations which traverse the whole class of statistically equivalent
staged trees, so all representations of the same model. An alternative approach to the question
of statistical equivalence—or, in Bayesian networks, to characterise Markov equivalence—is to
provide an implicit rather than a parametric description of the model itself. All graphical represenations whose corresponding distributions fulfil these implicit constraints are then statistically
equivalent. We present such an algebraic characterisation and analyse its properties in this paper.
3. An implicit characterisation of staged trees
In this section, we employ our understanding of the statistical model represented by a staged
tree to derive equations which define this model as the solution set of a system of polynomial
equations, without explicitly referring to a parametrisation.
3

θ0

T1
τ0

v0

τ1
τ2

v1

θ1
θ0

v2
v3

θ1
θ0
θ1

p1
p4
p2
p5
p3
p6

τ0

T2
θ0

v1

τ1
τ2

v0

τ0
θ1

v2

τ1
τ2

p1
p2
p3
p4
p5
p6

T3

σ0
θ0

v1

η0

v3

θ1

σ0

v2
σ1

p1
p2

p3

σ1

v0

η1
η0

v4

η1

p4
p5

p6

Figure 1: Three staged probability trees where those vertices which are in the same staged are also assigned the same
colour. All three of these represent the same statistical model: a discrete independence model on a binary and a
ternary random variable. For T2 , the parametrisation ψT2 : ∆2−1 × ∆2−1 → ∆6−1 is defined by (θ0 , θ1 , τ0 , τ1 , τ2 ) 7→
(θ0 τ0 , θ0 τ1 , θ0 τ2 , θ1 τ0 , θ1 τ1 , θ1 τ2 ). See Theorem 4 for a full analysis.

3.1. Conditional probabilities and odds ratios
In Bayesian networks when a probability distribution factorises according to an acyclic directed graph we have an expression of the atomic probabilities as a product of conditional probQ
abilities depending on ancestor configurations, p(x) = ki=1 pi (xi |xpa(i) ) for all atoms x in an
Q
underlying discrete space. In the same fashion, we can read the distribution pθ (λ) = e∈E(λ) θ(e)
over root-to-leaf paths λ in a probability tree as a product of conditional probabilities where every
label θ(e) of an edge e = (v, v′ ) denotes the transition probability of moving on to v′ given arrival
at v. We show below why this is so and how this interpretation gives rise to a nice interpretation
of stage identifications.
For clarity, we henceforth denote atomic probabilities as pi = pθ (λi ) for root-to-leaf paths λi
numbered as i = 1, . . . , n. We write [v] ⊆ {1, . . . , n} for the indices of those root-to-leaf paths
which pass through a fixed vertex v ∈ V and we abbreviate the sum of their corresponding atomic
P
probabilities to p[v] = i∈[v] pi . Thus, p[v] is simply the probability of the event ‘passing through
v’. Whenever a staged tree is used as an equivalent representation of a Bayesian network, this
type of vertex-centred event corresponds to a margin of the bigger model (Collazo et al., 2018).
Paths in a tree graph which are not root-to-leaf paths are throughout denoted by their head and
tail, for instance v → w for a path from v to w. Note that in a tree graph every such path between
two vertices is unique and that for our purposes we can usually ignore its directionality. The set
of edges a path v → w passes through can then be denoted as E(v → w) ⊆ E. The root vertex of
T is always denoted by v0 ∈ V.
Two useful properties of p[v] will be employed over the following sections, for v ∈ V. First,
because of the additivity of the underlying probability measure, we can split each such probability
into the sum of probabilities measured at the children of v:
X
p[v] =
p[v′ ] .
(3)
(v,v′ )∈E(v)

This naturally follows the branching of the tree graph at each vertex and can be translated into
graphical-model language as ‘the probability of a margin equals the sum of the probabilities of
its margins’. Second, we can either recursively employ this first observation or we can directly
write each atomic probability in terms of its parametrisation to find that every probability p[v] can
be written in terms of a polynomial associated to a subtree of the bigger probability tree. To state
this fact let thus T (v) denote the induced subtree of T which is rooted at v and whose root-to-leaf
4

paths correspond to v-to-leaf paths in T . Let w1 , . . . , wk denote the leaves of T (v), for k ≤ n. Because T (v) is itself a probability tree, it has an associated probability distribution which for now
P
P Q
we write as q. Throughout this text, we denote by t(v) = kj=1 q[w j ] = kj=1 e∈E(v→w j ) θ(e) the
sum of all atomic probabilities in T (v). When imposing sum-to-one conditions, by construction
we have that t(v) = 1 for all v ∈ V. This notation enables us to elegantly write
Y
Y
p[v] =
θ(e) · t(v) =
θ(e)
(4)
e∈E(v0 →v)

e∈E(v0 →v)

which implies that each p[v] simply equals the probability arriving at the vertex v ∈ V. For
completeness, we also observe that plugging (3) into (4) gives the following recursive relation
X
t(v) =
θ(v, v′ ) · t(v′ )
(5)
(v,v′ )∈E(v)

which will enable us to simplify proofs in the following sections.
We can now easily derive the following fact.
Lemma 1. The probability label of every edge (v, v′ ) ∈ E is a fraction of sums of atomic probabilities
p[v′ ]
θ(v, v′ ) =
(6)
p[v]
and is the conditional probability of transitioning from v to v′ .
Proof. We simply observe that by (4), the fraction (6) is equal to
P
Q
′
′
′
j∈[v′ ] p j
e′ ∈E(v0 →v) θ(e ) · θ(v, v ) · t(v )
=
P
Q
i∈[v] pi
e∈E(v0 →v) θ(e) · t(v)

where t(v) and t(v′ ) are equal to one.

A straightforward implication of the above lemma is the following new result, translating a
stage identification of conditional probabilities into a collection of odds-ratio equations.
Lemma 2. Two vertices v, w ∈ V are in the same stage, v ∼ w, if and only if the equation of
atomic probabilities
p[v′ ] p[w] = p[w′ ] p[v]
is true for any two edges (v, v′ ) ∈ E(v) and (w, w′ ) ∈ E(w) which share the same label.
Proof. Validity of the statement can simply be seen by noting that two vertices are in the same
stage v ∼ w if and only if their edge labels are identified θ(v, v′ ) = θ(w, w′ ) for all emanating
edges (v, v′ ) ∈ E(v) and (w, w′ ) ∈ E(w). Plugging these equations into (6) yields the claim.
An equivalent statement has been proven by Sullivant (2018, Proposition 4.1.6) for acyclic
digraphs but not for more general discrete statistical models, so in particular not for discrete
context-specific conditional independence models and staged trees. We will fill this gap below.
We also dedicate a large part of the analysis in Section 4 to the study of the exact role played by
the sum-to-one conditions inherent to both the parametrisation and the associated distribution of
a probability tree. These conditions are often neglected, not only by Sullivant (2018) but also for
instance by Geiger et al. (2006) who make no reference to these subtleties.
5

Following Drton and Sullivant (2007), we henceforth call the ideal associated to a staged tree
via the polynomials in Theorem 2 its ideal of model invariants, denoted
IT = hp[v] p[w′ ] − p[v′ ] p[w] | for all v ∼ w and all (v, v′ ), (w, w′ ) ∈ E with the same labeli.
In analogy, we call the variety V(IT ) = {x | f (x) = 0 for all f ∈ IT } its model variety.
A direct consequence of Lemmata 1 and 2 is the following implicit characterisation of a
staged tree model as its model variety intersected with the probability simplex.
Theorem 3. Let MT be a staged tree model represented by a tree T = (V, E) with n root-to-leaf
paths and with associated ideal of model invariants IT . Then MT = V(IT ) ∩ ∆◦n−1 .
Thus staged tree models can either be directly specified using a staged tree representation—
and hence an explicit parametrisation—or implicitly using a collection of polynomial equations
as above. We discuss the implications of this result for statistical inference below and will then
in the subsequent section move on to analysing its geometric properties.
We make two key observations.
First, in statistical inference the system of polynomial equations specified in Theorem 3 is
well known. A ratio of probabilities is often called an odds ratio and identifications of odds ratios are frequently used tools in Bayesian inference and gambling (Smith, 2010). Under certain
conditions it can be favourable to elicit odds ratios rather than probability distributions in order
to specify a model using domain expertise (Garthwaite et al., 2005). Odds ratios naturally appear
when analysing conditional independences in contingency tables (Altham, 1969, 1970a,b) and
models determined by this type of constraints are now well studied. Because of the correspondence of odds-ratio equations to vanishing 2 × 2 minors of contingency tables, these results have
also been of interest to the community of algebraic statistics (Drton et al., 2009).
Second, in contrast to other implicit model characterisations—such as those obtained by
Geiger et al. (2006) which are reviewed and extended in the following section— the odds-ratio
equations which fully characterise a staged tree model can simply be read from any staged tree
graph. See Fig. 1 for an example. Thus there is a simple (visual) algorithm for passing from a
parametric to an implicit specification of a staged tree model, making it unnecessary to invert a
given parametrisation or to employ implicitisation methods such as Gröbner bases from computational algebraic geometry. When checking whether any set of atomic probabilities factorises
according to a given tree, we then only need to substitute the given values into the equation specified in Theorem 3 and check whether these evaluate to zero. An extensive discussion of this
procedure can be found in Görgen (2017, Section 2.3).
3.2. The ideal of model invariants
The polynomial odds-ratio characterisation provided by Theorem 3 enables us employ the
language of algebraic geometry to characterise staged tree models. Decomposable graphical statistical models have in the same fashion already been successfully characterised as toric varieties
(Pistone et al., 2001; Geiger et al., 2006). Because staged tree models contain decomposable
models as a special case, we can now easily extend these results and verify our advancement in
a well-studied context. This section provides the foundation to do so in Section 4.
Before proceeding into a study of their geometry, we note two properties which make staged
tree models special from an algebraic viewpoint.
6

First, by Theorem 3 and because of the ‘if and only if’ in Lemma 2, in an implicit characterisation of staged tree models there are no inequality constraints other than those coming
from the probability simplex. As a consequence, staged tree models really are algebraic varieties
inside the probability simplex. This makes them pleasingly easy to handle with algebraic tools
without diverting into the domain of real semi-algebraic geometry where the notion of closure
might force us to handle algebraic approximations of a model rather than the model itself. The
presence of hard-to-characterise inequality constraints has been a big challenge in many of the
recent attempts to tackle statistical problems using algebra tools. In a similar fashion, in the current algebraic statistics literature, the constraints imposed by the probability simplex have been
largely neglegted.
Second, by (2), every staged tree model is the image of a parametrisation whose domain is
by definition given by a product of probability simplices. If we extend this to the full space
ΘT = Rd —retaining stage identifications but ignoring sum-to-1 conditions and positivity—then
this map becomes monomial and its image a toric variety. However, for staged tree models in
general this is not the case. By Theorem 3, staged tree models are only toric in the probabilities
of vertex-centred events (or margins of the original model) rather than in the probabilities of
atomic events. In Section 4 we will investigate conditions under which staged tree models are
toric and provide a more general characterisation of their properties in case they are not. Figure 2
gives examples of a staged tree which neither toric nor decomposable but a Bayesian network,
one which is toric but not decomposable and one which is neither toric nor a Bayesian network.
In order to be able to distinguish the toric and non-toric cases, we introduce the following
notation for model parametrisations. We henceforth denote by R[p] = R[p1 , . . . , pn ] the polynomial ring whose indeterminates are given by atomic probabilities p1 , . . . , pn . We denote by
R[Θ] = R[θ(e)|e ∈ E] the polynomial ring whose indeterminates are given by the edge labels of
a given staged tree T = (V, E). Then the algebraic analogue of the map (2) is simply the ring
map
ϕ : R[p1 , . . . , pn ] → R[Θ]/hθ − 1i
Y
pi 7→
θ(e)
for all i = 1, . . . , n

(7)

e∈E(λi )

P
where we use the shorthand hθ − 1i = h e∈E(v) θ(e) − 1 | v ∈ Vi to denote the ideal coding the local
vertex sum-to-1 conditions of the probability tree. These conditions imply two properties of this
map. First, ϕ is not a monomial map and hence ker ϕ is in general not an affine toric variety.
Second, the polynomial p1 + . . . + pn − 1 is in the kernel of ϕ. Thus, following common practice
in algebraic statistics, we always consider ker ϕ as a homogeneous ideal in projective space. For
a longer discussion of this subtle point we refer the reader to Sullivant (2018, Section 3.6).
The ring map given by a probability tree parametrisation (2) which ignores the local sum-to-1
conditions is indeed a monomial parameterization and can simply be written as
ϕtoric : R[p1 , . . . , pn ] → R[Θ]
Y
pi 7→
θ(e)
for all i = 1, . . . , n.

(8)

e∈E(λi )

The kernel of ϕtoric is a toric ideal . We will analyse the relation between the kernels of the two
maps (7) and (8) in the following section, with a strong focus on the role played by the local
7

X1

X3

X2

T1

σ0
τ0

σ1
η0

v1
θ0

τ1

η1
σ0
τ0

v5
σ1
η0

v2
τ1

σ0
τ0

v3

θ0

τ1

v4
η1
ν0

v0
θ1

τ0

v5

τ1

v6

η1

θ0
θ0
v0

v1
θ1

θ1
ν1
µ0

v2

v6

T3

σ1
η0

v1

v4

v0
θ1

T2

v3

µ1

Figure 2: Three staged trees. T1 represents the conditional independence model X1 ⊥
⊥ X2 and X3 ⊥
⊥ X1 | X2 also studied
in Garcia Puente et al. (2005b). This model cannot be faithfully represented by a directed acyclic graph, it is not decomposable but toric. Indeed, M1 = V(p1 p7 − p5 p3 , p1 p8 − p5 p4 , p2 p7 − p6 p3 , p2 p8 − p6 p4 , p1 p6 − p5 p2 , p3 p8 − p7 p4 )∩∆◦8−1 .
The staged tree T2 represents the non-decomposable collider Bayesian network M2 = V((p1 + p2 )(p7 + p8 ) − (p3 +
p4 )(p5 + p6 )) ∩ ∆◦8−1 . The staged tree T3 represents the model M3 = V(p1 p3 = p2 (p1 + p2 )) ∩ ∆◦3−1 which is neither
toric nor a Bayesian network.

sum-to-1 conditions. In particular, Theorem 10 will give necessary and sufficient graphical and
algebraic conditions for the equality ker ϕ = ker ϕtoric to be true.
Throughout the remainder of this text, we call a staged tree model toric if and only if the kernel of the associated algebraic parametrisation (7) is a toric ideal. In this case, we automatically
have that ker ϕ = ker ϕtoric .
Example 4. To illustrate the notions above consider the model in Fig. 1. All of the staged trees
T1 , T2 , T3 in this figure represent the same statistical model which we denote by MT . This
means that the closed images of all of the parametrisations ψTi inside the probability simplex
∆6−1 are the same even though the parametrisation of ψT3 is different from ψT1 = ψT2 . The
different staged tree representations of MT give three ideals of model invariants with different
set of generators, namely
IT1 = hp1 p5 − p2 p4 , p1 p6 − p3 p4 , p2 p6 − p3 p5 i,
IT2 = hp1 (p5 + p6 ) − p4 (p2 + p3 ), p2 (p4 + p6 ) − p5 (p1 + p3 ), p3 (p4 + p5 ) − p6 (p2 + p1 )i,
IT3 = hp1 p5 − p4 p2 , p3 (p4 + p5 ) − p6 (p1 + p2 )i.
However, Theorem 3 states that we can implicitly define MT as the vanishing of any of the
above ideals ITi intersected with the probability simplex. We will see in Theorem 8 that the
closed image of ψTi in R6 is an irreducible component of all the varieties V(ITi ). In algebraic
language, this simply means that ker ϕ is an associated prime of ITi for i = 1, 2, 3. Let thus
denote Q = ker ϕ, then the three ideals of model invariants in this example have the following
decomposition
IT1 = Q,

IT2 = Q ∩ hp4 + p5 + p6 , p1 + p2 + p3 i,

8

IT3 = Q ∩ hp1 + p2 , p4 + p5 i.

4. Properties of staged tree models
In this section, we explore algebraic properties such as dimension of the model variety of
a general staged tree. We state these precisely in the language of commutative algebra. In
particular, we find that the ideal of model invariants easily links to the kernel of the associated
algebraic parametrisation (7) via saturation.
4.1. Dimension of MT
The dimension of the variety V(IT ) specified in Theorem 3 can simply be inferred from the
tree graph T . This is because the parametrisation (2) between the product parameter space ΘT
and the corresponding model MT is birational onto its image: see Theorem 1 and compare
Theorem 6 in the subsequent section. As a consequence, the dimension of V(IT ) is equal to the
dimension of ΘT , so equal to the number of free parameters in the statistical model.
In particular, assuming that the vertices of a tree graph T = (V, E) are partitioned into r
equivalence classes, each class corresponding to one stage (or one assignment of a colour), letting
mi denote the number of vertices which are assigned the ith colour and letting ki be their number of
edges, i = 1, . . . , r, we can write the parameter space ΘT as the product of probability simplices
P
×ri=1 ∆◦ki −1 ⊆ R#E . This space is of dimension ri=1 (ki − 1). Equivalently, it can easily be seen that
the total number of free parameters is equal to the number of parameters labelling the edges of
the tree, minus sum-to-1 conditions and stage assignments:
d = #E − #V ′ −

r
X

(mi − 1)(ki − 1)

i=1

where V ′ ( V denotes the set of non-leaf vertices of the tree. The equation d =
P
P
true because #V ′ = ri=1 mi and #E = ri=1 mi ki .

Pr

i=1 (ki

− 1) is

Example 5. The model represented by the staged tree T2 in Fig. 2 is not toric. It is of dimension
six (and codimension one) and IT2 = ker ϕ = h(p1 + p2 )(p7 + p8 ) − (p3 + p4 )(p5 + p6 )i. In this
case, the kernel of the map ϕtoric is empty because the atomic probabilities of this model do not
satisfy any relations unless local sum-to-1 conditions are imposed on the parameters.
However, if in T2 we colour the vertices v3 , v5 blue and v4 , v6 green, we obtain T1 and thus
ker ϕ = ker ϕtoric = hp1 p7 − p5 p3 , p1 p8 − p5 p4 , p2 p7 − p6 p3 , p2 p8 − p6 p4 , p1 p6 − p5 p2 , p3 p8 − p7 p4 i
which is a toric ideal whose corresponding variety is of dimension four.
In the above example, we observe that if we add extra colour to a staged tree, we lower the
dimension of the corresponding model and we can end up with a toric variety even when the
original model was not toric. This is systematic. In fact, whenever we identify new edge labels
we constrain the parameter space by projecting it onto a lower dimensional product of simplices.
This corresponds to creating a submodel of the original model. If in this way we superpose
two staged trees with the same tree graphs but different colourings, we merge more vertices into
common stages and thus add extra odds-ratio equations. This corresponds to intersecting the
corresponding model varieties.
We abstain from introducing cumbersome extra notation to formalise the point made above
but note that this can be done by characterising a staged trees’ model variety as the sum of its
stage ideals defined in (9) below.
9

4.2. Local properties of IT
In Theorem 6, the main result of this section, we state Theorem 3 in the language of commutative algebra. This result is then used to clarify the close relation between IT and ker ϕ in
terms of local rings.
In general, we always have that the ideal of model invariants IT ⊂ ker ϕ is contained in the
kernel of its algebraic parametrisation (7), or equivalently, that the model variety V(IT ) contains
the closed image of ϕ. However, as was illustrated in Theorem 4, equality does not always hold.
Compare also the long discussion given in Section 6.
Let henceforth p ∈ R[p1 , . . . , pn ] denote the product of all the denominators which appear in
the identified conditional probabilities (6) in a staged tree.
Theorem 6. For any staged tree T , the localized map
ϕp : (R[p1 , . . . , pn ]/IT )p → (R[Θ]/hθ − 1i)ϕ(p)
is an isomorphism of R-algebras. Hence (ker ϕ)p = (IT )p .
Proof. To prove that ϕp is an isomorphism we define the map
ψ : (R[Θ]/hθ − 1i)ϕ(p) → (R[p1 , . . . , pn ]/IT )p
p[v′ ]
θ(v, v′ ) 7→
p[v]
and check that this is an inverse for ϕp . Let thus λ = (e1 , . . . , ek ) denote the ordered sequence of
edges of the root-to-leaf path which is assigned atomic probability pi . Then
ψ(ϕp (pi )) = ψ(

k
Y

θ(ei )) =

i=1

k
Y

ψ(θ(ei )).

i=1

Writing the edges ei in terms of pairs of vertices, so e1 = (v0 , v1 ), e2 = (v1 , v2 ), . . . , ek = (vk−1 , vk ),
we see that the above can be further simplified to:
k
Y
i=1

ψ(θ(ei )) =

k
Y
p[v1 ] p[v2 ]
p[vk ]
p[vk ]
p[vi ]
pi
=
···
=
=
= pi
p
p
p
p
p
1
[v0 ] [v1 ]
[vk−1 ]
[v0 ]
i=1 [vi−1 ]

for any i = 1, . . . , n.
For the other direction, we see that
ϕp (ψ(θ(v, v′ ))) = ϕp

!
p[v′ ]
= θ(v, v′ )
p[v]

where the last equality follows from the Lemma 1. This proves the claim.
The next two corollaries follow immediately from properties of ideals after localising at an
element of the ring. Theorem 7 provides a way to compute ker ϕ without the use of elimination
theory.
Corollary 7. The kernel of ϕ is the saturation of IT with respect to p, so
ker ϕ = IT : (p)∞ .
10

Proof. For any ideal I in a polynomial ring R and any non-nilpotent element x, we have I x ∩ R =
I : (x)∞ where I x denotes the extension of the ideal I to the local ring R x . Then from Theorem 6
it follows that
ker ϕ = (ker ϕ)p ∩ R = (IT )p ∩ R = IT : (p)∞ .

In Theorem 3 we saw that the ideal of model invariants IT defines the model MT as a variety
V(IT ) inside the probability simplex. Theorem 8 states that the closed image of the parametrisation ψT is an irreducible component of IT .
Corollary 8. The ideal IT decomposes as
IT = ker ϕ ∩ Q
where Q is an intersection of primary components containing p.
Proof. This follows by localizing the primary decomposition for IT .
We remark that a result similar to Theorem 7 has been proven by Garcia Puente et al. (2005b)
for Bayesian networks. In that paper, the authors obtain their results without explicitly referring
to a parametrisation of the models they study. The big advantage of our result in Theorem 6 is
that the explicit probability-tree parametrisation admits simple interpretations of the algebraic
notions in terms of the underlying model. In particular, whilst for the authors above the element
p is the product of certain marginals of the random variables in a Bayesian network, for us
it is simply the product of all normalising constants we need to keep track of when identifying
conditional probabilities, so ratios of sums of atomic probabilities, across a staged tree. Thus, the
odds-ratio equations tell us precisely what an algebraic characterisation of the model looks like.
In addition, because Bayesian networks are simple special cases of staged trees, our Theorem 6
holds for a much more general class of models.
5. Toric staged tree models
These sections form the core of our algebraic analysis of staged tree models. In particular,
we are now ready to provide conditions under which the kernel of the ring map ϕ is a toric ideal.
In order to study these conditions, we introduce an ideal Ipaths whose generators can be read
from a staged tree in a way slightly different to the odds ratios. This ideal captures in a finer
way the implicit equations that define MT and is a key ingredient to understand the case when
ker ϕ = ker ϕtoric . Surprisingly, we will find in Theorem 10 that these kernels are equal if and
only if the local sum-to-1 conditions imposed on the domain of a probability tree parametrisation
can be ignored.
5.1. Definition and properties of Ipaths
Let v, w ∈ V and suppose the two vertices are in the same stage, so their attached labels
are identified θv = θw . For simplicity of notation, let θv = (s1 , . . . , sk ) be this vector of labels.
Write the sets E(v) and E(w) of edges emanating from v and w as E(v) = {(v, v1 ), . . . , (v, vk )} and
E(w) = {(w, w1 ), . . . , (w, wk )}, respectively. Without loss of generality assume that si = θ(v, vi ) =
θ(w, wi ). We define the ideal associated to this stage as
Iv∼w = hp[vi ] p[w j ] − p[wi ] p[v j ] | i, j = 1, . . . , ki
11

(9)

and denote the sum of all of these ideals as
Ipaths =

X

v∼w

in

(10)

Iv∼w .
T

The generators of Ipaths are quadratic polynomials that vanish on the closed image of ψT . They
are both algebraically and graphically closely related to the generators of IT and provide an
excellent tool to study the kernel of the corresponding parametrisation ϕ: we investigate the
details of this connection in this section.
The reason we denote the ideal in (10) as Ipaths is because each generator p[vi ] p[w j ] − p[wi ] p[v j ]
can be read off the staged tree by following two paths starting and ending at the identified vertices: this is shown in Fig. 3. We thus call these generators path differences. For simplicity, we
henceforth denote the two paths coding such a path difference as the pair (vi → w j , wi → v j ).
P
Using the identity p[v] = (v,vi )∈E(v) p[vi ] derived in (3), we immediately see that if T is a
binary staged tree then any odds-ratio equation p[w] p[vi ] − p[wi ] p[v] = 0 from Theorem 2 which
identifies two edges (v, vi ) and (w, wi ) is a path difference, i = 1, 2. These reduce to the unique
generator of Iv∼w . Indeed, we can explicitly calculate that p[v] = p[v1 ] +p[v2 ] and p[w] = p[w1 ] +p[w2 ]
so that
p[v] p[w1 ] − p[v1 ] p[w] = (p[v1 ] + p[v2 ] )p[w1 ] − p[v1 ] (p[w1 ] + p[w2 ] )
= p[v2 ] p[w1 ] − p[v1 ] p[w2 ] .
This equality between odds-ratio differences and path differences does not hold in case T is not
a binary tree: see tree T2 in Fig. 1 for an illustration. More generally, for non-binary trees each
odds-ratio difference can be written as a sum of elements in the ideal Ipaths . We can see this
simply by writing the odds-ratio difference which identifies the labels θ(v, vi ) = θ(w, wi ) as




 X

 X

p[vi ] p[w] − p[wi ] p[v] = p[vi ] 
p[w j ]  − p[wi ] 
p[v j ] 
(w,w j )∈E(w)

=

k
X

(v,v j )∈E(v)

p[vi ] p[w j ] − p[wi ] p[v j ] .

j=0

The differences p[vi ] p[w j ] − p[wi ] p[v j ] for v ∼ w and i, j ∈ {1, . . . , k} are exactly the generators of
Iv∼w . This discussion proves the first containment in the next lemma.
Lemma 9. IT ⊆ Ipaths ⊆ ker ϕ.
Proof. From the definition of Ipaths , it is enough to show that for any two vertices v, w in the same
stage, the generators of Iv∼w are in ker ϕ. Using the relation obtained in (4) from Section 3.1, we
have
Y
Y
ϕ(p[v] ) = t(v) ·
θ(e) =
θ(e).
e∈E(v0 →v)

e∈E(v0 →v)

This implies that


 


 Y
  Y
  Y
  Y

ϕ(p[vi ] p[w j ] − p[wi ] p[v j ] ) =  si ·
θ(e)  s j ·
θ(e) −  s j ·
θ(e)  si ·
θ(e) = 0. (11)
e∈E(v0 →v)

e∈E(v0 →w)

12

e∈E(v0 →w)

e∈E(v0 →v)

si

vi

sj

..
.
vj

si

wi

sj

..
.
wj

v

tail of path
p[vi ] p[w j ] = p[wi ] p[v j ]

v0
w

..
.

head of path

Figure 3: A staged tree illustrating path differences. Here, white stages can be of any colour as long as v and w are in
the same stage. The unique path starting at vi and ending in w j then corresponds to the product p[vi ] p[w j ] and the unique
path starting at wi and ending at v j corresponds to p[wi ] p[v j ] .

By Theorem 9, we can thus use the path structure of a staged tree directly as a tool to find
an inclusion between the kernel of the algebraic map describing the associated model and the
true relations describing the model variety. Over the next section, we will use this result to study
conditions under which these ideals are equal and conditions under which they are toric.
5.2. Characterization of toric staged tree models
Theorem 10 presented in this section is the key result of this paper. It gives necessary and
sufficient algebraic criteria for a staged tree model to be toric. Most pleasantly, we find that such
criteria can be formulated in terms of the polynomials t(v) defined in Section 3 for v ∈ V, and
can be therefore be interpreted in terms of the statistical properties of the staged tree model.
To formulate this connection precisely, we briefly recall a definition from Smith and Anderson
(2008). Two vertices v and w in a staged tree T = (V, E) are said to be in the same position if they
are in the same stage v ∼ w and their induced subtrees T (v) and T (w) have the same parametrisation ψT (v) = ψT (w) . The notion of positions is of practical importance in staged tree models
because it both provides a vocabulary to address vertices which have identical future unfoldings
(independent of their different histories) and it provides a tool to classify subtrees representing
the same statistical (sub-)model. We refer the reader to Collazo et al. (2018) for a detailed discussion of the subtle relations between stages and positions. Görgen and Smith (2017) show that
two vertices v and w are in the same position if and only if the symbolic polynomials t(v) and
t(w) as defined in (4) are identical: this notion is also known as polynomial equivalence.
Consider now a path difference p[vi ] p[w j ] − p[wi ] p[v j ] ∈ Iv∼w . We showed in Lemma 9 that
ϕ(p[vi ] p[w j ] − p[wi ] p[v j ] ) = 0. In the proof of this lemma, the equation in (11) can equivalently be
written as


Y
 Y

ϕ(p[vi ] p[w j ] − p[v j ] p[wi ] ) = si s j · 
θ(e) ·
θ(e)  · (t(vi )t(w j ) − t(wi )t(v j )).
(12)
e∈E(v0 →v) e∈E(v0 →w)

Now the expression (12) is equal to zero either if we use the property t(vi ) = t(w j ) = t(wi ) =
t(v j ) = 1 or if the polynomial equation t(vi )t(w j ) = t(wi )t(v j ) is true in R[Θ] where we are
not taking the quotient by the ideal of sum-to-1 conditions. This observation implies that if
13

t(vi )t(w j ) = t(wi )t(v j ) is true then the path difference p[vi ] p[w j ] − p[v j ] p[wi ] ∈ ker ϕtoric lies in the
kernel of the monomial parametrisation associated to the tree.
In other words, if we assume that in the ring R[Θ] spanned by the edge labels the equation
t(vi )t(w j ) = t(wi )t(v j )

for all i, j = 1, . . . , k

(⋆)

is true then the stage ideal Iv∼w ⊂ ker ϕtoric lies in the kernel of the toric map. This leads us to the
main result of this paper.
Theorem 10. Let T be a staged tree. Then
ker ϕtoric = ker ϕ
if and only if condition (⋆) holds for all vertices v, w of T which are in the same stage.
Proof. If condition (⋆) holds for all vertices v, w in the same stage, it follows that Ipaths ⊂ ker ϕtoric
by the definition of Ipaths and the discussion before the theorem. Hence, using Theorem 9, we
deduce that IT ⊂ ker ϕtoric . It is also straightforward to see that ker ϕtoric ⊂ ker ϕ. We thus arrive
at the chain of containments
IT ⊂ ker ϕtoric ⊂ ker ϕ.
Using Theorem 6 and localizing at p, we see that
(IT )p = (ker ϕtoric )p = (ker ϕ)p .
Since both ker ϕtoric and ker ϕ are prime, we obtain ker ϕtoric = ker ϕ.
Theorem 10 has two main implications for our algebraic characterisation of staged tree models.
First, whenever condition (⋆) holds, the algebraic parametrisation (7) behaves exactly like
the monomial parametrisation (8). As a consequence, (⋆) is true if and only if the sum-to-1
conditions on the parameter space of the staged can be ignored.
Second, we can simply read from the tree graph a sufficient condition for (⋆) to hold. In
fact, if two vertices v ∼ w with children v1 , v2 and w1 , w2 , respectively, are in the same stage
then t(v1 )t(w2 ) = t(w1 )t(v2 ) is satisfied whenever t(v1 ) = t(w1 ) and t(w2 ) = t(v2 ). In this case,
the vertices v1 and w1 , and v1 and w2 , are in the same position, respectively. This implies the
following:
Corollary 11. If in a staged tree all vertices which are in the same stage are also in the same
position then the corresponding staged tree model is toric.
In the language of Collazo et al. (2018), simple chain event graphs are toric.
Intuitively, coloured probability trees for which all stages are also positions have many symmetries. For example, the tree T2 from Fig. 2 satisfies condition (⋆) for all staged vertices
whereas the tree T3 in the same figure does not. Indeed, the kernel of the monomial parametrisation belonging to T3 is empty. This straightforward visual property of staged trees and the
fact that the polynomials t(·) can be easily read from a staged tree without any knowledge about
either the underlying statistical model or the algebraic characterisation, is precisely what makes
our models so appealing and Theorem 10 so powerful.
We illustrate in the next example that the result in Corollary 11 is sufficient but not necessary:
even if none of the vertices vi , v j from condition (⋆) are in the same position it could still be the
case that t(vi )t(w j ) = t(wi )t(v j ).
14

Example 12. Consider a staged tree T where the vertices v, w are the only children of the root
v0 and v ∼ w. Suppose v, w only have two emanating edges and denote E(v) = {(v, v1 ), (v, v2)}
and E(w) = {(w, w1 ), (w, w2 )}. If t(v1 ) = (a0 + a1 )(b0 + b1 + b2 ), t(w2 ) = c0 + c1 and t(w1 ) =
(a0 + a1 )(c0 + c1 ), t(v2 ) = b0 + b1 + b2 then the equation t(v1 )t(w2 ) = t(w1 )t(v2 ) is satisfied but
none of the vertices v1 , v2 , w1 , w2 are in the same position.
5.3. Extension of paths and binomial generators of ker ϕtoric
We proved in Lemma 9 that Ipaths is contained in ker ϕ. In addition, each generator of Ipaths
can be read from T as in Figure 3. In this section we describe a way to extend pairs of paths
associated to generators of Ipaths in such a way that when we write down the path difference of
an extended pair, we automatically get an element in ker ϕ.
If we extend each path (v1 → w2 , w1 → v2 ) by one edge in such a way that the two added
edges have the same parameter label, we see that from the extended paths we can write a new path
difference in R[p1 , . . . , pn ] that is also in ker ϕ. More precisely, a pair of paths (vh → wt , wh → vt )
is said to be an extension of (v1 → w2 , w1 → v2 ) by l edges if the next two conditions hold.
1. The path vh → wt is obtained from v1 → w2 by adding l edges either at the head or tail of
v1 → w2 and likewise for wh → vt and w1 → v2 .
2. Let {e1 , . . . , el } = E(vh → wt ) \ E(v1 → w2 ) and {e′1 , . . . , e′l } = E(wh → vt ) \ E(w1 → v2 )
then
l
l
Y
Y
θ(ei ) =
θ(e′i ).
i=1

i=1

We associate the path difference p[vh ] p[wt ] − p[wh ] p[vt ] to the extended pair (vh → wt , wh → vt )
and note that the second condition implies that p[vh ] p[wt ] − p[wh ] p[vt ] ∈ ker ϕ.
Example 13. We consider the staged tree T1 in Figure 2. We label the leaves of T2 from top to
bottom by l1 , . . . , l8 and in the same fashion for the atomic probabilities p1 , . . . , p8 . Consider the
pair (v3 → v6 , v5 → v4 ) and its associated path difference
p[v3 ] p[v6 ] − p[v5 ] p[v4 ] = (p1 + p2 )(p7 + p8 ) − (p5 + p6 )(p3 + p4 ).
Notice that a possible extension of (v3 → v6 , v5 → v4 ) by one edge is given by (l1 → v6 , l5 → v4 )
because θ(v3 , l1 ) = θ(v5 , l5 ) = σ0 . The path difference associated to this extension is
p[l1 ] p[v6 ] − p[l5 ] p[v4 ] = p1 (p7 + p8 ) − p5 (p3 + p4 ).
We can further extend this path by using an edge with label η0 or η1 . For instance the extension
(l1 → l7 , l5 → l3 ) with associated path difference p1 p7 − p5 p3 .
From the example above, we see that each path difference in Iv∼w can have several extensions
to paths in T . We call an extension (vh → wt , wh → vt ) of (v1 → w2 , w1 → v2 ) a maximal
extension if it is not possible to add edges to the pair (vh → wt , wh → vt ) in such a way that
condition (2) is satisfied. For example, the extension (l1 → l7 , l5 → l3 ) in Theorem 13 is maximal
but (l1 → v6 , l5 → v4 ) is not.
We define the ideal Impaths generated by all maximal path differences in an analogous way to
Ipaths . Explicitly, given v ∼ w, we denote by Imax(v∼w) the ideal generated by all path differences
associated to all maximal paths extending a pair (vi → w j , wi → v j ) for all i, j ∈ {1, . . . , k}. Then
X
Impaths =
Imax(v∼w) .
v∼w

in

15

T

We say that a pair of paths (v1 → w2 , w1 → v2 ) fully extends if for each maximal extension
(vh → wt , wh → vt ), all of the vertices vh , wt , wh , vt are leaves of T . When this is the case, we see
that all path differences associated to extensions are actually binomials. For instance, it is easy
to see that all paths in T1 from Theorem 13 fully extend and
Impaths = hp1 p7 − p5 p3 , p1 p8 − p5 p4 , p2 p7 − p6 p3 , p2 p8 − p6 p4 , p1 p6 − p5 p2 , p3 p8 − p7 p4 i
is binomial. For this ideal the first four generators correspond to extended paths and the other two
are the path differences of the blue and green stages. Furthermore MT1 is toric and ker ϕ = Impaths .
Following the strategy from the previous section, we now first characterise staged trees in
terms of (maximal) path differences and then use these results to understand the ideal of model
invariants.
Below, we thus start by giving a necessary condition for a path difference to fully extend.
Interestingly, this condition is the same that comes up in Theorem 10 to decide wether ker ϕ is
toric. In the discussion at the end of this paper, we conjecture that this is the case because for
toric staged trees, the ideal Impaths is equal to the kernel of ϕ.
Lemma 14. Suppose that v ∼ w and t(vi )t(w j ) − t(wi )t(v j ) = 0 for all i, j ∈ {1, . . . , k}. Then every
path (vi → w j , wi → v j ) fully extends.
Proof. For convenience, assume i = 1, j = 2. Suppose that t(v1 )t(w2 ) − t(w1 )t(v2 ) = 0. For
v ∈ V, each t(v) is a sum of atomic probabilities of the subtree T (v). The expansion of t(v1 )t(w2 )
is a sum of products of atomic probabilities in T (v1 ), T (w2 ). Therefore each term in t(v1 )t(w2 )
cancels with a term in t(w1 )t(v2 ). We may write this cancelation as mv1 mw2 − mw1 mv2 = 0 where
Y
Y
Y
Y
mv 1 =
θ(e), mw2 =
θ(e), mw1 =
θ(e), mv1 =
θ(e)
e∈E(v1 →l1 )

e∈E(w2 →l2 )

e∈E(w1 →l3 )

e∈E(v2 →l4 )

are atomic probabilities of the subtrees T (v1 ), T (w2 ), T (w1 ), T (v2 ), respectively. Thus the pair
(l1 → l2 , l3 → l4 ) is an extension of (v1 → w2 , w1 → v2 ), namely
l1 → l2

=

l1 → v1 → w2 → l2

l3 → l4

=

l3 → v2 → w1 → l4

and mv1 mw2 = mw1 mv2 . The path (l1 → l2 , l3 → l4 ) is a full maximal extension because l1 , l2 , l3 , l4
are leaves of T . Conversely, every maximal extension is a cancellation of terms in t(v1 )t(w2 ) −
t(w1 )t(v2 ).
We can now directly derive the following result, providing a sufficient condition for Impaths to
be binomial.
Theorem 15. Let T be a staged tree and suppose that condition (⋆) holds for all v, w ∈ T in the
same stage. Then Impaths is a binomial ideal.
Proof. Using Lemma 14 we see that the path differences in Iv∼w fully extend for all vertices of
T in the same stage. By the definition of full extension of paths this implies that the generators
of Impaths are binomials.
16

6. An example and connections to graphical models
In this section we illustrate the concepts introduced over the course of this paper in a simple
real system: see Collazo et al. (2018, Examples 3.4 and 3.6) for details. The discrete statistical
models represented by the graphs in Fig. 4 were built to explain the unfoldings of events in a cell
culture. Within this culture the environment might be hostile or benign and the activity between
cells might be high or low, independent of the state of the environment. If the environment is
hostile then cells suffer damage and either die or survive with the same respective probabilities.
Surviving cells make either a full or partial recovery, independent of their history.
These highly asymmetric stories can be represented by the undirected graph given in Fig. 4b,
the directed acyclic graph in Fig. 4c, the staged tree in Fig. 4a or the staged tree in Fig. 4d.
We can now analyse the different statistical and algebraic properties of each of these models,
contrasting our results to those obtained by Garcia Puente et al. (2005b); Geiger et al. (2006) for
decomposable graphical models and Bayesian networks.
Consider first the decomposable model from Fig. 4b. This graph represents the single conditional independence assumption that recovery of a cell is independent of its activity and of the
state of the environment, given survival. In symbols, X4 ⊥
⊥ (X1 , X2 ) | X3 . As a staged tree, this
model can be represented by the graph in Fig. 4a with the vertices v7 , v9 , v11 , v13 and v8 , v10 , v12 , v14
in the same stage, respectively. So rather than working on the undirected graph, we can equivalently exclusively consider the red and yellow colouring of this tree, for the moment ignoring the
other colours: for simplicity, we denote this staged tree as Tdec . The ideal of model invariants of
Tdec is given by
ITdec = Ired + Iyellow
where the generators of the stage ideals Ired = Iv7 ∼v9 + Iv9 ∼v11 + Iv11 ∼v13 and Iyellow = Iv8 ∼v10 +
Iv10 ∼v12 + Iv12 ∼v14 are odds-ratio differences which can be read from the tree as
Ired = hp1001 p1100 − p1000 p1101 , p0101 p1100 − p0100 p1101 , p0001 p1100 − p0000 p1101 ,
p0101 p1000 − p0100 p1001 , p0001 p1000 − p0000 p1001 , p0001 p0100 − p0000 p0101 i
Iyellow = hp1011 p1110 − p1010 p1111 , p0111 p1110 − p0110 p1111 , p0011 p1110 − p0010 p1111 ,
p0111 p1010 − p0110 p1011 , p0011 p1010 − p0010 p1011 , p0011 p0110 − p0010 p0111 i.
Because Tdec is a binary tree, the ideal ITdec = Ipaths is equal to the ideal generated by path
differences. By construction, ITdec is also equal to the ideal Ilocal(G) generated by cross-product
differences coding the local Markov property in the decomposable graph G in Fig. 4b, as defined
by Geiger et al. (2006). In particular, the model is thus equal to the variety V(ITdec ) = V(Ilocal(G) )
intersected with the probability simplex. To illustrate the direct translation of our methods into
their framework, here we use notation used by the authors cited above and denote by pi jkl =
P
P(X1 = i, X2 = j, X3 = k, X4 = l) an atomic probability and by pi j++ = kl pi jkl a marginal
probability, for i, j, k, l = 0, 1. Naturally, the atomic probabilities are attached to leaves of the
tree, so pi jkl is the probability of the root-to-leaf path labelled X1 = i, X2 = j, X3 = k, X4 = l. The
marginal probabilities can equivalently clearly be expressed as probabilities of vertex-centred
events in the tree graph: for instance, p00++ = p[v3 ] = θ(v0 , v1 )θ(v1 , v3 ) · t(v3 ) where the labels
θ(v0 , v1 ) = P(X1 = 0) and θ(v1 , v3 ) = P(X2 = 0|X1 = 0) are conditional probabilities and t(v3 ) is
the sum of atomic probabilities in the induced subtree T (v3 ).
We observe that the ideal Ired + Iyellow is toric because the path differences coding the red and
the yellow stage belong to pairs of paths which extend to the leaves of the tree simply because
17

X1

X3

X2

X4
die
0
X3 =
X3 =
surviv 1
e

v3
v1
le
sti
ho = 0
X1

v7

h
hig
=0
X2
X2
=1
low

v8

v9
die
0
X3 =
X3 =
surviv 1 v
10
e

v4

v0
v11
die
0
X3 =
X3 =
surviv 1 v
12
e

X

1

be = 1
ni
gn

v5
v2

h
hig
=0
X2
X2
=1
low

v13
die
0
X3 =
X3 =
surviv 1 v
14
e

v6

full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial
full X4 = 0
X4 = 1
partial

p0000
p0001
p0010
p0011
p0100
p0101
p0110
p0111
p1000
p1001
p1010
p1011
p1100
p1101
p1110
p1111

(a) A staged tree T representing a context-specific Bayesian network.

die
environment

environment

X1

recovery

X3
X2
activity

survival

X1

X2

l e v1
sti
low
ho

recovery

X3

X4

full

v8
h v3
survive pa
hig
X4

survival

v0
be
high
nig
n v2

activity

die

rtial

v4

surv v10 full
ive
pa
rt i a
l

low
(b) A decomposable undirec- (c) A Bayesian network that is (d) A staged tree T>0 which is not a
ted graphical model.
not decomposable.
context-specific Bayesian network.
Figure 4: Four graphical models for the unfoldings of events in a cell culture. For simplicity, here stages which do not
contain more than one vertex have been coloured white.

18

the children of these stages are leaves. Using any computer algebra software, we can check
that the ideal of model invariants of the staged tree is also equal to the kernel of the algebraic
parametrisation: ITdec = ker ϕ.
Equivalently, Geiger et al. (2006) prove in their Theorem 4.3 that ITdec = Ilocal(G) is toric
because it is the ideal of model invariants of a decomposable graphical model. We can see
here that, in contrast to the staged tree, the generators of this ideal cannot be directly read from
the decomposable graph but need to be calculated via other methods, for instance using the
Macaulay2 package GraphicalModels (Garcia Puente et al., 2005a).
Consider now the Bayesian network given in Fig. 4c which is not decomposable. This graph
codes the additional condition that the state of the environment and the activity within a cell
culture are independent of each other: so here, X1 ⊥
⊥ X2 as well as X4 ⊥
⊥ (X1 , X2 ) | X3 . This
model can alternatively be represented by a staged tree denoted TBN which has the same coloured
graph as Tdec but with an additional stage v1 ∼ v2 , coloured blue. The ideal of model invariants
of this tree is again generated by path differences and is equal to ITBN = ITdec + Iblue where
Iblue = hp[v3 ] p[v6 ] − p[v4 ] p[v5 ] i = hp00++ p11++ − p01++ p10++ i.
By construction, Iblue is toric in the marginal probabilities. However, by Theorem 10, it is
not toric in the atomic probabilities. Indeed, the full ideal of model invariants of this tree is not
toric because the condition (⋆) is not fulfilled: we can easily use the tree graph to check that
t(v3 )t(v6 ) , t(v4 )t(v5 ).
Using any computer algebra software, we find that the ideal of model invariants ITBN = ker ϕ
is still equal to the kernel of the algebraic parametrisation. The theory developed by Geiger et al.
(2006) did not supply the means to find this algebraic characterisation. However, here we study
a Bayesian network on four binary random variables, so one of the subjects of the thorough
analysis provided by Garcia Puente et al. (2005b, Table 1, #21). Using prime decomposition of
the conditional independence ideal, these authors find that the ideal of model invariants of this
Bayesian network is prime, of codimension 7, of degree 32, and has 13 minimal generators.
In a third step, consider the context-specific Bayesian network represented by the graph in
Fig. 4c and with the extra condition that X3 ⊥
⊥ X2 | X1 = 0 is true. In words, we now embed
the information that the probability of survival of a cell in the culture does not depend on its
activity, given that the environment was hostile. Whilst the directed acyclic graph cannot code
this condition graphically, we can immediately read it from the green stage in the staged tree T
given in Fig. 4a. The full ideal of model invariants IT = ITBN + Igreen is now equal to
IT = Ired + Iyellow + Iblue + Igreen
just like discussed in Section 4.1. Here, the green path differences generate the ideal
Igreen = hp[v7 ] p[v10 ] − p[v9 ] p[v8 ] i = hp000+ p011+ − p010+ p001+ i
in the obvious notation for marginal probabilities. This result extends the results of both of
Garcia Puente et al. (2005b); Geiger et al. (2006) who do not study context-specific Bayesian
networks.
Using Theorem 10, we can see again that IT is not toric. This is because even though now
v3 and v4 are in the same position, implying that t(v3 ) = t(v4 ), we still have t(v5 ) , t(v6 ). So
t(v3 )t(v6 ) , t(v4 )t(v5 ) and condition (⋆) is not fulfilled.
19

Because in the staged tree T tree path differences can be extended, we find that in this case
the ideal of model invariants is not equal to the kernel of the algebraic parametrisation, IT ,
ker ϕ. In fact IT is not radical and has five associated primes, one of them being ker ϕ. We can
computationally check in this case that the kernel of ϕ is equal to the ideal of maximal paths:
ker ϕ = Impaths . This observation, together with all of the examples presented in this paper, is
strong evidence for Theorem 16 which we formulate in the discussion at the end of this paper.
In a final step, we observe that many of the unfoldings in the graph of T as given in Fig. 4a
are logically impossible. For instance, the measure of recovery for cells which have died is
nonsensical. In the same fashion, the problem description states that within the cell culture, cells
get damaged only if the surrounding environment was hostile. This implies that the measure of
survival is nonsensical in benign environments. As a result, many of the atomic probabilities in
the context-specific Bayesian network need to be assigned probability zero. We can avoid this
redundancy by directly modelling the given situation using the staged tree depicted in Fig. 4d.
We denote this tree T>0 because all of its labels are strictly positive. The dimension of the
corresponding model MT>0 is much smaller: the model variety is of dimension four in sevendimensional space, rather than of dimension six in sixteen-dimensional space, as was the case
for MT .
The ideal of model invariants for the staged tree T>0 can be calculated in exactly the same
fashion as presented above, now resulting in
′
′
′
+ Iblue
IT>0 = Iyellow
+ Igreen

= hp2 p6 − p5 p3 i + hp1 (p5 + p6 ) − p4 (p2 + p3 )i + h(p1 + p2 + p3 )p8 − p7 (p4 + p5 + p6 )i
where we read the atomic probabilities from top to bottom in Fig. 4d. This ideal is toric because
all paths fully extend. Again, we can calculate that IT>0 , ker ϕ but that the kernel of the algebraic
parametrisation is given by the maximal paths:
Impaths = ker ϕ = hp3 p5 − p2 p6 , p2 p4 − p1 p5 , p3 p4 − p1 p6 , p4 p7 − p1 p8 , p5 p7 − p2 p8 , p6 p7 − p3 p8 i.
These generators form a Gröbner basis with respect to the reverse lexicographical term order.
7. Discussion
Throughout this text we have analysed the algebraic and geometric properties of the ideal IT
of model invariants of MT . We have seen that this ideal has a distinguished prime component,
namely ker ϕ, and we have fully characterised in Theorem 10 conditions under which this ideal
is toric. Although we have not always explicitly stated it, all of the examples we have seen in
this paper have the property that ker ϕ is equal to the ideal Impaths . This leads us to:
Conjecture 16. Let T be a staged tree. Then the kernel of ϕ is exactly the ideal generated by
maximal paths,
ker ϕ = Impaths .
For brevity, we decided not to discuss the algorithmic properties of the ideal Impaths in this
text. However, the available nested polynomial representations of staged trees, as in (4) and (5)
and analysed by Görgen et al. (2018), provide a promising computational tool to find Impaths . This
is because using these, we can recursively relate extensions of path differences to the polynomials
t(v) for any v ∈ V.
20

Restricting our study to toric staged tree models in Section 5.2, we saw that the algebraic
characterisation of these is closely related to condition (⋆) which is necessary for paths to extend. In the context of decomposable graphical models, we know that the ideal of model invariants given by conditional independence statements is the toric ideal defining the kernel of the
associated parameterisation, and that moreover the generators of this ideal form a Gröbner basis.
In the analysis conducted in Section 6 of this paper, we saw that for decomposable models the
ideal Impaths is exactly the ideal obtained by Geiger et al. (2006) and that therefore its generators
form a Gröbner basis. In the toric model represented by the tree T>0 from Fig. 4d, we can see
that not only ker ϕ = Impaths but the binomial generators of Impaths form a Gröbner bases of the
ideal they generate. This leads is to state a variation of Theorem 16 for toric staged tree models.
Conjecture 17. Let T = (V, E) be a staged tree and suppose that condition (⋆) holds for all
vertices v, w ∈ V which are in the same stage. Then
ker ϕ = Impaths
and the generators of Impaths corresponding to path differences of maximal extensions form a
Gröbner basis of ker ϕ.
Acknowledgement
Part of this research was supported through the programme ‘Oberwolfach Leibniz Fellows’
by the Mathematisches Forschungsinstitut Oberwolfach in 2017 and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 314838170, GRK 2297 MathCoRe. All
of the computations in this paper have been carried out using the freely available software
Macaulay2 (Grayson and Stillman, 2017).
References
Altham, P. M. E., 1969. Exact Bayesian analysis of a 2 × 2 contingency table, and Fisher’s “exact” significance test. J.
Roy. Statist. Soc. Ser. B 31, 261–269.
Altham, P. M. E., 1970a. The measurement of association in a contingency table: three extensions of the cross-ratios and
metrics methods. J. Roy. Statist. Soc. Ser. B 31, 395–407.
Altham, P. M. E., 1970b. The measurement of association of rows and columns for an r × s contingency table. J. Roy.
Statist. Soc. Ser. B 32, 63–73.
Barclay, L. M., Collazo, R. A., Smith, J. Q., Thwaites, P., Nicholson, A., 2015. The dynamic chain event graph. Electronic
Journal of Statistics 9 (2), 2130–2169.
Barclay, L. M., Hutton, J. L., Smith, J. Q., 2013. Refining a Bayesian Network using a Chain Event Graph. International
Journal of Approximate Reasoning 54 (9), 1300 – 1309.
Collazo, R. A., Görgen, C., Smith, J. Q., 2018. Chain Event Graphs. Chapman & Hall.
Collazo, R. A., Smith, J. Q., 2015. A New Family of Non-Local Priors for Chain Event Graph Model Selection. Bayesian
Anal. 11 (4), 1165–1201.
Cowell, R. G., Dawid, A. P., Lauritzen, S. L., Spiegelhalter, D. J., 2007. Probabilistic networks and expert systems.
Statistics for engineering and information science. Springer, New York ; London.
Drton, M., Sturmfels, B., Sullivant, S., 2009. Lectures on algebraic statistics. Vol. 39 of Oberwolfach Seminars.
Birkhäuser Verlag, Basel.
Drton, M., Sullivant, S., 2007. Algebraic Statistical Models. Statist. Sinica 17 (4), 1273–1297.
Freeman, G., Smith, J. Q., 2011. Dynamic staged trees for discrete multivariate time series: Forecasting, model selection
and causal analysis. Bayesian Analysis 6 (2), 279–305.
Garcia Puente, L. D., Petrovic, S., Stillman, M., Sullivant, S., 2005a. GraphicalModels: A package for discrete and
Gaussian graphical models. Version 1.0.

21

Garcia Puente, L. D., Stillman, M., Sturmfels, B., 2005b. Algebraic geometry of Bayesian networks. J. Symbolic Comput.
39 (3-4), 331–355.
Garthwaite, P. H., Kadane, J. B., O’Hagan, A., 2005. Statistical method for eliciting probability distributions. J. Amer.
Statist. Assoc. 100 (470), 680–700.
Geiger, D., Heckerman, D., King, H., Meek, C., 2001. Stratified exponential families: graphical models and model
selection. Ann. Statist. 29 (2), 505 – 529.
Geiger, D., Meek, C., Sturmfels, B., 2006. On the toric algebra of graphical models. Ann. Statist. 34 (3), 1463–1492.
Görgen, C., 2017. An algebraic characterisation of staged trees: their geometry and causal implications. Ph.D. thesis,
University of Warwick, Department of Statistics.
Görgen, C., Bigatti, A., Riccomagno, E., Smith, J. Q., 2018. Discovery of statistical equivalence classes using computer
algebra. IJAR (forthcoming). Preprint available from arXiv:1705.09457v1 [].
Görgen, C., Smith, J. Q., 2017. Equivalence Classes of Staged Trees. Bernoulli (forthcoming). Preprint available from
arXiv:1512.00209v3 [].
Grayson, D. R., Stillman, M. E., 2017. Macaulay2, a software system for research in algebraic geometry. Available at
http://www.math.uiuc.edu/Macaulay2/.
Lauritzen, S. L., 1996. Graphical models. Vol. 17 of Oxford Statistical Science Series. The Clarendon Press, Oxford
University Press, New York, oxford Science Publications.
Pistone, G., Riccomagno, E., Wynn, H. P., 2001. Algebraic Statistics. Vol. 89 of Monographs on Statistics and Applied
Probability. Chapman & Hall/CRC, Boca Raton, FL, computational commutative algebra in statistics.
Shafer, G., 1996. The Art of causal Conjecture. Artificial Management. MIT Press, Cambridge.
Smith, J. Q., 2010. Bayesian decision analysis: principles and practice. Cambridge University Press, Cambridge; New
York.
Smith, J. Q., Anderson, P. E., 2008. Conditional independence and chain event graphs. Artificial Intelligence 172 (1),
42–68.
Sullivant, S., 2018. Algebraic Statistics. In preparation. http://www4.ncsu.edu/~ smsulli2/Pubs/asbook.html.

22

