Markov equivalence of marginalized local independence graphs
Søren Wengel Mogensen Niels Richard Hansen

	
	
		
		
		
		Marginalized local independence graphs
		
		
			
			
			
			[a]Department of Mathematical Sciences 
 University of 
			Copenhagen 

				Universitetsparken 5 

				DK-2100 Copenhagen Ø 

				Denmark 

				e1
			[b]Department of Mathematical Sciences 
 University of 
			Copenhagen 

				Universitetsparken 5 

				DK-2100 Copenhagen Ø 

				Denmark 

				e2
			
			S. W. Mogensen & N. R. Hansen
			
			University of Copenhagen
			
			This work was supported by VILLUM FONDEN (grant 
			13358).
		
			journalname
		
		
		[class=MSC]
			[Primary ]62M99
			[; secondary ]62A99
		
		
		
			directed mixed graphs
			independence model
			local independence
			local independence graph
			Markov equivalence
			μ-separation
		
		
		
Symmetric independence relations are often stu­di­ed using
graphical representations. Ancestral graphs or acyclic directed mixed graphs 
with
m-separation provide classes of symmetric graphical independence models that 
are closed
under marginalization. Asymmetric independence relations 
appear naturally for multivariate stochastic processes, for instance
in terms of local independence. However, no
class of graphs representing such asym­me­tric independence relations, which 
is also closed under marginalization, has been developed. We develop the theory 
of
directed mixed graphs with μ-separation and show that this provides a
graphical independence model class which is closed under marginalization and 
which gene­ra­lizes previously
considered graphical representations of local independence.

Several graphs may encode the same set of independence relations and this means 
that in many cases only an equivalence class of graphs can be identified from 
observational 
data. For statistical applications, it is therefore pivotal to characterize 
graphs that
induce the same independence relations. Our main result is that for directed 
mixed graphs
with μ-separation each equivalence class contains a maximal
element which can be constructed from the independence relations
alone. Moreover, we introduce the directed mixed equivalence graph as
the maximal graph with dashed and solid edges. This graph encodes all
information about the edges that is identifiable from the independence
relations, and furthermore it can be computed efficiently from the maximal 
graph.
		
		
		
	
	






§ INTRODUCTION


Graphs have long been used as a formal tool for reasoning with
independence models. Most work has been concerned with symmetric
independence models arising from standard probabilistic independence
for discrete or real-valued random variables.  However, when working
with dynamical processes it is useful to have a notion of independence
that can distinguish explicitly between the present and the past, and
this is a key motivation for considering local independence.

The notion of local independence was introduced for composable Markov processes 
by Schweder <cit.> who also gave examples of graphs describing 
local 
independence 
structures. Aalen <cit.> discussed how one could extend the 
definition of 
local independence in the broad class of 
semi-martingales using the Doob-Meyer decomposition. 
Several authors have since then used graphs to represent 
local 
independence 
structures of multivariate stochastic process models – in particular for 
point process models, see e.g. <cit.>. 
Local 
independence takes a dynamical point of view in the sense that it 
evaluates the dependence of the present on the past. This provides a natural 
link to statistical causality as cause must necessarily precede 
effect <cit.>. Furthermore, recent 
work argues that for some applications it can be important to consider
continuous-time
models, rather than only cross-sectional models, when trying to infer causal 
effects 
<cit.>.

Local independence for point processes has been applied for data ana­ly­sis, 
see 
e.g. 
<cit.>, but in applications a direct causal
interpretation may be invalid if only certain dynamical
processes are observed while other processes of 
the system under study are unobserved. Allowing for such latent
processes is important for valid causal inference, and this motivates our study
of representations of marginalized local 
independence graphs.

Graphical representations of independence models have also
been stu­died for time series <cit.>. In the time series context – using the
notion of Granger causality – Eichler <cit.> gave an algorithm for
learning a gra­phi­cal representation of local independence. However,
the equivalence class of graphs that yield the same local
independences was not identified, and thus the learned graph does not
have any clear causal interpretation. Related research has been
concerned with inferring the graph structure from subsampled time
series, but under the
assumption of no latent processes, see e.g. <cit.>.

In this paper, we 
give a 
formal, graphical framework for handling
the pre­sen­ce of unobserved processes and extend the work on graphical 
representations of local 
independence models by formalizing marginalization and giving results on the 
equivalence classes of such graphical representations. The graphical framework 
that we propose is a generalization of that of Didelez <cit.>. This development is 
analogous to work on 
margina­li­za­tions of graphical mo­dels using directed acyclic graphs, 
DAGs. 
Starting 
from a DAG, one can find graphs (e.g. maximal ancestral graphs or acyclic 
directed mixed graphs) that encode marginal independence models 
<cit.>. One can then 
characterize the equivalence class of graphs that yield the same
independence model <cit.> – the so-called Markov equivalent 
graphs – and construct learning 
algorithms to find such an
equivalence class from data. The purpose of this paper is to develop
the necessary theoretical foundation for learning local independence
graphs by developing a precise characterization of the learnable object: the
class of Markov equivalent graphs. 

The paper is structured as follows: in Section <ref> we discuss 
abstract independence models, relevant
graph-theoretical concepts, and the notion of local
independence and local independence graphs. In Section <ref>
we introduce μ-separation for directed mixed graphs, which will be
used to represent marginalized local independence graphs, and we
describe an algorithm to marginalize a given local independence
graph. In Sections <ref> and <ref> we
develop the theory of μ-separation for directed mixed graphs
further, and we discuss, in particular, Markov equivalence of such
graphs. All proofs of the main paper are given in the supplementary material. 
Sections <ref> to
<ref> are in the supplementary material.




§ INDEPENDENCE MODELS AND GRAPH THEORY



Graphical separation criteria as well as probabilistic models
give rise to abstract conditional independence statements. Graphical modeling is
essentially about relating graphical separation to probabilistic
independence. We will consider 
both as instances of abstract independence models. 

Consider some set 𝒮. An independence model,
ℐ, on 𝒮 is a set of triples (A,B,C) where
A,B,C∈𝒮, that is,
ℐ⊆𝒮×𝒮×𝒮. Mathematically, an independence model is a ternary
relation. In this paper, we will consider independence models over a finite set V which means that
𝒮 = 𝒫(V), the power set of V. In this case an
independence model  is a subset of
𝒫(V)×𝒫(V)×𝒫(V). We will
call an element
s ∈𝒫(V)×𝒫(V)×𝒫(V) an
independence statement and write s as
⟨ A,B | C⟩ for A, B, C ⊆ V. This
notation emphasizes that s is thought of as a statement about A
and B conditionally on C.

Graphical and probabilistic independence 
models have 
been studied in very general settings, though mostly under the assumption of 
symmetry of the independence model, that is,


    ABC∈⇒BAC∈,


see e.g. <cit.> and 
references 
therein. These works take an abstract axiomatic approach by describing and 
working with a number of 
properties that hold for e.g. models of conditional independence. In this 
paper, we consider independence models that do not 
satisfy the symmetry property as will become evident when we introduce the 
notion of local independence.



 §.§ Local independence



We consider a real-valued, multivariate stocha­stic process 

    X_t = (X_t^1, X_t^2, …, X_t^n),   t ∈ [0, T]

defined on a probability space
(Ω, ℱ, P). In this section, the process is a
continuous-time process indexed by a compact time interval. The case
of a discrete time index, corresponding to X = (X_t)
being a time series, is treated in Section <ref> in the supplementary 
material. We 
will later identify the coordinate processes of X with the nodes of a graph, 
hence, both are indexed by V = {1,2,…,n}. As illustrated in
Example <ref> below, the index set may be chosen in a more
meaningful way for a specific application. In that example, X_t^I
≥ 0 is a price process, X_t^L ∈ℕ_0 is a counting
process of events, and the remaining four processes take values in
{0,1} indicating if an individual at a given time is a regular
user of a given substance. Figure <ref> shows examples
of sample paths for three individuals. 

To avoid technical difficulties, irrelevant for the present paper, we
restrict attention to right-continuous processes with coordinates of finite and
integrable variation on the interval [0, T]. This includes most non-explosive 
multivariate counting processes as an important
special case, but also other interesting processes such as 
piecewise-deterministic Markov processes. 

To define local independence below we need a mathematical description
of how the stochastic evolution of one coordinate process depends
infinite­si­mally on its own past and the past of the other
processes. To this end, let ℱ_t^C,0 denote the 
σ-algebra generated by {X_s^α: s ≤ t, α∈ C}
for C⊆ V. For technical reasons we need to
enlarge this σ-algebra, and we define ℱ_t^C to be the completion of 
∩_s
  > tℱ_s^C,0 w.r.t. P. Thus (ℱ_t^C) is
a right-continuous and complete filtration  
which represents the history of the processes indexed by
C⊆ V until time t. Figure <ref> illustrates, in the 
context of 
Example
<ref>, the filtrations ℱ_t^V,
ℱ_t^{L, M, H}, and ℱ_t^{T, A, M, H}.

For β∈ V and C ⊆ V let Λ^C, β
denote an  ℱ_t^C-predictable process of finite and
integrable variation such that 

    E(X^β_t |ℱ^C_t) -   Λ_t^C, β
 
is an ℱ_t^C martingale. Such a process exists, see Section 
<ref> for the
technical details, and is usually called
the compensator or the dual predictable projection of
E(X^β_t |ℱ^C_t). It is in general unique up to
evanescence. 





	Let A,B,C ⊆ V. We say that X^B is 
	locally independent of X^A given X^C if there exists an 
	ℱ_t^C-predictable version of
        Λ^A ∪ C, β
        for all
        β∈ B. We use 
	A ↛B| C to denote that X^B is 
	locally 
	independent of X^A given X^C.
	



In words, the process X^B is locally independent of X^A given
X^C if, for each timepoint, the past up until time t of X^C
gives us the same predictable information about E(X^β_t |ℱ^A ∪ C_t) as the past of X^A∪ C until time t. Note
that when β∈ C, E(X^β_t |ℱ^C_t) =
X_t^β. 

Local independence was introduced by
Schweder <cit.> for composable Mar­kov processes and extended by 
Aalen
<cit.>. Local independence and graphical representations
thereof were later considered by Didelez
<cit.> and by Aalen et al. 
<cit.>. Didelez <cit.> also discussed local independence 
models of composable finite Markov processes under some specific types of 
margina­li­zation.
Commenges and Gégout-Petit <cit.> discussed 
definitions
of local independence in classes of semi-martingales. Note that
Definition <ref> allows a process to be separated from
itself by some conditioning set C, generalizing the definition used
by e.g. Didelez <cit.>.





Local independence defines the independence model

    = {ABC| X^B  is locally independent of  X^A 
     given  
    X^C }


such that the local independence statement A↛B| C is equivalent to ⟨ A,B| C⟩∈ in the abstract notation. 
We note that the local independence model is generally not symmetric. Using 
Definition <ref>, we introduce below an associated directed 
graph in 
which there is no directed edge from a node α to a node β if and 
only β is locally independent of α given V∖{α}. 


For the local independence model determined by X, we define the local 
	independence graph to be the directed graph, 𝒟, with nodes V 
	such that 
	for α,β∈ V

    α↛_𝒟β⇔α↛β| V∖{α}
				

where α↛_𝒟β denotes that there is 
no directed edge from α to β in the graph 𝒟. 

	

Didelez <cit.> gives almost the same definition of a local 
independence graph, however, in essence always assumes that there is a 
dependence of each process on its own past. See also Sections 
<ref> and <ref>.

The local independence graph induces an independence model by
μ-separation as defined below. The main goal of the present paper
is to provide a graphical representation of the induced independence
model for a subset of coordinate processes corresponding to the case where some
processes are unobserved. This is achieved by establishing a
correspondence, which is preserved under marginalization, between
directed mixed graphs and independence models induced via
μ-separation. We emphasize that the correspondence only relates
local independence to graphs when the local independence model
satisfies the global Markov property with respect to a graph. 

The local independence model satisfies the global Markov property with
respect to the local independence graph if every μ-separation in the graph 
implies a
local independence. This has been shown for point processes under some
mild regularity conditions <cit.> using the slightly
different notion of δ-separation. Section <ref>
discusses how δ-separation is related to μ-separation, and
Section <ref> shows how to translate the global Markov
property of <cit.> into our framework. Moreover, general
sufficient conditions for the global Markov property were given in
<cit.> covering point processes as well as certain
diffusion processes. Section <ref> provides, in addition, a
discussion of Markov properties in the context of time series. 

To help develop a better understanding of local independence and its
relevance for applications, we discuss an example of drug abuse progression.


[Gateway drugs]
	The theory of gateway drugs has been discussed for many years in the 
	literature on substance abuse <cit.>. In short, 
	the theory 
	posits that the use of “soft” and often licit drugs precedes (and 
	possibly 
	leads to) later 
	use of “hard” drugs.	Alcohol, tobacco, and marijuana have all been 
		discussed as candidate gateway drugs to “harder” drugs such as heroin.
	

		
	
	We propose a hypothetical, dynamical model of transitions into
        abuse via a gateway drug, and 
	more 
	generally, a model of substance abuse progression. Substance abuse is 
	known to be 
	associated with social 
	factors, genetics, and other individual and environmental factors 
	<cit.>. Substance abuse can evolve over time when an individual 
	starts or stops using some drug. In this example, we consider
	substance processes Alcohol (A), Tobacco (T), Marijuana (M), and Hard 
	drugs 
	(H) modeled as zero-one processes, that is, stochastic processes 
	that are piecewise constantly equal to zero (no substance use) or one 
	(substance use). We also include L, a process describing 
	life events, and a process I, which can be thought 
	of as an exogenous process that influences the tobacco consumption of 
	the individual,
	e.g. the price of tobacco which may change due to changes in tobacco 
	taxation. Let V = {A, T, M, H, L, I}.
	
	We will visualize each process as a node in a graph and draw
        an arrow from one process to another if the first has a direct
        influence on the second. We will not go into a full discussion
        of how to formalize “influence” in terms of a continuous-time causal 
        dynamical model as this would lead us astray, see instead
        <cit.>. The upshot is
        that for a (faithful) causal model, there is no direct influence if and 
        only if α↛β| V∖{α}, which identifies the “influence” graph with the
        local independence graph.
	
	
	Several formalizations of the gateway drug 
	question are possible. We 
	will focus on the questions “is the use of hard drugs locally independent 
	of use of alcohol for some conditioning set?” and “is the use of hard 
	drugs 
	locally independent of 
	the use of tobacco for some conditioning set?”. Using the dynamical nature 
	of local independence, we are asking if e.g. the past alcohol usage
	changes the hard drug usage propensity when accounting for the past of 
	all 
	other 
	processes in the model. This is one possible formalization of the gateway 
	drug question as a negative answer would mean that there exist some 
	gateway 
	processes through which any influence of alcohol usage on hard drug usage
	is mediated. If the visualization in Figure <ref> is indeed a 
	local independence graph in the above sense we see that 
	conditioning on all other processes, H is indeed locally independent of 
	A 
	and locally independent of T. In this hypothetical scenario we could 
	interpret this as marijuana in fact acting as a gateway drug to hard drugs. 
	If the global Markov property holds, we can furthermore use 
	μ-separation to obtain further local independences from the graph.
	We return to this example in Section <ref> to illustrate how 
		the 
		main results of the paper can be applied. In particular, we are 
		interested in what conclusions we can make when we do not observe all 
		the processes but only a subset.
				
		




 §.§ Marginalization and separability



Given an independence model ℐ over V, 
the marginal independence model over O⊆ V is 
defined as 

    ℐ^O = {⟨ A, B| C ⟩|⟨ A, B| C ⟩∈ℐ; A,B,C ⊆ O  }.



Marginalization is defined abstractly above, though we are primarily
interested in the marginalization of the independence model
encoded by a local independence graph via μ-separation. The main
objective is to obtain a graphical representation of such a
marginalized independence model involving only the nodes
O. To this end, we consider the notion of separability in an independence 
model. 


	Let ℐ be an independence model 
	over V. Let α, β∈ V. We say that β 
	is separable from α 
	if there exists C⊆ V∖{α} such that 
	αβC∈, and 
	otherwise we say that β is inseparable from α. We define
	
	
    s(β, ℐ) = {γ∈ V|β is 
    		separable from γ}.

	
	We also define u(β, ℐ) = V∖ 
	s(β, 
	ℐ).
	


We show in Proposition <ref> that if ℐ is the
independence model induced by a directed graph via μ-separation,
then α∈ u(β, ℐ) if and only if there is a directed edge 
from α to β. In this case the graph is thus directly
identifiable from separability properties of ℐ. That is,
however, not true in general for a marginalization of
ℐ, and this is the motivation for developing a theory of
directed mixed graphs with μ-separation.



 §.§ Graph theory



A graph, 𝒢 = (V,E), is an ordered pair where V is a finite set of 
vertices (also called nodes) and E is a finite set of edges. Furthermore, 
there is a map that to 
each edge assigns a pair of nodes (not necessarily 
distinct). We say that the edge is between these two nodes.
We consider graphs with two types of edges: directed (→) and
bidirected (↔). We can think of the edge 
set as a disjoint 
union, E = E_d  E_b, 
where E_d is a set of ordered pairs of nodes (α, β) 
corresponding to directed edges, and E_b is a set of 
unordered 
pairs of nodes {α, β} corresponding to bidirected
edges. This implies that the edge α↔β is 
identical to the edge β↔α, but the edge α→β is different from the edge β→α. It 
also implies that the graphs 
we consider can have multiple edges between a pair of nodes α and 
β, but they will always be a subset of the 
edges {α→β, α←β, α↔β}. 



	A directed mixed graph (DMG), 𝒢 = (V,E), is a graph with 
	node set V and edge set E consisting of directed and bidirected edges 
	as described above. 
	


Throughout the paper,  will denote a DMG with node set V
and edge set E. Occasionally, we will also use 𝒟 and 
ℳ to denote DMGs. We use 𝒟 only when the DMG is also a 
directed graph, that is, has no bidirected edges. We use ℳ to 
stress that some 
DMG is obtained as a marginalization of a DMG 
on 
a 
larger node set. We will use notation such as
↔_𝒢 or →_𝒟 to denote the 
specific
graph that an edge belongs to.

If α→β, we say that the edge has a 
tail at α and a head at β. Jointly tails and heads are 
called (edge) marks. An edge e∈ E between 
nodes α and β is a loop if α = β. We also say 
that the edge is incident with the 
node α and with the node β and that α and β are adjacent.

For α, β∈ V we use the notation α∼β to
denote a generic edge of any type between α and β. We use
the notation α *→β to indicate an edge that
has a head at β and may or may not have a head at
α. Note that the presence of one edge, α→β, say, does not in general
preclude the presence of other edges between these two nodes. Finally, α_𝒢β means
that there is no edge in  between α and β that has a
head at β and α↛_β means that there is no 
directed edge from α to β. Note that 
α↛_β is a statement about the absence of an edge in 
the graph  and to avoid confusion with local independence, 
α↛β| C, we 
always include the conditioning set when writing local independence statements, 
even if C = ∅ (see also Definition <ref>). 

We say that α is a parent of β in the graph
𝒢 if α→β is present
in 𝒢 and that β is a child of
α. We say that α is a sibling of β (and that
β is a sibling of α) if α↔β is
present in the graph. The motivation of the term sibling will be
explained in Section <ref>. We use pa(α) to denote the 
set of parents of α.
	
	
	
	
	A walk is an ordered, alternating sequence of vertices, γ_i, 
	and 
	edges, 
	e_j, denoted ω = ⟨γ_1, e_1, …, e_n, γ_n+1⟩, such 
	that 
	each e_i is between γ_i and γ_i+1, along with an 
	orientation of each directed loop along the walk (if e_i is
        a loop then we also know if e_i 
	points in the direction of γ_1 or in the direction of 
	γ_n+1).  Without the orientation, for instance the walks α→β→β→γ 
	and 
	α→β←β→γ would be 
	indistinguishable. See Figure 
	<ref> for examples.  We will often present the walk ω using the notation
	
	
    γ_1 e_1∼γ_2 e_2∼…e_n∼γ_n+1,

	
	where the loop orientation is explicit. We will omit
        the edge superscripts when they are not needed. 








        
	
	We say 
	that the walk ω contains 
	nodes γ_i and edges e_j. The length of the walk is n, the 
	number of 
	edges 
	that it contains. We define a trivial walk to be a 
	walk with no edges, and therefore only a single node. Equivalently, a 
	trivial 
	walk can be defined as a walk of length zero.  A subwalk
        of ω is 
	either 
	itself a 
	walk of the form ⟨γ_k, e_k, …, e_m-1, γ_m⟩ 
	where 1≤ k < m ≤ n+1 or a trivial walk ⟨γ_k ⟩, 
	1≤ k ≤ n+1.  
	A 
	(nontrivial) walk is 
	uniquely 
	identified 
	by its edges, and the ordering and orientation of these edges, hence the 
	vertices can be omitted 
	when describing the walk. At times we will omit the edges to simplify 
	notation, 
	however, we will always have a specific, uniquely identified walk in mind 
	even 
	when the edges and/or their orientation is omitted. The first and last 
	nodes of 
	a 
	walk are called endpoint nodes (these could be equal) or just endpoints, and we say 
		that a walk is between its 
		endpoints, or alternatively from its first node to its last 
		node. We call the walk ω^-1 = ⟨γ_n+1, e_n, …, e_1, γ_1 ⟩ 
		the inverse walk of ω. Note that the orientation of directed loops is also 
		reversed in the inverse walk such that they point towards γ_1 in 
		the inverse if 
		and only if they point towards γ_1 in the original walk. A 
		path is a walk on which no node is 
			repeated. 

Consider a walk ω and a subwalk thereof,
			⟨α, e_1, γ, e_2, β⟩, where 
			α,β,γ∈ 
			V and e_1, e_2∈ E. If e_1 and e_2 both have heads at 
			γ 
			then γ is a collider on ω. If this is not the 
			case, then 
			γ is a noncollider. Note that an endnode of a walk is 
			neither a 
			collider, nor a noncollider. We stress that the property of being 
			a 
			collider/noncollider is relative to a
                        walk (see also Figure <ref>).
			
			Let ω_1 = ⟨α, e_1^1,γ_1^1 …, 
			γ_n-1^1, e_n^1, 
			β⟩ and ω_2 = ⟨α, e_1^2,γ_1^2 …, 
			γ_m-1^2, e_m^2, β⟩ be two (nontrivial) walks. We say 
			that they are 
			endpoint-identical if e_1^1 and e_1^2 have the same mark 
				at α and 
				e_n^1 and e_m^2 have the same mark at β. Note that 
				this may depend on the orientation of directed edges in the two 
				walks. Assume that 
				some edge e is 
				between α and β. We say that the (nontrivial) 
				walk 
				ω_1 is 
				endpoint-identical to e if it is endpoint-identical to 
				the walk 
				⟨α, e, β⟩. If α = β and e 
				is directed this 
				should hold for just one of the possible orientations of e. 
				
				Let ω_1 be a walk between α and γ, and 
				ω_2 a walk 
				between γ and β. The composition of 
				ω_1 with 
				ω_2 is the walk that starts at α, traverses every 
				node and edge 
				of ω_1, and afterwards every node and edge of 
				ω_2, ending in 
				β. We say that we compose ω_1 with 
				ω_2.
				
				A directed path from α to β is a path 
				between α and 
				β consisting of edges of type → only 
				(possibly of length 
				zero) such that they all point in the direction of β. A 
				cycle is either a loop, or a (nontrivial) path from 
				α to 
				β composed with β∼α. 
				This means that in a cycle of length 2, an edge can be 
				repeated. A 
				directed 
					cycle is either a loop, α→α, or a 
					(nontrivial) 
					directed path from α to β 
					composed with β→α.
					For α∈ 
					V we let An(α) denote the set of ancestors, 
					that is,
					
					
    An(α) = {γ∈ V |there is a directed 
    					path 
    					from γ to α}.

					
					This is generalized to non-singleton sets 
					C⊆ V,
					
					
    An(C) = ∪_α∈ C An(α).

					
					We stress that C ⊆ An(C) as we allow 
					for trivial
					directed paths in the 
					definition of an ancestor. We use the notation 
					An_𝒢(C) if we wish 
					to emphasize in which graph 
					the ancestry is read, but omit the subscript when no 
					ambiguity arises.
					
					Let 𝒢 = (V,E) be a graph, and let O ⊆ 
					V. Define  the 
						subgraph induced by O to be the graph 
						𝒢_O 
						= (O, E_O) where 
						E_O⊆ E 
						is the set of edges that are between nodes in O. If 
						_1 = (V,E_1) and 
						_2 = (V,E_2), we will write _1 ⊆_2 
						to denote E_1 
						⊆ E_2 and say that _2 is a supergraph of _1.
						
						
						A directed graph (DG), 𝒟 = 
						(V,E), 
						is a graph with only 
						directed 
						edges. Note that this also allows directed loops. 
						Within a class of graphs, we 
						define the 
						complete graph to be the graph 
						which is the supergraph of all graphs in the class
						when such a graph 
						exists. For the class of DGs on 
						node set V, the complete graph is the graph 
						with edge set E = { (α,β) |α,β∈ V }.
						
									A directed acyclic graph (DAG) is a DG 
										with no loops
									and no directed cycles. An acyclic directed mixed graph (ADMG) is 
										a DMG with no loops and 
									no 
									directed cycles. 





§ DIRECTED MIXED GRAPHS AND SEPARATION



In this section we introduce μ-separation for DMGs which are then
shown to be closed under marginalization. In particular, we obtain a DMG 
representing the 
independence model arising from a local
independence graph via marginalization.  

The class of DMGs contains as a subclass the ADMGs that have no directed cycles
<cit.>.  ADMGs have been used to represent
marginalized DAG models, analogously to how we will use DMGs to
represent margina­lized DGs. ADMGs come with the
m-separation criterion which can be extended to DMGs, but this 
criterion differs 
in important ways from the μ-separation criterion introduced below. These 
differences also mean that our main result on Markov equivalence does not apply 
to e.g. DMGs with m-separation and thus our theory of Markov equivalence 
hinges on the fact that we are considering DMGs using the asymmetric notion of 
μ-separation. 



 §.§ μ-separation


We define μ-separation as a generalization of δ-sepa­ra­tion 
introduced by 
Didelez 
<cit.>, analogously to how m-separation is a gene­ralization of 
d-separation, see e.g. <cit.>. In Section 
<ref> we make the connection to Didelez's δ-separation 
exact 
and 
elaborate further on this in Section <ref>.


	A nontrivial walk 
    ⟨α,e_1,γ_1,…, 
    	γ_n-1,e_n,β⟩

	in  
	is said to be μ-connecting (or simply open) 
	from α to β 
	given C if α∉ C, every collider is in An(C), no 
	noncollider is in C, and e_n has a head at β.
	


When a walk is not μ-connecting given C, we say that it is closed 
or blocked by C. One should note that if ω is a μ-connecting 
walk from
α to β given C, the inverse walk, ω^-1, is not
in general μ-connecting from β to α given C. The requirement 
that a
μ-connecting walk be nontrivial, that is, of strictly positive
length, leads to the possibility of a node being separated from itself
by some set C when applying the following graph separation criterion to
the class of DMGs.

 Let A,B,C ⊆ V. We say that B is 
  μ-separated from A given C if there is no μ-connecting walk 
  from any α∈ A to any β∈ B given C and write 
  ABC, or write
  ABC if we want to stress to what graph the separation 
  statement applies.
 


The above notion of separation is given in terms of walks of which there are 
infinitely many in any DMG with a nonempty edge set. However, we will see that 
it is sufficient to consider a finite subset of walks from A to B 
(Proposition <ref>). 

Given a DMG, 𝒢 = (V,E), we define an 
independence model over 
V using 
μ-separation,


    ℐ(𝒢) = {⟨ A,B | C ⟩|ABC}.


Definition <ref> implies 
ABC 
whenever A ⊆ C and therefore () ≠∅.

Below we state two propositions that essentially both give equivalent ways of 
defining μ-separation. The propositions are useful when proving 
results on μ-separation models.


	Let α,β∈ V, C⊆ V. If there is a μ-connecting 
	walk from α 
	to β given C, then there is a μ-connecting walk from α 
	to β 
	that furthermore satisfies that every collider is in C.
	


 A route from α to β is a walk
  from α to β such that no node different from 
  β occurs more than
  once, and β occurs at most twice.


A route is always
a path, a cycle, or a composition of a path and a cycle that share
no edge and only share the vertex β.


  Let α, β∈ V, C⊆ V. If ω is a μ-connecting 
  walk
  from α to β given C, then there is a μ-connecting
  route from α to β given C consisting of edges in ω. 
	


If there is a μ-connecting walk from A to B given C, it does not in 
general follow 
that we can also find a μ-connecting path or cycle from A to B given 
C. As an 
example of this, consider the following DMG on nodes {α,β,γ}: 
α←β←γ.  There is a μ-connecting walk 
from α to β given ∅, and a μ-connecting route, but 
no μ-connecting path from α to β given 
∅.




 §.§ Marginalization of DMGs


Given a DG or a DMG, , we are interested 
in 
finding a graph that represents the marginal independence model over a node set 
O⊆ V, i.e., finding a graph ℳ such that


    ℐ(ℳ) = (ℐ(𝒢))^O.


It is well-known that the class of DAGs with d-separation is not closed under 
marginalization, 
i.e. for a DAG, 𝒟 = (V,E), and O 
⊊ V, it is not in general possible to find a DAG with node set O 
that encodes the same independence model among the variables in O as did the 
original graph. Richardson and Spirtes <cit.> gave a concrete 
counterexample and in 
Exam­ple <ref> we give a similar example to make the 
analogous point: DGs read with μ-separation are not closed under 
marginalization. In this example, we use the following proposition 
which gives a simple characterization of separability in DGs.


	Consider a DG, 𝒟 = (V,E), and let α, β∈ V. Then 
	β is μ-separable (see Definition <ref>) 
	from 
	α in 
	𝒟 if and only 
	if α↛_𝒟β.
	



	
	
	Consider the directed graph, 𝒢, in Figure <ref>. We wish 
	to show that it is not possible to encode the μ-separations among nodes 
	in 
	O={α,β,γ,δ} using a DG on these nodes only. To 
	obtain a contradiction, assume 
	𝒟 = 
	(O,E) is a DG such that 
	
	
    ABC𝒟⇔ABC

	
	
	for A,B,C ⊆ O. There is no C ⊆ O∖{α} such that αβC and no C ⊆ 
	O∖{β} such that βγC. If 
	𝒟 has the property (<ref>) then it follows 
	from Proposition <ref> that α→_𝒟β and β→_𝒟γ. However, 
	then γ is not μ-separated from α given 
	∅ in 𝒟. This shows that there exists no DG, 
	𝒟, that satisfies (<ref>).
	
	


We note that marginalization of a
probability model does not only 
impose conditional independence constraints on the observed variables but also 
so-called equality and 
inequality constraints, see e.g. <cit.> and references therein. In 
this paper, we will only be concerned with the graphical representation of 
local 
independence constraints, and not with representing analogous equality or 
inequality 
constraints.

In the remainder of this section, we first introduce 
the latent 
projection of a graph, see also
<cit.> and <cit.>, and then show
that it provides a marginalized DMG in the sense of 
(<ref>). At the end of the section, we give an algorithm 
for computing the latent projection of a DMG. 
This algorithm is an adapted version of one described by Sadeghi 
<cit.> for 
a 
different class of graphs. Koster <cit.> described a similar 
algorithm for ADMGs.




	Let 𝒢 = (V,E) be a DMG, V = M  O. We define the latent projection of  on O to be the DMG (O, D) such that α∼β∈ D if and only 
	if 
	there exists an endpoint-identical (and nontrivial) walk between α 
	and β in 
	 
	with no colliders and such that every non-endpoint node is in M. Let 
	m(, O) denote the latent projection of  on O.


The definition of latent projection motivates the graphical term sibling 
for 
DMGs, as 
one way to obtain an edge α↔β is through 
a latent projection of 
a larger graph in which α and β share a parent.

To characterize the class of graphs obtainable from a DG via a latent
projection, we introduce the canonical DG of the DMG
  𝒢, 𝒞(𝒢), as follows: for each (unordered) 
  pair of nodes {α, β}⊆ V  such that
α↔_𝒢β, add a distinct auxiliary node,
m_{α, β}, add edges
m_{α, β}→α, m_{α, β}→β to E, and then remove all
bidirected edges from E. If 
𝒟 
is any DG, then
ℳ = m(𝒟, O) will satisfy


    α↔_ℳβ⇒α↔_ℳα for all α,β∈ O


for all subsets of vertices O. Conversely, if = (V, E) is a 
DMG that satisfies 
(<ref>), then 𝒢 is the latent projection of its
canonical DG; m(𝒞(𝒢), V) = 𝒢. The class of DMGs 
that satisfy (<ref>) is closed under marginalization (Proposition 
<ref>) and has certain regularity properties (see e.g. 
Proposition <ref>). These result provide the 
means for graphically representing marginals of local independence graphs. However, the theory that leads to our 
main results on Markov equivalence does not require the property 
(<ref>) and therefore we develop it for general DMGs.


	Let O ⊆ V.  The graph 
	ℳ = m(𝒢, O) is a DMG. If  satisfies 
	(<ref>), 
	then 
	ℳ does as well.
	




	Assume that 𝒢 satisfies (<ref>) and let α∈ 
	V. 
	Then 
	α has no loops if and only if ααV∖{α}.
	


We also observe directly from the definition that the latent
projection operation preserves ancestry and non-ancestry in the
following sense.


	Let O ⊆ V, ℳ = 
	m(𝒢, O) and α, β∈ O. Then α∈ 
	An_𝒢(β) if and only if α∈ An_ℳ(β).
	


The main result of this section is the following theorem, which 
states that the marginalization defined by the latent 
projection operation preserves the marginal independence model encoded by a 
DMG. 


	Let O ⊆ V, ℳ = 
	m(𝒢, 
	O). Assume A,B,C 
	⊆ O. Then
	
	
    ABC⇔ABCℳ.

	






 §.§ A marginalization algorithm


We describe an algorithm to compute the latent projection of a graph on some 
subset of nodes. For this purpose, we define a triroute, θ, to be 
a walk of length 2, 
	⟨α, e_1, γ, e_2, β⟩, such that γ≠α, 
	β. We suppress e_1 and 
	e_2 from the notation and use _θ(α,γ, β) 
	to 
	denote the 
	triroute. We say that a triroute is colliding if 
	γ is a 
	collider on θ, and otherwise we say that it is noncolliding. This is analogous to the concept of a tripath 
		(see e.g. <cit.>), but allows for α = β.


 Define 
Ω_M() to be the set 
of noncolliding 
triroutes _θ(α, m, β) such that m∈ M and such 
that an 
endpoint-identical edge α∼β is not present in 
𝒢.




	Algorithm <ref> outputs the latent projection of a DMG.
	




§ PROPERTIES OF DMGS





	Let _1=(V,E_1) and _2=(V,E_2) be DMGs. We say 
	that _1 and _2 are Markov equivalent if 
	ℐ(𝒢_1) = ℐ(𝒢_2). This defines an 
	equivalence relation and we let 
	[𝒢_1] denote the (Markov) equivalence class of 𝒢_1.


[Markov equivalence in DGs]
	Let 𝒟 = (V,E) be a DG. There is a directed edge from α 
	to 
	β if and only if β cannot be separated from α by any set 
	C⊆ V ∖{α} (Proposition <ref>). This 
	implies that two DGs are Markov 
	equivalent if and only if they are equal. Thus, in the restricted class of 
	DGs, every Markov equivalence class is a 
	singleton and in this sense identifiable from its induced 
	independence model. However, when 
	considering Markov equivalence in the more general class of DMGs not every 
	equivalence class of a DG is a singleton as the DG might be Markov 
	equivalent to a DMG. As an example of this, consider the complete DG 
	on a node set V which is Markov 
	equivalent to the complete DMG on V.



	We say that  is maximal if it is complete, or 
	if
	any added edge changes the induced independence model 
	().
	




 §.§ Inducing paths


Separability of nodes can be 
stu­died using the concept of an inducing path which has also been 
used in
other classes of graphs 
<cit.>. In the context of DMGs and 
μ-separation, it is 
natural to define several types of inducing paths due to the asymmetry of 
μ-separation and the possibility of directed cycles in DMGs.


	An inducing path from α to β is a 
	nontrivial 
	path or cycle, π = ⟨α,…,β⟩, which has a 
	head at β and 
	such 
	that 
	there are no noncolliders on π and every node is an 
	ancestor of α or β.
	The inducing path π is bidirected if every edge on π is 
	bidirected. If π is not bidirected, it has one of the forms α→β or
	
	
    α→γ_1 ↔…↔γ_n 
    	↔β.

	
	and we say that it is unidirected. If, furthermore,
	γ_i 
	∈ 
	An(β) 
	for all i=1,…,n (or it is on the form α→β) 
	then we say that it is directed.


Note that an inducing path is by 
definition 
either a path or a cycle. An inducing path is either bidirected or unidirected. 
Some unidirected indu­cing paths are also directed. Propositions 
<ref> 
and <ref> show how bidirected and directed inducing paths in a 
certain sense correspond to bidirected and directed edges, respectively.


		


	Let ν be an inducing path from α to β. The following holds 
	for any C 
	⊆ V ∖{α}. If α≠β, then there exists
	a μ-connecting path from α to β given C. If α = 
	β then there exists a μ-connecting cycle 
	from α to β 
	given C. We call such a path or cycle a ν-induced open path or cycle, respectively, or simply a
      ν-induced open walk to cover both the case 
	α=β and the case α≠β. If the 
	inducing path is bidirected or directed, then the 
	ν-induced open walk is endpoint-identical to the inducing path.
	


The following corollary is a direct consequence of Proposition
<ref>, show­ing that β is inseparable from
α if there is an inducing path from α to β irrespectively
of whether the nodes are adjacent. 


	Let α,β∈ V. If there 
	exists an inducing path from α to β in , then 
	β is not μ-separated from α given C for any C⊆ 
	V∖{α}, that is, α∈ u(β,
        ℐ(𝒢)).  
	


The following two propositions  show that for two of the three types
of inducing paths there is a Markov equivalent supergraph in which the
nodes are adjacent. This illustrates how one can easily find
Markov equivalent DMGs that do not have the same adjacencies.
Example <ref> shows that for a unidirected inducing path
it may not be possible to add an edge without changing the
independence model.


	If there exists a bidirected inducing path from α to β in 
	, then adding α↔β in 𝒢 does not 
	change the independence model.
	




	If there exists a directed inducing path from 
	α to β in , then adding α→β in 
	 does not change the independence model.
	


 We say 
 that nodes α and β are collider-connected if there exists a nontrivial walk between
 α and β such that every non-endpoint node is a 
 collider on the
 walk. We say that α is directedly collider-connected to
 β if α and β are collider-connected by a
 walk with a head at β.


	Let α,β∈ V. We define the set 
	
    D(α,β) = {γ∈ An(α,β)|γ is directedly
    	collider-connected to β}∖{α}.



Note that if α↛_β, then pa(β)
⊆ D(α,β), and if the graph is furthermore a directed graph 
then pa(β)
= D(α,β).


	If there is no inducing path from α to β in , then 
	β 
	is separated from α by D(α,β).
	


[Inducing paths]
Consider the DMG 
on nodes {α,γ} and with a single edge γ→α. In this case, there is no inducing path from α to 
α and α is μ-separated from α by D(α, α) = 
{γ}. Now add the edge α↔γ. In this new
DMG, there is an inducing path from α to α and therefore α 
is inseparable from itself.


[Non-adjacency of inseparable nodes in a maximal DMG]

		

	
	Consider the DMG in Figure <ref>. One can show that this DMG is 
	maximal (Definition <ref>).
	There is an inducing path from β to δ making δ 
	inseparable from β, yet no arrow can be 
	added 
	between β and 
	δ without changing the independence model. This example illustrates 
	that maximal 
	DMGs 
	do not have the property that inseparable nodes are adjacent. This is 
	contrary to MAGs which form a subclass of ancestral graphs and have this
	exact property <cit.>.
	




§ MARKOV EQUIVALENCE OF DMGS



The main result of this section is that each Markov equivalence class of DMGs 
has a greatest element, that is, an element which is a supergraph of all other 
elements. This fact is helpful for understanding and graphically representing 
such equivalence classes, and potentially also for 
constructing learning algorithms. We will prove this result by arguing that the 
independence model of a DMG, = (V,E), defines for each node 
α∈ V a set of potential parents and a set of potential 
siblings. We then construct the greatest element of [] by simply 
using these sets, and argue that this is in fact a Markov equivalent 
supergraph. As we only use the independence model to define the sets of 
potential parents and siblings, the supergraph is identical for all members of 
[], and thus a greatest element. Within the equivalence class, the greatest 
element is also the only maximal element, and we will refer to it as 
the maximal element of the equivalence class.



 §.§ Potential siblings



	Let  be an independence model over V and let α, β∈ V. 
	We say that α and β are potential siblings in  if (s1)–(s3) hold:
	
	
		
  * β∈ u(α, ℐ) and 
		α∈ u(β, ℐ),
		
  * for all γ∈ V, C ⊆ V such that β∈ C,
		
    γαC∈⇒γβC∈,

		
  * for all γ∈ V, C ⊆ V such that α∈ C,
		
    γβC∈⇒γαC∈.

	
	


Potential siblings are defined abstractly above in terms of the
independence model only. The following proposition gives a useful
characterization for graphical independence models by simply contraposing 
(s2) and (s3). 


	Let () be the independence model induced by . Then
	α, β∈ V are potential siblings if and only if (gs1)–(gs3) 
	hold: 
	
	
		
  * β∈ u(α, ℐ()) and 
		α∈ u(β, ℐ()),
		
  * for all γ∈ V, C ⊆ V such that β∈ C: 
		if there exists a μ-connecting walk from γ to β given 
		C, then there exists a μ-connecting walk from γ to 
		α given C,
		
  * for all γ∈ V, C ⊆ V such that α∈ C: 
		if there exists a μ-connecting walk from γ to α given 
		C, then there exists a μ-connecting walk from γ to 
		β given C.
	
	



	Assume that α↔β is in 𝒢. Then 
	α and 
	β are potential 
	siblings in (). 
	



	Assume that α and β are potential siblings in 
	ℐ(𝒢). Let 𝒢^+ denote the DMG obtained 
	from 𝒢 by adding α↔β. Then 
	ℐ(𝒢) = ℐ(𝒢^+).
	


The above shows that if α and β are potential siblings in () 
then there exists a supergraph, ^+, which is Markov equivalent with  such 
that α and β are siblings in ^+. This motivates the term 
potential siblings.



 §.§ Potential parents


In this section, we will argue that also a set of potential parents are 
determined by the independence model. This case is slightly more involved for 
two reasons. First, the relation 
is asymmetric, as for each potential parent edge there is a parent node and a 
child node. Second, adding directed edges potentially changes the ancestry of 
the graph.



	Let  be an independence model over V and let α, β∈ V. 
	We say that α is a potential parent of β in  if 
	(p1)–(p4) hold:

	
		
  * α∈ u(β, ℐ),
		
  * for all γ∈ V, C ⊆ V such that α∉ 
		C,
		
    γβC∈⇒γαC∈,

		
  * for all γ,δ∈ V, C ⊆ V such that 
		α∉ C, β∈ C,
		
    γδC∈⇒γβC∈αδC∈ ,

		
  * for all γ∈ V, C⊆ V, such that 
		α∉ C,
		
    βγC∈⇒βγC ∪{α}∈.

	
	



	Let () be the independence model induced by . Then 
	α∈ V is a potential parent of β∈ V if and only if 
	(gp1)–(gp4) 
	hold: 
	
	
		
  * α∈ u(β, ℐ()),
		
  * for all γ∈ V, C ⊆ V such that α∉ 
		C: if there exists a μ-connecting walk from γ to α 
		given C, then there exists a μ-connecting walk from γ to 
		β given C,
		
  * for all γ,δ∈ V, C ⊆ V such that 
		α∉ C, β∈ C: if there exists a μ-connecting walk 
		from γ to β given C and a μ-connecting walk from 
		α to δ given C, then there exists a μ-connecting 
		walk from γ to δ given C,
		
  * for all γ∈ V, C⊆ V, such that 
		α∉ C: if there exists a μ-connecting walk from β 
		to γ given C ∪{α}, then there exists a 
		μ-connecting walk from β to γ given C.
	
	



	Assume that α→β is in 𝒢. Then α 
	is a 
	potential parent of β in ℐ(𝒢). 
	



	Assume that α is a potential parent of β in 
	ℐ(𝒢). Let 𝒢^+ denote the DMG obtained 
	from 𝒢 by adding α→β. Then 
	ℐ(𝒢) = ℐ(𝒢^+).
	





 §.§ A Markov equivalent supergraph


Let 𝒢 = (V,E) be a DMG. Define 
𝒩(ℐ(𝒢)) = (V,E^m) to 
be the DMG with edge set E^m = E^d ∪ E^b where E^d is a set of 
directed edges and E^b a set of bidirected edges such that the directed edge 
from α to β is in E^d if and only if α is a potential 
parent of β in ℐ(𝒢) and the bidirected edge between 
α 
and β is in E^b if and only if α and β are potential 
siblings in ℐ(𝒢).


	Let 𝒩 = 
	𝒩(ℐ(𝒢)). Then 𝒩∈ 
	[𝒢] and 𝒩 is a supergraph of all elements of 
	[𝒢]. Furthermore, if we have a finite sequence of DMGs
	𝒢_0, 𝒢_1, …, 𝒢_m, 𝒢_i = 
	(V,E_i), such that 𝒢_0 = 𝒢, 𝒢_m = 
	𝒩, and E_i ⊆ E_i+1 for all i =0, …, m -1, 
	then _i is Markov equivalent with 𝒩 for all i =0, …, 
	m -1.
	


The graph 𝒩 in the above theorem is a supergraph of every Markov 
equivalent DMG and therefore maximal. On the other hand, every maximal DMG is 
a representative of its equivalence class, and also a supergraph of all Markov 
equivalent DMGs. This means that we can use the class of maximal DMGs to obtain 
a unique representative for each DMG equivalence 
class.

Lemmas <ref> and <ref> show that conditions 
(gs1)–(gs3) and (gp1)–(gp4) are sufficient to Markov equivalently add a 
bidirected or a directed 
edge, respectively. The conditions are also necessary in the sense that for 
each 
condition one can find example graphs where only a single condition is violated 
and 
where the larger graph is not Markov equivalent to the smaller graph.

We can note that α is a potential parent and a potential sibling of 
α if and only if α∈ u(α, ()). This means that in 
𝒩(ℐ(𝒢)) for each node either both a directed 
and a bidirected loop is present or no loop at all.




 §.§ Directed mixed equivalence graphs



Theorem <ref> suggests that one can represent an equivalence class 
of DMGs by displaying the maximal element and then 
simply indicate which edges are not present for all members of the 
equivalence class.


	Let 
	𝒩 = (V,F) be a maximal DMG. 
	Define 
	F̅⊆ F such that for e∈ F we let e∈F̅ if and only if there exists a DMG 𝒢 = 
	(V,F̃) such that ∈ [𝒩] and e∉F̃. 
	We call 
	𝒩' = (V,F,F̅) a directed mixed equivalence graph 
	(DMEG). When visualizing 𝒩', we draw 𝒩, but use 
	dashed edges 
	for the set F̅, see Figure <ref>.
	


Let 𝒩' = 
(V,F,F̅) be a DMEG.  The 
DMG (V,F) is in the equivalence class represented by 𝒩'. However, 
one cannot necessarily remove any subset of F̅ and obtain a member of 
the Markov equivalence class (see Fi­gu­re <ref>). Moreover, an 
equivalence class does not in general contain a 
least 
element, that is, an element which is a subgraph of all Markov equivalent 
graphs.

We will throughout this section let 𝒩 = (V,F) be a maximal DMG. For 
e∈ F we will use 𝒩 - e to denote the graph (V, F∖{e}). Assume that we have a maximal DMG
from which we wish to derive the DMEG. Consider some 
edge 
e∈ F. If 𝒩 - e ∈ [𝒩], then e∈F̅ as there exists a Markov 
equivalent subgraph of 𝒩 in which e is not present. On the other 
hand, if 𝒩 - e ∉ [𝒩] then we note that 
𝒩 - e is the largest subgraph of 𝒩 that does not 
contain 
e. Let 𝒦 be a subgraph of 𝒩 that does not contain 
e. 
Then ℐ(𝒩) ⊊ℐ(𝒩 - e) 
⊆ℐ(𝒦). Using Theorem <ref>, we know that all 
𝒩-Markov equivalent DMGs are in fact subgraphs of 𝒩, 
and using that 𝒦 is not Markov equivalent to 𝒩 we see 
that all graphs in [𝒩] must contain e. This 
means that when 𝒩 - e ∉ [𝒩] then e∉F̅ 
as 
e must be present in all Markov equivalent DMGs.

Any loop should in principle be dashed when drawing a DMEG as for each 
node in 
a maximal DMG either both the 
directed and the bidirected loop is present or neither of 
them. However, we choose to not present them as dashed as if they are present 
in the maximal DMG, then at least one of them 
will be present in any Markov equivalent DMG satisfying (<ref>), 
that 
is, for any DMG which is a marginalization of a DG. In addition we only draw 
the 
directed 
loop 
to not overload the visualizations.



	





 §.§ Constructing a directed mixed equivalence graph



When constructing a DMEG from 𝒩 it suffices 
to consider 
the graphs 𝒩 - e for each e∈ E and 
determine if 
they are Markov equivalent to 𝒩 or not. A brute-force approach 
to 
doing so is to simply check all separation statements in both graphs. 
However, one can make a considerably more 
efficient algorithm.


	Assume αe→_𝒩β. It holds that 𝒩 - e 
	∈ 
	[𝒩] if and only if α∈ 
	u(β, ℐ(𝒩 - e)).
	




	Assume αe↔_𝒩β. Then 
	𝒩 - e 
	∈ 
	[𝒩] if and only if α∈ u(β, (𝒩 - e)) 
	and β∈ u(α, (𝒩 - e)).
	


We can now outline a two-step algorithm for constructing the DMEG from an 
arbitrary 
DMG, . We first construct the maximal Markov equivalent graph, 
𝒩. We know 
from Theorem 
<ref> that one can simply check if each pair of nodes are potential 
siblings/parents in the independence model induced by  and construct the 
maximal 
Markov equivalent graph directly. This may, however, not be computationally 
efficient.

The above propositions show that given the maximal DMG, one can efficiently 
construct the DMEG by 
evaluating separability once for each directed edge and 
twice for each bidirected edge. 
Using Proposition <ref> one can determine separability by testing 
a 
single separation statement, and this 
means that starting from 𝒩,  one can construct the 
corresponding DMEG 
in a way such that the number of 
separation 
statements to test scales linearly in the 
number of edges in 𝒩.



		

[Gateway drugs, continued]
	We return to the model in Example <ref> to consider what happens 
	when it is only partially observed and to give an interpretation 
	of the corresponding local independence model. The local
        independence graph is assumed to be as depicted on Figure
        <ref>, left. 
	
	Consider first the situation where L and I are
        unobserved. In this case, under the faithfulness assumption of the full 
        model (Definition
       <ref>) we can construct
        the DMEG, which is shown in the center panel of Figure
        <ref>, from the local independence model. The DMEG
        represents the Markov equivalence class which we can infer from
        the marginal local independence model (L and I are
        unobserved). Theoretically, the inference requires an oracle to
        provide us with local independence statements, which will in
        practice have to be approximated by statistical tests. What is
        noteworthy is that the DMEG can be inferred from the
        distribution of the observed variables only, and we do not
        need to know the local independences of the full model. 

        If we ignore which edges are dashed and
        which are not, the graph simply represents the local
        independence model of the marginal system as the maximal
        element in the Markov equivalence class. The
        dashed edges give us additional – and in some sense local –
        information. As an example, the directed edge from A to H is
        dashed and we cannot know if there exists a conditioning set
        that would render H locally independent of A in the full
        system. On the other hand, the directed edge from 
        T to H is
        absent, and we can conclude that tobacco use is not directly affecting
        hard drug use.
	
	Consider instead the situation where I is also observed. I serves as an 
	analogue to an instrumental variable (see e.g. <cit.> for an 
	introduction to instrumental variables). The 
	inclusion of this variable identifies some of the structure by removing 
	some dashed edges and making others non-dashed.		





§ DISCUSSION AND CONCLUSION



In this paper we introduced a class of graphs to represent local 
independence structures of partially observed multivariate stochastic 
processes. Previous work 
based on 
directed graphs, that allows for cycles and use the asymmetric 
δ-separation criterion,
was extended to mixed directed graphs to account for latent processes and we 
introduced μ-separation in mixed directed
graphs.

An important task is the characterization of equivalence classes of graphs and 
this has been studied for e.g. MAGs <cit.>. In the case of 
MAGs, a key result 
is that every element in a Markov equivalence class has the same skeleton, i.e. the same adjacencies <cit.>. As shown by 
Propositions 
<ref> 
and <ref> this is not the case for DMGs, and Example 
<ref> shows that one cannot necessarily within a Markov equivalence 
class find an element such that two nodes are inseparable if and only if 
they are adjacent.

We proved instead a central maximality property 
which allowed us to propose the use of DMEGs to represent a Markov 
equivalence class of DMGs in a concise 
way. Given a maximal DMG, 
we furthermore argued that one can efficiently find 
the DMEG. Similar results are known for chain graphs, as one can also 
in a certain sense find a unique, largest graph represen­ting a Markov 
equivalence 
class <cit.>, though this graph is not a supergraph of all 
Markov equivalent graphs 
as 
in the case of DMGs. Volf and Studený <cit.> suggested to use 
this largest graph as 
a unique representative of the Markov equivalence class, and they provided an 
algorithm to construct it. 

We emphasize that the characterization given of the maximal element of a Markov 
equivalence class of DMGs
is constructive in the sense that it straightforwardly defines an algorithm 
for 
learning a maximal DMG from a local independence oracle. This learning 
algorithm may not be computationally efficient or even
feasible for large graphs, and it is ongoing research to develop 
efficient learning algorithms and to develop the practical
implementations of the tools needed for replacing the oracle by
statistical tests.




§ ACKNOWLEDGMENTS


This work was supported by a research grant from VILLUM FONDEN (13358). The 
authors are grateful to Steffen Lauritzen for his helpful comments and 
suggestions. We also thank two referees and an area editor whose comments have 
helped improve this manuscript.











	Supplementary material







			In this supplementary material we discuss
			relations between μ-separation and other asymmetric 
			notions of graphical separation. We also compare our 
			proposed definition of local independence to previous 
			definitions to argue that ours is in fact a 
			generalization. We furthermore relate μ-separation
			to m-separation. We provide, in particular,
			a detailed discussion of the local
			independence model for discrete-time stochastic
			processes (time series), and we show how to
			verify μ-separation via separation in an
			auxiliary undirected graph. We also
			discuss the existence of the compensators that
			are used in the definition of local
			independence for continuous-time stochastic
			process models. This supplementary material also 
			contains proofs of the results of the main paper.
			
			
			
			
			
			

§ RELATION TO OTHER ASYMMETRIC NOTIONS OF GRAPHICAL 
				SEPARATION

			
			
			In this section we relate μ-separation to δ-separation as
			introduced previously in the literature for directed graphs.
			
			
			
				Let 𝒢 = (V,E_d) be a DG, and let B⊆ V. 
				The 
				B-bereaved graph,
				𝒢^B, is constructed from 𝒢 by
				removing every directed edge with a tail at a node in B 
				except loops. More
				precisely, 𝒢^B = (V, E̅_d^B),
				where E̅_d^B = E_d ∖(⋃_β∈ B{(
				β, δ
				) |δ≠β}).
				
			
			
			Didelez <cit.> considered a DG, and for disjoint 
			sets 
			A,B,C⊆ V said that B is 
			separated 
			from A by C if there is no μ-connecting walk in 
			𝒢^B, or 
			equivalently, no μ-connecting path. This 
			is called 
			δ-separation. Note that the condition in Definitions 
			<ref> 
			and <ref> that 
			a 
			connecting walk be nontrivial makes no difference now due to A 
			and B being 
			disjoint. The condition that a μ-connecting walk ends with a 
			head at 
			β∈ B is also obsolete as we are evaluating separation in 
			the bereaved 
			graph ^B. Didelez <cit.> always assumed that a 
			process depended 
			on its own past, and thus did not visualize loops in the DGs as a 
			loop would 
			always be present at every node.
			
			Meek <cit.> generalized δ-separation to 
			δ^*-separation 
			in a 
			DG (allowing for loops)
			by considering only nontrivial μ-connecting walks in 
			𝒢^B for sets A,B,C⊆ V such that A∩ C = 
			∅ 
			with the motivation that a 
			node can be separated from itself using this notion of separation. 
			However, 
			if we consider the
			graph α→β, and sets
			A = {α}, B = {α, β}, C = ∅, then 
			using 
			δ^*-separation, B is separated from A given C, which 
			runs 
			counter to an intuitive understanding of separation. More 
			importantly,
			δ^*-separation in the local independence graph will not
			generally imply local independence. 
			
			To establish an exact relationship between δ- and 
			μ-separations 
			and argue 
			that we are indeed proposing a generalization of the former, assume 
			that  
			is 
			a DG and that A,B,C 
			⊆ V are disjoint. We will argue that
			
			
    ABC∪ B⇔ABC.

			
			To see that this is the case, consider first a 
			δ-connecting walk from α∈ A to β∈ B given 
			C in 
			𝒢^B, ω. The subwalk from α to the first 
			node on 
			ω which is in B 
			is also present and μ-connecting given C ∪ B in 
			𝒢. On the other hand, assume that there 
			exists a μ-connecting sequence, ω, in 𝒢. We 
			know that 
			A∩ B = ∅, and because B is a 
			subset of 
			the conditioning set on the left hand side in 
			(<ref>), we 
			must have that the first time the path enters B, 
			it has a head at the node in B, and this implies that a subwalk 
			of ω  
			is δ-connecting, that is, present and connecting in ^B. 
			In Section 
			<ref> we will discuss why B 
			is included in the conditioning set on the left side of 
			(<ref>).
			
			
			

§ MARKOV PROPERTIES

			
			
			The equivalence of pairwise and global Markov properties is pivotal 
			in much of 
			graphical modeling. In this section, we will show how our proposed 
			graphical 
			framework fits with known results on Markov properties in the 
			case of point processes and argue that our graphical framework is a 
			generalization 
			of that of 
			Didelez <cit.> to allow for non-disjoint sets and 
			unobserved 
			processes.
			
			
				Let  be 
				an independence model over V. We say that 
				 satisfies the pairwise Markov property with respect 
				to 
				the DG 𝒟 if 
				for all α, 
				β∈ V,
				
				
    α↛_𝒟β⇒αβV∖{α}∈.

				
			 
			
			
			
				Let A,B,C ⊆ V. Let  be an 
				independence model over V. We 
				say that  satisfies the global Markov property with 
				respect 
				to the DMG 
				 if 
				() ⊆, i.e., if
				
				
    ABC⇒ABC∈.

				
			 
			
			Didelez <cit.> only considered disjoint sets and gave a 
			slighty 
			different 
			definition of local independence. For disjoint sets, Didelez 
			<cit.> 
			defined
			that B is locally independent of A given C if 
			
			
    A ↛B | C ∪ B,

			
			and we will make the relation between the two definitions 
			precise in 
			this section. Consider sets 𝒮,𝒮_d ⊆𝒫(V) ×𝒫(V) ×𝒫(V), 
			
			
    𝒮_d     = 
    			{(A, B, C) | A,B,C  disjoint, A,B  non-empty}
    𝒮    = 
    			{(A, B, C) | B⊆ C,  A,C  disjoint, A,B  
    				non-empty}

			
			and the bijection s: 𝒮_d →𝒮, 
			s((A,B,C)) = 
			(A,B, 
			C∪ B). We will in this section let  denote a subset of
			𝒮 and let ^d denote a subset of
			𝒮_d. In Section <ref> we argued that for 
			any 
			directed graph  and (A,B,C) ∈𝒮_d,
			
			
    ABC   ⇔ABC∪ B

			
			and therefore
			
			
    { (A,B,C) ∈𝒮_d : ABC} = s^-1( { 
    			(A,B,C) 
    			∈𝒮 : ABC}).

			
			For any local independence model defined by Didelez's 
			definition, 
			^d, and 
			any local independence model defined by Definition 
			<ref>, , it holds that
			
			
    ⟨ A,B| C⟩∈^d    ⇔ A↛B| 
    			C∪ B 
       ⇔⟨ A,B| C∪ B⟩∈

			
			so ^d = s^-1(). Hence, there is a bijection between the two sets, and graphical 
			and 
			probabilistic independence models are preserved under the 
			bijection. This means 
			that we have equivalence of Markov properties between 
			the two formulations. Thus, restricting our framework to 
			𝒮, we 
			get the equivalence of pairwise and global 
			Markov property directly from the proof by Didelez in the case of 
			point process 
			models, and we see that our seemingly dif­fe­rent definitions of 
			local 
			independence and graphical separation indeed give an extension of 
			earlier 
			work.
			
			One can show that for two DMGs _1, _2, that both have all 
			directed 
			and bidirected loops it holds that
			
			
    (_1) ∩𝒮 = (_2) ∩𝒮⇔(_1) = (_2).

			
			Let 𝔾 denote the class of DMGs such that 
			all directed 
			and bidirected loops are present. Consider now some 𝒢∈𝔾. By the above result we can identify the Markov 
			equivalence class 
			from the independence model restricted to 𝒮. This 
			equivalence class 
			has a maximal 
			element which is also in 𝔾 and thus one can also in this 
			case 
			represent the Markov equivalence class using a DMEG.
			
			
			
			

§ TIME SERIES AND UNROLLED GRAPHS

			
			
			In this section we first relate the cyclic DGs and 
			DMGs to acyclic 
			graphs and then 
			use this to discuss Markov properties (see Definition 
			<ref>) and faithfulness of local 
			independence 
			models in the time series case.
			
			
				Let 𝒢 = (V,E) be a DMG and let α,β∈ V. 
				A
				path between 
				α and 
				β is said to be m-connecting if no noncollider on the 
				path is in 
				C 
				and every collider on the path is in 
				An(C).  For 
				disjoint sets A,B,C⊆ V, we say that A and 
				B 
				are m-separated by C if there is no m-connecting path 
				between 
				α∈ 
				A and β∈ B.
				In this case, we write ABC.
			
			
			The above m-separation is a generalization
			of the well-known d-separation in DAGs. In
			this section we will only consider
			m-separation for DAGs, and will thus use the
			d-separation terminology. In Section <ref> 
			we 
			provide a more general relation between 
			μ-separation and m-separation. 
			
			We first describe how to obtain a DAG from a DG
			such that the DAG, if read 
			the right way, will 
			give the same separation model as the DG. 
			This can be 
			useful in time series 
			examples as well as when working with continuous-time models. 
			Sokol and Hansen <cit.> studied solutions to 
			sto­cha­stic 
			differential 
			equations and used a DAG in discrete time to approximate the 
			continuous-time dynamics. Danks and Plis <cit.> and 
			Hyttinen et al. 
			<cit.> used similar 
			translations between an unrolled graph in which time 
			is 
			discrete and explicit and a rolled graph in which time is 
			implicit. Some authors use the term unfolded instead of 
			unrolled.  In 
			a rolled graph each node represents a stochastic process whereas in 
			an unrolled 
			graph each node represents a single random variable. Definition 
			<ref> 
			shows 
			how to unroll a local independence graph and Lemma 
			<ref> 
			establishes a precise relationship between
			independence models in the rolled and unrolled 
			graphs.
			
			
				Let 𝒢 = (V,E) be a DG and 
				let T ∈ℕ. The unrolled version of 𝒢, 
				𝒟_T(𝒢) = 
				(V̅, E̅),
				is the DAG on nodes 
				
    V̅ = {x_t^α| (t,α) ∈{0,1,… , T}× 
    				V}

				and with edges
				
    E̅ = {x_s^α→ x_t^β|α→_𝒢β and  s < t}.

				Let D ⊆ 
				V 
				and let T∈ℕ. We define D_0:T = { 
				x_t^α∈V̅|α∈ D, t ≤ T} and D_T 
				= { 
				x_t^α∈V̅|α∈ D, t = T}.
				
				
			
			
			

				
			

			
			
				Let = (V,E) be a DG. If ABC then 
				(A∖ 
					C)_0:(T-1)B_TC_0:(T-1)𝒟_T(𝒢).
				For large 
				enough values of T, the opposite implication holds as well.
				
			
			
			
				Assume first that  ⟨ x_s_0^α_0, e_1, 
				x_s_1^α_1 ,…, e_l, 
				x_s_l^α_l⟩ is a d-connecting path in 
				𝒟_T(𝒢). This path has a head at 
				x_s_l^α_l∈ B_T. 
				Construct a 
				walk in 𝒢 by for each node, x_s_k^α_k, 
				taking the corresponding 
				node, α_k, and for each edge x_s_k^α_k∼ 
				x_s_k+1^α_k+1 taking the corresponding, 
				endpoint-identical 
				edge α_k∼α_k+1 in 
				𝒢. On this walk, no noncollider is in C, and 
				every 
				collider is 
				an ancestor of a node in C.
				
				Assume instead that ω is a μ-connecting walk in 
				𝒢 
				from A to B 
				given C,
				
				
    α_1 ∼…∼α_l-1→α_l

				
				and let T ≥ 3(| E| + 1) + 1. Using 
				Proposition 
				<ref>, we can assume that ω has length 
				smaller than 
				or equal to | E| + 1. We construct 
				a d-connecting walk in 𝒟_T()
				in 
				the following way. Starting from x_T^α_l, we choose 
				the edge 
				between 
				x_| E| + 1^α_l-1 and x_T^α_l. For 
				the 
				remaining 
				edges, α_k ∼α_k+1, we choose the edge x_s_k-1^α_k→ 
				x_s_k^α_k+1 if α_k →α_k+1 in ω, and x_s_k^α_k + 1→ 
				x_s_k +1 ^α_k if α_k ←α_k+1 in ω where s_k is determined by the 
				endpoints of the 
				previous 
				edge. 
				No 
				noncollider on 
				this walk 
				will be in C_0:(T-1). Every collider will be in 
				An_𝒟_T(𝒢)(C_0:(T-1)) as the collider 
				will be in 
				the time 
				slices 0 
				to 
				2(| E| + 1).  This d-connecting walk can be trimmed 
				down to a 
				d-connecting path.
			
			
			We defined local
			independence for a class of continuous-time
			processes in Definition <ref>. In this 
			section we define a similar
			notion for time series, as also introduced in 
			<cit.>. Let V 
			= 
			{1,…,n}. We consider a 
			multivariate time series (X_t)_t∈ℕ∪{0}, X_t = 
			(X_t^1,…,X_t^n), of the form
			
			
    X_t^α = f_α t(X_s<t, ε_t^α),

			
			where X_s<t = {X_u^α|α∈ V,u < t 
			}. 
			The random variables {ε_t^α} are independent. 
			For 
			S⊆ℕ∪{0} and
			D⊆ V 
			we 
			let 
			X_S^D = {X_s^α|α∈ 
			D, s ∈ S  } and X^D = { X^α|α∈ D}. In the 
			case of 
			time 
			series, 
			a notable feature of local independence 
			and local 
			independence 
			graphs is that they provide a simple representation in comparison 
			with graphs 
			in which each vertex represents a single time-point variable. 
			
			
				Let X be a multivariate time series. We say that X^B is 
				locally 
					independent of X^A given X^C if for all t ∈ℕ, 
				β∈ B, X_s<t^A  and X_t^β are conditionally 
				independent 
				given X_s<t^C, that is,
				
				
    X_s<t^A ⊥⊥ X_t^β| X_s<t^C

				
				and write 
				A 
				↛B | C.
			
			
			The above definition induces an independence
			model over V, which we will also refer to as
			the local independence model and denote
			ℐ in the following. The main
			question that we address is whether this
			independence model is graphical.  That is, we
			will construct a DG, consider the Markov and 
			faithfulness
			properties of ℐ and
			this DG, and relate them to Markov and
			faithfulness properties of the conditional
			independence model of finite distributions and
			unrolled versions of the DG.
			
			
				Let A,B,C ⊆ V. Let  be an 
				independence model on V and let 
				be a DMG. We 
				say that  and  are faithful if 
				= (), i.e., if
				
				
    ABC∈⇔ABC.

				
				One can give analogous definitions using other notions of 
				graphical separation. Below we also consider faithfulness of a 
				probability distribution and a DAG, implicitly using 
				d-separation instead of μ-separation in the above 
				definition.
				
			 
			
			Let 
			𝒟_T for T ≥ 1
			be the DAG on nodes {x_s^α| s ∈{0,…,T}, 
			α∈ V } such that there is an edge x_s^α→ 
			x_t^β 
			if and only if f_β t depends on the argument
			X_s^α. Let D_S =  {x_s^α|α∈ D, s ∈ S}. Let  denote  
			the minimal 
			DG such 
			that its unrolled version, 𝒟_T(), is a supergraph of 
			𝒟_T for all T ∈ℕ.
			
			For all T∈ℕ, the DAG 
			𝒟_T(𝒢) and the distribution of X_s≤ T 
			satisfy 
			
			
    x_s^α, x_t^β not adjacent ⇒ X_s^α⊥⊥ 
    			X_t^β| 
    			(An(X_s^α) ∪ An(X_t^β)) ∖{X_s^α,X_t^β},

			
			which is also known as the pairwise Markov property for 
			DAGs.
			Assume
			equivalence of the pairwise and global Markov properties for this 
			DAG and the
			finite-dimensional distribution (see e.g. <cit.> for 
			necessary 
			and 
			sufficient conditions for this equivalence).
			Assume that B is μ-separated from A by C in the DG 
			𝒢, 
			ABC.  By Lemma 
			<ref>,  
			(A∖ 
				C)_s<TB_TC_s<T𝒟_T(𝒢), and 
			by the 
			global Markov property in this DAG, 
			X_s<T^A∖ C⊥⊥ X_T^B | X_s<T^C. 
			This 
			holds for any T, and therefore A∖ C ↛B 
			| C. It 
			follows that A ↛B | C. This means that 
			ℐ satisfies the global Markov property with respect to 
			.  
			
			Assume furthermore that the distribution of X_T and the DAG 
			𝒟_T(𝒢) for some T∈ℕ are faithful and  that 
			T ≥ 
			3(| E| +1) +1. Meek <cit.> 
			studied faithfulness of DAGs and argued that faithful 
			distributions 
			exist 
			for any DAG. 
			If A ↛B 
			| C, then A∖ C ↛B | C and 
			X_s<T^A∖ 
				C⊥⊥ 
			X_T^B 
			| X_s<T^C. By faithfulness of the 
			distribution of X_T and the DAG 𝒟_T(), we have 
			(A∖ C)_s<TB_TC_s<T𝒟_T() and 
			using 
			Lemma 
			<ref> this implies that ABC, 
			giving us 
			faithfulness of ℐ and . 
			
			In summary, for every DG there exists a
			time series such that the local independence
			model induced by its distribution and the DG
			are faithful.
			
			

§ AN AUGMENTATION CRITERION

			
			
			In this section we present results that allow us to determine 
			μ-separation 
			from graphical separation in an undirected graph. An undirected graph is 
			a graph, (V,E), with an edge set that consists of 
			unordered 
			pairs of 
			nodes such that every edge is of the type -. Let A,B, and C 
			be disjoint 
			subsets 
			of V. We say that A and B are separated by C if every path 
			between 
			α∈ A and β∈ B contains a node in C.
			
			When working with d-separation in DAGs, it is possible to give an 
			equivalent 
			se­pa­ration criterion using a derived undirected graph, the moral 
			graph 
			<cit.>. Didelez <cit.> also gives both
			pathwise and so-called moral graph criteria for 
			δ-separation. The 
			augmented graph below is a generalization of the moral graph 
			<cit.> which allows one to give a 
			criterion for 
			m-separation based on an augmented graph. We use the 
			similarity of μ-separation and m-separation to give an 
			augmentation graph 
			criterion for μ-separation. The first step 
			in making a connection to m-separation is to 
			explicate that each node 
			of a DMG re­pre­sents an entire stochastic 
			process, and notably, both the past and the present of that 
			process. We do that 
			using graphs of the below type.
			
			
				Let 𝒢 = (V,E) and let B = 
				{β_1,…,β_k}⊆ 
				V. The 
				B-history 
				version of 𝒢, denoted by 𝒢(B), is the 
				DMG with node 
				set V {β_1^p,…, β_k^p} such that 
				𝒢(B)_V 
				= 
				𝒢 and
				
				
					
  * α↔_𝒢(B)β_i^p 
					if α↔_𝒢β_i and α∈ V, 
					β_i ∈ 
					B, 
					
  * α→_𝒢(B)β_i^p if
					α→_𝒢β_i and α∈ V, 
					β_i ∈ 
					B.
				
				
			
			
			𝒢(B) is a graph such that every node b∈ B is simply 
			split in 
			two: 
			one that represents the present and one that represents the past. 
			We define 
			B^p = {β_1^p,…, β_k^p}.
			
			
				Let 𝒢 = (V,E) be a DMG, and let A,B,C ⊆ 
				V. Then 
				
				
    ABC⇔A∖ 
    					CB^pC(B).

				
			
			
			
				Assume first that there is a μ-connecting walk from 
				α∈ A to 
				β∈ B given C in 𝒢. By definition α∈ 
				A∖ C. By Proposition 
				<ref> there is a μ-connecting route,
				
				
    α∼…∼β∼…γβ.

				
				The subwalk from α to γ is also present in 
				𝒢(B) and composing it with γ_𝒢(B)β^p 
				gives an m-connecting path between A∖ C and B^p 
				which is 
				open 
				given C.  
				
				On the other hand, if there is an m-connecting path from 
				α∈ A 
				∖ C 
				to 
				β^p∈ B^p given C in 𝒢(B), then no 
				non-endpoint node 
				is in B^p,
				
				
    α∼…γβ^p

				
				The subpath from α to γ is present in 
				𝒢 and can 
				be composed with the edge γβ to 
				obtain 
				a 
				μ-connecting walk from A to B given C in 
				𝒢.
			
			
			
			
			
				Let 𝒢 = (V,E) be a DMG. We define the augmented graph of 
				𝒢, 𝒢^a, to be the undirected graph 
				without loops 
				and with node set 
				V such that two distinct nodes are adjacent if and only if 
				the two nodes 
				are 
				collider connected in 𝒢.
			
			
			
				Let 𝒢 = (V,E) be a DMG, A,B,C⊆ V. Then 
				ABC if and only if 
				A∖ C and B^p are separated by C in the augmented 
				graph of 
				𝒢(B)_An(A∪ B^p∪ C).
			
			
			
				Using Proposition <ref> we have that 
				ABC⇔A∖ CB^pC(B). Let 
				(B)' be the DMG obtained from (B) by removing all 
				loops. Then 
				A∖ CB^pC(B)  if and only if 
				A∖ CB^pC(B)'. We can apply Theorem 
				1 of 
				<cit.>. That theorem assumes an ADMG, however, 
				as noted in 
				the paper, acyclicity is not used in the proof 
				which therefore also applies to (B)', and we conclude that 
				A∖ CB^pC(B)' if 
				and only if A ∖ C and B^p 
				are separated by C in ((B)'_An(A∪ B^p∪ C))^a = 
				((B)_An(A∪ B^p∪ C))^a.
				
				
			
			
			

§ EXISTENCE OF COMPENSATORS

			
			
			Let Z = (Z_t) denote a real-valued stochastic process defined on a
			probability space (Ω, ℱ,
			P), and let (𝒢_t) denote a
			right-continuous and complete filtration
			w.r.t. P such that 𝒢_t ⊆ℱ. Note that Z is not assumed
			adapted w.r.t. the filtration. When
			Z is a right-continuous process of finite and integrable
			variation, it follows from Theorem
			VI.21.4 in <cit.> that there exists a
			predictable process of integrable variation,
			Z^p, such that ^oZ - Z^p is 
			a
			martingale. Here ^oZ denotes the
			optional projection of Z, which is a
			right-continuous version of the process
			(E(Z_t |𝒢_t)), cf. Theorem
			VI.7.1 and Lemma VI.7.8 in
			<cit.>. The process Λ = Z^p is called the dual
			predictable projection or compensator of the
			optional projection ^oZ as well
			as of the process Z itself. It depends
			on the filtration (𝒢_t). 
			
			If Z is adapted w.r.t. a (right-continuous and
			complete) filtration (ℱ_t), it has a compensator
			Λ̃ = Z^p such that
			Z - Λ̃ is an ℱ_t martingale. 	
			When 𝒢_t ⊆ℱ_t it may be of interest 
			to understand the
			relation between Λ, as defined above
			w.r.t. (𝒢_t), and Λ̃.
			If Λ̃ is continuous with Λ̃_0 = 0, 
			say, we may ask
			if Λ equals the predictable projection,
			E(Λ̃_t |𝒢_t-). As Λ̃  
			is assumed continuous and is of finite variation, 
			
    Λ̃_t = ∫_0^t λ̃_s
    			d s.

			If ( λ̃_t) itself is an integrable right-continuous
			process, then its
			optional projection, ( E(λ̃_t |𝒢_t)), is
			an integrable right-continuous process, and 
			
    E(Λ̃_t |𝒢_t-) = ∫_0^t 
    			E(λ̃_s |𝒢_s) d s
 is a finite-variation, continuous
			version of the predictable projection of Λ̃. It is 
			clear that
			
    E(Z_t |𝒢_t) - ∫_0^t E(λ̃_s |𝒢_s) d s
 is
			a 𝒢_t martingale, thus 
			
    Λ_t = ∫_0^t E(λ̃_s |𝒢_s) 
    			d s

			is a compensator of Z w.r.t. the filtration (𝒢_t).
			
			We formulate the consequences of the discussion as a criterion
			for determining local independence via the computation of
			conditional expectations. The setup is as in Definition 
			<ref> in Section <ref>.
			
			 Assume that the process X^β for all β∈ 
				V
				has a compensator w.r.t. the filtration (ℱ^V_t) of 
				the form 
				
    Λ^V,β_t = Λ_0^V,β + ∫_0^t 
    				λ_s^βds

				for an integrable right-continuous process 
				(λ_t^β) and a
				deterministic constant Λ_0^V,β. Then X^β 
				is
				locally independent of X^A given X^C for A, C ⊆ V 
				if the
				optional projection 
				
    E(λ_t^β|ℱ^A ∪ C_t)

				has an ℱ_t^C adapted version.
			
			
			Another way to phrase the conclusion of the proposition is that if 
			the optional
			projection E(λ_t^β|ℱ^C_t) is
			indistinguishable from E(λ_t^β|ℱ^A ∪
				C_t), then A ↛β| C, and it is a 
			way
			of testing local independence via the computation of conditional
			expectations. It is a precise formulation of the innovation theorem
			stating how to compute compensators for one filtration via 
			conditional 
			expectations 
			of compensators for a superfiltration. 
			
			

§ PROOFS
 The following are proofs of the results from 
			the main paper.
			
			
			
				Let ω be a μ-connecting walk given 
				C and let γ 
				be a collider on the walk such that γ∈ An(C) ∖ 
				C. Then 
				there 
				exists a 
				subwalk ω̅ = α_1 γα_2, and an open (given C), directed path from γ 
				to δ∈ 
				C, 
				π. By composing  α_1 γ with 
				π, 
				π^-1, 
				and γα_2 we get an open walk which is endpoint-identical to 
				ω̅ 
				and 
				with its only collider, δ, in 
				C, and we can substitute ω̅ with this new walk. 
				Making 
				such 
				a substitution for every collider in An(C) ∖ C on 
				ω, we 
				obtain a μ-connecting walk on which every collider is in 
				C.
			
			
			
				Assume that 
				we start from α and continue along ω until some 
				node, γ≠β, is 
				repeated. Remove the cycle from γ to γ 
				to obtain another walk from α to β, 
				ω̅. If 
				γ= α, then 
				ω̅ is μ-connecting. Instead assume γ≠α. 
				If  this instance of γ is a 
				noncollider on ω̅ then it must have been a 
				noncollider in an 
				instance on ω and thus γ∉ C. If on the 
				other hand this 
				instance of γ is a collider on ω̅ then 
				either γ 
				was a collider in an instance on ω or the ancestor of a 
				collider on 
				ω, and thus γ∈ An(C). In either case, we see 
				that 
				ω̅ is a μ-connecting walk. Repeating this 
				argument, we 
				can construct a μ-connecting walk where only β is 
				potentially 
				repeated. If there is n > 2 instances of β then we can 
				remove 
				at least n-2 of them as above as long as we leave an edge 
				with a head at 
				the final β. 
			
			
			
				Note first that a vertex can be a 
				parent 
				of 
				itself. The result then follows from the fact
				that
				αβpa(β).
			
			
			
				The first statement follows from the fact that no edge without 
				heads (i.e. 
				-) is ever added. Assume for the second statement that  
				satisfies 
				(<ref>). Let M = V \ O. Assume α↔_ℳβ. By definition of the latent 
				projection, 
				we can find an endpoint-identical walk between α and 
				β in  
				with no colliders and such that all non-endpoint nodes are in 
				M. 
				Either this walk has a bidirected edge at α in which 
				case α↔_α by (<ref>) and therefore 
				also α↔_ℳα. Otherwise, there is a 
				directed edge 
				from some node γ∈ M such that γ→_α. 
				Then the walk α←γ→α is 
				present in 
				 and therefore α↔_ℳα because ℳ is a 
				latent 
				projection.
			
			
			
				Assume first that α has no loops. In this case, there 
				are no 
				bidirected edges between α and any node, and therefore 
				the edges 
				that have a head at α have a tail at the previous node. 
				Any 
				nontrivial walk between α and α is 
				therefore blocked by V∖{α}. Conversely, if 
				α has a 
				loop, then αα is a μ-connecting walk given 
				V∖{α}.
			
			
			 Let M = V 
				\ O. 
				Let first ω be a μ-connecting walk from α∈ 
				A to 
				β∈ B given C in . Using Proposition 
				<ref>, we can find a μ-connecting 
				walk from 
				α∈ A to β∈ B given C in  such that all 
				colliders are 
				in C. Denote this walk by ω̅. Every node, m, on 
				ω̅ which is in M is on a subwalk of 
				ω̅, δ_1 
				∼…∼ m ∼…∼δ_2, such that 
				δ_1,δ_2∈ O and all other nodes on the subwalk are 
				in M. 
				There are no 
				colliders on this subwalk and therefore there is an 
				endpoint-identical edge 
				δ_1 ∼δ_2 in ℳ. Substituting all 
				such subwalks 
				with their corresponding endpoint-identical edges gives a 
				μ-connecting 
				walk in ℳ.
				
				On the other hand, let ω be a μ-connecting walk from 
				A to B 
				given C in ℳ. Consider some edge in ω 
				which is not in 
				. In  there is an endpoint-identical walk with no 
				colliders and no 
				non-endpoint nodes in C. Substituting each of these edges 
				with such an 
				endpoint-identical walk gives a μ-connecting walk in  
				using 
				Proposition <ref>.
			
			
			
				We first note that in Algorithm <ref> adding an edge 
				will never 
				remove any triroutes. Therefore, Algorithm <ref> 
				returns 
				the same output regardless of the order in which the algorithm 
				adds edges. 
				
				Let ℳ denote 
				the output of Algorithm <ref> which is clearly a DMG. 
				The graphs 
				ℳ and m(, O) have the same 
				node set, thus it suffices to show that also the edge sets are 
				equal. 
				Assume first αe∼_m(, O)β. Then 
				there 
				exist an endpoint-identical walk in  that contains no 
				colliders and 
				such that all the non-endpoint nodes are in M = V∖ O, 
				α∼γ_1 ∼…∼γ_n ∼γ_n+1 = β. Let e_l be 
				the edge 
				between α and γ_l which is endpoint-identical to 
				the subwalk 
				from α to γ_l. If e_l is present in 
				ℳ_k at some 
				point during 
				Algorithm 
				<ref>, then edge e_l+1 will also be added before 
				the 
				algorithm terminates, l = 1,…,n. We see that e_1 is in 
				, and 
				this means that e 
				is 
				also present in ℳ.
				
				On the other hand, assume that some edge e is in 
				ℳ. If e is 
				not in , then we can find a noncolliding, 
				endpoint-identical 
				triroute in the graph ℳ_k (k has the value that 
				it takes when 
				the algorithm terminates) such that the noncollider is in M. 
				By 
				repeatedly using 
				this argument, we can from any edge, e, in ℳ 
				construct
				an endpoint-identical walk in  that contains no colliders 
				and such that 
				every non-endpoint node is in M, and therefore e is also 
				present in 
				m(, O).
			
			
			
				Let 
				
				
    α *→γ_1 ↔…↔γ_n ↔β

				
				be the inducing path, ν. Let γ_n+1 
				denote β. 
				If ν has length one, then 
				it is directed or 
				bidirected and itself a μ-connecting path/cycle regardless 
				of C. 
				Assume instead that 
				the length of ν is 
				strictly larger than one, and assume also first that α≠β. 
				Let 
				k be the maximal index in {1,…,n} such that there 
				exists an open 
				walk from α to γ_k given C which does not 
				contain β 
				and only contains α once. 
				There is a μ-connecting walk from 
				α to γ_1 ≠β given C and therefore k 
				is always 
				well-defined.
				
				Let ω be the open walk from α to γ_k. If 
				γ_k∈ 
				An(C), then the 
				composition of ω with the edge γ_k ↔γ_k+1 
				is open from α to γ_k+1 given C. By 
				maximality of k, we 
				must have k = n, and the composition is 
				therefore an open walk from α to β on which 
				β only 
				occurs once. We can reduce this to a μ-connecting path 
				using arguments 
				like those in the 
				proof of Proposition <ref>. Assume instead that 
				γ_k∉ An(C). There is a directed path from 
				γ_k to 
				α or to β. Let π denote the subpath from 
				γ_k to the 
				first occurrence of either α or β on this directed 
				path. If 
				β occurs first, 
				then the 
				composition of ω with π gives an open walk from 
				α to 
				β. There is a head at 
				β when moving from α to β and therefore the 
				walk can be 
				reduced to a μ-connecting path from α to β 
				using the 
				arguments in the proof of Proposition <ref>. If 
				α 
				occurs first, then the composition of π^-1 and the edge 
				γ_k 
				↔γ_k+1 gives a 
				μ-connecting walk and it follows that k = n by maximality 
				of 
				k. This walk is a μ-connecting path.
				
				To argue that the open path is endpoint-identical if ν is 
				directed or 
				bidirected, let instead k be the 
				maximal index such that there exists a μ-connecting 
				walk from α to γ_k with a head/tail at α. 
				Using the 
				same argument as above, we see 
				that 
				the μ-connecting path will be endpoint-identical to ν 
				in this case. In the directed case, note that in the case 
				γ_k∉ 
				An(C) one can find a directed path form γ_k to β, 
				and if 
				α occurs on this path one can simply choose the subpath 
				from 
				α to 
				β.
				
				In the case α = β, analogous arguments can be made 
				by assuming 
				that k is the maximal index such that there exists a 
				μ-inducing path 
				from α to γ_k given C such that β = 
				α only 
				occurs 
				once.
			
			
			
				For both propositions it suffices to argue 
				that if there is a μ-connecting walk in the larger graph, 
				then we 
				can also find a μ-connecting walk in the smaller graph. 
				Using 
				Proposition <ref> we can find 
				endpoint-identical walks 
				that are open given C∖{α} and replacing 
				αβ 
				with such a walk will give a walk which is open given C. For 
				Proposition 
				<ref> one should note that adding the edge respects 
				the 
				ancestry of the nodes due to transitivity.
			
			
			
				Assume there is no inducing path from α to β and 
				let ω 
				be some walk from α to β with a head at
				β. Note that ω must 
				have length at least 2. 
				
				
    α = γ_0 e_0∼γ_1 
    				e_1∼…e_m-1∼γ_m 
    				e_mβ.

				
				There must exist an i ∈{0,1,…,m} such that 
				γ_i is not 
				directedly collider-connected to β along ω or such 
				that 
				γ_i ∉ An(α, 
				β). Let j be the largest such index. Note first that 
				γ_m is 
				always directedly collider-connected to β along ω 
				and γ_0 
				is always in 
				An(α,β). If j ≠ m and γ_j 
				is not directedly collider-connected to β along ω, 
				then 
				γ_j+1 is a noncollider 
				and
				ω is closed in γ_j+1∈ D(α,β) (note 
				that α 
				= γ_j+1 is impossible as there would then be an 
				inducing path from 
				α to β). If j ≠ 0 and
				γ_j ∉ An(α,β) then there is some k ∈{1,…,j} such that γ_k 
				is a collider and γ_k ∉ An(α,β) and 
				ω is 
				therefore closed in this collider.
			
			
			 We verify 
				that 
				(gs1)–(gs3) hold. 

				(gs1) The edge α↔β 
				constitutes an 
				inducing path in both directions.
				
				(gs2-3) Let γ∈ V, C⊆ V 
				such that 
				β∈ C, and 
				assume that there is a μ-connecting walk from 
				γ to β given C in . This 
				walk has a head at β and composing the walk with α↔β creates an μ-connecting walk from
				γ to α given C.
			
			
			
				Any μ-connecting walk in 𝒢 is also present and 
				μ-connecting in 
				𝒢^+, hence ℐ(𝒢^+) ⊆ℐ(𝒢).
				
				Assume γ,δ∈ V, C ⊆ V and assume that 
				ρ is a 
				μ-connecting route from γ to δ given C in 
				𝒢^+. Let e denote the edge α↔β. 
				Using (gs1), 
				there exist an inducing path from α to 
				β in  and one from β to α. Denote these 
				by ν_1 
				and ν_2. If e is not in 
				ρ, then ρ is also in 𝒢 and 
				μ-connecting as 
				the addition of the bidirected edge does not change the 
				ancestry of .
				
				If e occurs twice in ρ then it contains a subroute 
				αe↔βe↔α and 
				α = δ  (or 
				with the roles 
				interchanged). Either one can find a μ-connecting 
				subroute of ρ with no occurrences of e or α∉ 
				C. If 
				β∈ C, then compose the subroute of ρ from γ 
				to the 
				first occurrence of α (which is either trivial or can be 
				assumed to 
				have a tail at 
				α) with the ν_1-induced open walk from 
				α to β using Proposition <ref>. 
				This is a 
				μ-connecting walk in  from γ to 
				β and using (gs2) the result follows. If β∉ 
				C, 
				then the result follows from composing the subroute from 
				γ to 
				α with the ν_1-induced open walk from α to 
				β and 
				the ν_2-inducing open walk from 
				β to α.
				
				If e only occurs once on 
				ρ, consider first a ρ of the form
				
				
    γ∼…∼α_ρ_1e↔β∼…δ_ρ_2.

				
				Assume first that α∉ C. Let π denote 
				the 
				ν_1-induced open walk from α to β and note 
				that π 
				has a head at β. If γ = 
				α then π composed with ρ_2 is a
				μ-connecting walk from γ to δ in . If 
				γ≠α 
				we can just 
				replace e with π, and the resulting composition of the
				walks ρ_1, π and ρ_2 is a μ-connecting
				walk from γ to δ in . If instead α∈ C, then γ≠α and α is a collider on 
				ρ, 
				and
				ρ_1 thus has a head at α and is μ-connecting
				from γ to α given C in . Using (gs3) we can 
				find a 
				μ-connecting walk from γ to 
				β given C in 𝒢. Composing this with 
				ρ_2 gives a 
				μ-connecting walk from 
				γ to δ given C in .
				
				If ρ instead has the form
				
				
    γ∼…∼βe↔α∼…δ,

				
				a similar argument using (gs2) applies. In
				conclusion, ℐ(𝒢) ⊆ℐ(𝒢^+).  
			
			
			 We verify 
				that 
				(gp1)–(gp4) hold. 

				(gp1) α→β constitutes an 
				inducing 
				path from α to β. 
				
				(gp2)  Let ω be a μ-connecting 
				walk from 
				γ to 
				α given C, α∉ C. Then ω composed 
				with 
				α→β 
				is 
				μ-connecting from γ to β given C.
				
				(gp3)  Let ω_1 be a μ-connecting 
				walk from 
				γ to 
				β given C, α∉ C, β∈ C, and let 
				ω_2 be a 
				μ-connecting 
				walk 
				from α to δ given C. The composition of 
				ω_1, 
				α→β, and ω_2 is μ-connecting.
				
				(gp4)  Let ω be a μ-connecting 
				walk from 
				β to  
				γ given C∪{α}, α∉ C. If this 
				walk is closed 
				given C, 
				then there exists a collider on ω, which is an ancestor 
				of α 
				and 
				not in An(C). Let δ be the collider on ω with 
				this property 
				which is the closest to γ. Then we can find a directed 
				and open 
				path from δ to β and composing the inverse of this 
				with the 
				subwalk of 
				ω from δ to γ gives us a connecting walk. 
			
			
			 As 
				 for all C⊆ V, any 
				μ-connecting 
				path 
				in 𝒢 is also 
				μ-connecting in 𝒢^+, and it therefore follows 
				that 
				(^+) 
				⊆(). 
				
				We will prove the other inclusion by considering a 
				μ-connecting walk 
				from 
				γ to δ given C in ^+ and argue that we can 
				find 
				another μ-connecting walk in ^+ that fits into cases 
				(a) or (b) 
				below. 
				In both cases, we will use the potential parents properties 
				to argue 
				that there is also a μ-connecting walk from γ to 
				δ given 
				C in . Let e denote the edge α→β.
				
				Let  ν denote the inducing path 
				from α to β in  which we know to exist by 
				(gp1) and 
				Proposition
				<ref>. Say we 
				have a μ-connecting walk in 𝒢^+, ω, 
				from γ to δ given C. There can be two reasons 
				why ω 
				is not 
				μ-connecting in 
				𝒢: 1) e is in ω, 2) there exist colliders, 
				c_1,…,c_k, on ω, which are in 
				An_𝒢^+(C) but not 
				in An_𝒢(C). We will in this proof call such 
				colliders newly closed. 	If there exists a newly closed collider on 
				ω, 
				c_i, 
				then there exists in 𝒢 a directed path from c_i 
				to α on which no node is in C, and furthermore 
				α∉ C. 
				Note that this path does not contain β, and the existence 
				of a 
				newly closed collider implies that β∈ 
				An_𝒢(C).
				
				Using Proposition 
				<ref>, we can find a route, ρ, in ^+ 
				from γ 
				to 
				δ, which is μ-connecting in ^+. Assume first 
				that e occurs 
				at most 
				once on ρ. 
				If there are newly closed colliders on ρ, we will argue 
				that we can 
				find a μ-connecting walk in ^+ with no newly closed 
				colliders and 
				such 
				that e occurs at most once. 
				Assume that 
				c_1,…,c_k are newly closed 
				colliders, ordered by their occurrences on the route ρ. We 
				allow 
				for 
				k=1, in which case c_1 = c_k. We will divide the argument
				into three cases, and we use 
				in all three cases that a μ-connecting walk in  is also 
				present in 
				^+ and has no newly closed colliders nor occurrences of 
				e. We also 
				use that α∉ C when applying (gp2).
				
				
					
  * e is between γ and c_1 on ρ. Consider the subwalk of ρ from γ to the first 
					occurrence of 
					α. If this subwalk has a tail at α (or is 
					trivial) then 
					we can compose 
					it with 
					the inverse 
					of the path from c_k to α and the subwalk from 
					c_k to 
					δ. This walk is open. If there is a head at 
					α, then using (gp2) we can find a μ-connecting 
					walk 
					from γ to β in , compose it with e, the 
					inverse of 
					the path 
					from c_k to α and the subwalk from c_k to 
					δ. This is 
					open as β∈ An_(C) and α∉ C whenever 
					there exist 
					newly closed 
					colliders.
					
  * e is between c_k and δ on ρ. Consider the subwalk of ρ from γ to c_1, and 
					compose it 
					with the directed path from c_1 to α. This is 
					μ-connecting 
					in  and using (gp2) we can find a μ-connecting walk 
					in  
					from γ to β. Composing this walk with the 
					subwalk of 
					ρ from 
					β to 
					δ gives a μ-connecting walk from γ to 
					δ, 
					noting that β∈ An_(C). 
					
  * e is between c_1 and c_k on ρ or not on 
					ρ at all. 
					Composing the subwalk from γ to c_1 with the
					directed path from c_1 to α gives a 
					μ-connecting 
					walk from γ to α given
					C in 𝒢, and by (gp2) 
					we 
					can 
					find a μ-connecting walk from γ to β in 
					, thus 
					there 
					are no newly closed colliders on this walk and it does not 
					contain e. 
					Composing it with e, the directed path from c_k to 
					α and the 
					subwalk from c_k to δ gives a μ-connecting 
					walk in ^+.
				
				
				In all cases (i), (ii), and (iii) we have argued that 
				there 
				exists 
				a μ-connecting 
				walk from γ to δ in ^+ 
				that contains no 
				newly closed colliders and that contains e at most once.
				Denote 
				this walk by ω̃. If ω̃ does not 
				contain e at 
				all, then we are done. Otherwise, two cases 
				remain, 
				depending on the orientation of e in the 
				μ-connecting walk ω̃:
				
				
					
  * Assume first we have a walk
					of the form
					
					
    γ∼…e_α∼α→β∼…δ,

					
					If there is a tail on e_α at 
					α, or if γ=α, then we can 
					substitute e with the open path between α and 
					β induced 
					by 
					ν and obtain an open walk. Otherwise, assume a head on 
					e_α 
					at α. ω̃ is μ-connecting in ^+ 
					and 
					therefore α∉ C. Using (gp2), there exists a 
					μ-connecting 
					walk 
					from γ to β, and composing this walk with the 
					(potentially 
					trivial) 
					subwalk from β to δ gives a
					μ-connecting walk from γ to δ given
					C in 𝒢.
					
					
  * Consider instead a walk of the form
					
					
    γ∼…e_β∼β←α∼…δ.

					
					If there is a head on e_β at β,
					β is a collider. If β∈ C,	then (gp3)
					directly gives a μ-connecting walk from γ
					to δ given C in 𝒢. If instead β∈ 
					An_^+(C)∖ C then we can 
					find a 
					directed path, π, in ^+ from β to 
					ε∈ C. 
					The 
					edge e 
					is not present on π and therefore we can compose the 
					subwalk from 
					γ to β with π, 
					π^-1, and the subwalk from β to δ to 
					obtain an open 
					walk 
					from γ to δ without any newly closed 
					colliders, only 
					one 
					occurrence of e, and such that there is a tail at
					β just before the occurence of e. 
					
					We have reduced this case to walks, ω̃, of 
					the form
					
    γ∼…←β_ω̃_1←α∼…δ_ω̃_2,

					where ω̃_1 is potentially trivial. Let 
					π̅ denote 
					the ν-induced open path or cycle 
					from α to β in . Using Proposition
					<ref> there is a μ-connecting
					route, ρ̅, 
					from α to δ given C in . 
					
					
					
					
					
					If there is a tail at 
					α on 
					ρ̅ 
					or on π̅ then the composition of
					ω̃_1, π and
					ρ̅ is 
					μ-connecting. Otherwise, if α≠β,
					the composition of π and
					ρ̅ is a μ-connecting walk from β to 
					δ given 
					C∪{α} in  as α does not occur as a 
					noncollider on 
					this composition. Using 
					(gp4) there is also one given C. As 
					there is a tail at β on ω̃ we can 
					compose
					ω̃_1 with this walk
					to 
					obtain 
					an open walk from γ to δ given C in 
					𝒢. If 
					α = β 
					the composition of ω̃_1 with 
					ω̃_2 is an 
					open walk from γ to δ given C in 
					𝒢.
				
				
				Assume finally that e occurs 
				twice on ρ. In this case ρ contains a subroute βe←αe→β and β = δ. In 
				this case 
				α∉ 
				C. If there are any newly closed colliders, consider the one 
				closest to 
				γ, c. The subroute of ρ from γ to c 
				composed with 
				the directed path from c to α gives a μ-connecting 
				path and 
				(gp2) gives the result. Else if there is a head at α on 
				the 
				ν-induced open walk then (gp2) again gives the result. 
				Otherwise, 
				compose the subroute from γ to the first β, the 
				inverse of the 
				ν-induced open walk, and the ν-induced open walk to 
				obtain an open 
				walk in  from γ to β = δ.
			
			
			
				Propositions 
				<ref> and <ref> show that 
				𝒩 is in 
				fact a supergraph of 𝒢, and as E^m only depends 
				on the 
				independence model, it also shows that 𝒩 is a 
				supergraph of any 
				element in [𝒢]. We can sequentially add the edges 
				that are in 
				𝒩 but not in , and Lemmas <ref> 
				and 
				<ref> show that this is done Markov equivalently, 
				meaning 
				that 𝒩∈ [𝒢].
			
			
			
				Let α,β∈ V. If there is a directed edge, e, from 
				α to β, and a unidirected inducing path from 
				α to 
				β of length at least two in 𝒩, then there is 
				a directed 
				inducing path from 
				α to β in 𝒩 - e.
				
			
			
			
				Let ν denote the unidirected inducing path and 
				γ_1,…,γ_n the non-endpoint nodes of ν. 
				Then 
				γ_i ∈ An_𝒩({α,β}) and also 
				γ_i 
				∈ 
				An_𝒩(β) due to the directed edge from α
				to β. It follows that either γ_i ∈ 
				An_𝒩(α) 
				or γ_i ∈ An_(𝒩 - e)(β). If γ_i 
				∈ 
				An_𝒩(α), let e_i denote the directed edge 
				from γ_i 
				to  
				β, and let 𝒩^+ = (V, F ∪{e_i}). We will 
				argue that 
				𝒩 = 𝒩^+ using the 
				maximality of 𝒩. Note first that the edge does not 
				change the 
				ancestry of the 
				graph in the sense that An_𝒩(γ) = 
				An_𝒩^+(γ) for all γ∈ V. Note also 
				that there is a
				bidirected inducing path between γ_i and β in 
				𝒩, 
				and therefore γ_i ↔_𝒩β. 
				Assume 
				that 
				e_i is in a μ-connecting path in 𝒩^+. There 
				is a directed 
				path from γ_i to α in 𝒩 and therefore 
				e_i can 
				either be 
				substituted with γ_i →α_i →…→α_k →α→β (if 
				α_1,…,α_k,α∉ C), or with γ_i 
				↔β (otherwise), and we see that 
				ℐ(𝒩) = ℐ(𝒩^+). By 
				maximality of 
				𝒩 we have that 
				𝒩 = 𝒩^+ which implies that e_i ∈ F. 
				Thus 
				γ_i ∈ 
				An_(𝒩 - e)(β). This shows that ν is 
				also a 
				directed inducing path in 𝒩 - e.
			
			
			
				Let edges α→β, 
				β→α and α↔β 
				be denoted by 
				e_1, e_2, e_3, respectively. If e_1, e_3 ∈ F, then 
				𝒩 - e_1 
				∈ 
				[𝒩]. If e_1,e_2,e_3 ∈ F, then 𝒩 - e_3 
				∈ 
				[𝒩].
				
			
			
			
				Note that if edges γα, α↔β, and α→β 
				are present in a maximal DMG, then so is γβ 
				by Propositions <ref> and <ref>. Assume 
				e_1,e_3∈ 
				E. Using the above observation, note that every 
				vertex that is a parent of 
				α in 
				𝒩 is also 
				a parent of β, thus An_𝒩(δ) ∖{α} = 
				An_(𝒩 - 
					e_1)(δ) ∖{α} for all δ∈ V. 
				Consider a 
				μ-connecting 
				walk, ω, in 𝒩 given C. Any collider 
				different from 
				α on this walk is in An_(𝒩 - e_1)(C). If 
				α∉ An_(𝒩 - 
					e_1)(C) is a 
				collider, 
				then we can substitute the subwalk γ_1 αγ_2 with γ_1 βγ_2. If e_1 is the first edge on 
				ω and α the first node, then 
				just substitute 
				e_1 with e_3. Else, we need to consider two cases: in the 
				first case 
				there is a 
				subwalk 
				γα→β (or β←αγ) and therefore an edge 
				γβ in 𝒩 - e_1 if γ≠α. If 
				γ = α, we can 
				simply remove the loop, replacing e_1 with e_3 if γ 
				was the 
				final node on ω. In the second 
				case, there is a subwalk 
				γ←α→β (or β←α→γ), and we can substitute 
				e_1 with 
				e_3 if β≠γ. If β 
				= γ, then we can substitute 
				β←α→β with β↔β.
				
				The proof of the other statement is
				similar.
			
			
			
			
			
				One implication is immediate by contraposition: if α∉ 
				u(β, (𝒩 - e)), then 𝒩 - e ∉ 
				[𝒩]. 
				
				Assume α∈ u(β, ℐ(𝒩 - e)). 
				There 
				exists an inducing path, ν, from α to β in 
				𝒩 - e. If ν is directed, then the conclusion 
				follows from 
				Proposition <ref>. If ν is unidirected and of 
				length one, 
				then it is also directed. If it is unidirected and has length 
				at least two, 
				it follows from 
				Lemma <ref> that there also exists a 
				directed inducing path 
				in 𝒩 - e. Proposition <ref> finishes 
				the argument. 
				Assume that ν is bidirected. Then α↔_𝒩β due to maximality and 
				Proposition 
				<ref>. Lemma <ref> gives the result.
			
			
			
				One implication follows by contraposition. Assume instead that 
				α∈ 
				u(β, (𝒩 - e)) 
				and β∈ u(α, (𝒩 - e)). Then there is 
				an inducing 
				path from α to β and one from β to α 
				in 
				𝒩 - e. Denote these by ν_1 and ν_2. If one 
				of them is 
				bidirected, then the conclusion follows. Assume instead that 
				none of them 
				are bidirected and assume first that both are a single edge. 
				The conclusion 
				then follows using Lemma <ref>.
				
				Assume now that ν_1 or ν_2 is an inducing path of 
				length at 
				least 2. Say that β→γ_1 ↔…↔γ_m 
				↔α is an inducing path. If ν_1 is the
				inducing path α→_𝒩β of length one, then there is 
				also a 
				bidirected inducing 
				path 
				between γ_1 and β in 𝒩, and there will 
				also be a 
				bidirected inducing path in 𝒩 - e between α 
				and β. 
				If 
				instead ν_1 is the 
				inducing path α→ϕ_1 ↔…↔ϕ_k ↔β then γ_1 ↔_𝒩ϕ_1. In 
				this case 
				α↔γ_m …γ_1 ↔ϕ_1 
				…ϕ_k ↔β can be trimmed down to a 
				bidirected 
				inducing path in 
				𝒩 - e. 
			








