betaFeedback

WorksMathematics

A fast and sound algorithm to simplify summations in interventional queries expressions

Abstract

Identification formulas returned by the ID algorithm often contain summations that can be removed. The procedure proposed in arxiv:1806.07082 (TK) removes them by combining factors of the formula into joint distributions, through the chain rule and through the insertion of factors for missing variables. We make two changes to this procedure: only the factors that involve the summed variable are combined, and every factor is written with a minimal conditioning set. These two changes determine the rest of the procedure, in which each search over a power set is replaced by a single test and the variables to insert are fixed in advance, and they remove summations that the TK procedure leaves in place. The resulting procedure is sound and, for minimal input terms, complete for each individual elimination with respect to joins and insertions.

Introduction

A central task of causal inference is to express the effect of an intervention through the distribution of observed variables. When the causal assumptions are encoded in a diagram GG, whose directed edges represent direct causal influence and whose bidirected edges represent latent common causes, an interventional distribution P(y∣x^)P(y \mid\hat{x}) is identifiable if it can be computed from the observational distribution P(v)P(v) and GG alone [1, 2]. Identifiability is characterised by the do-calculus [1], whose completeness was shown independently by Shpitser and Pearl [3] and by Huang and Valtorta [4]. The ID algorithm of Shpitser and Pearl [3] decides it constructively, by a recursion on the c-components of GG, the maximal sets of vertices connected by bidirected paths, over which the observational distribution factorises [5, 6], and returns a formula for P(y∣x^)P(y \mid\hat{x}) in the identifiable cases.

The formula is always correct but rarely in its simplest form. It is built from conditional distributions P(V∣C)P(V \mid C), which we call terms, with head VV and conditioning set CC, combined by products, ratios and nested summations. Simplifying such formulas is not just a matter of elegance: a simpler formula is easier to interpret, since it may reveal a familiar adjustment, and easier to estimate especially when generalized random zeros [7] exist in the dataset.

An ID interventional formula can be simplified in three (main) ways: common factors in numerator and denominator of a single ratio; cancellations between factors of different ratios; summations that can be worked out. This paper concerns the last problem, in particular how to solve summations in atomic expressions

∑S∏iP(Vi∣Ci)\sum_{S} \prod_{i} P(V_i \mid C_i)

which are sums of products of terms. A summation is added to the expression whenever line 2 of ID is recursively called, or when line 4 or one of the exit lines 1 or 6 is called, whether or not it can be carried out.

To show how sums can be simplified, let us consider the query P(c∣b^)P(c \mid\hat{b}) on the simple collider graph G=a→c←bG = a \to c \leftarrow b with topological order a<b<ca < b < c. ID returns

P(c∣b^)=∑aP(a) P(c∣a,b).(1)P(c \mid\hat{b}) = \sum_{a} P(a)\,P(c \mid a,b). \tag*{(1)}

Since aa and bb are independent, P(a)=P(a∣b)P(a)=P(a \mid b), and the chain rule combines the two terms into a joint distribution in which aa is a head and nowhere a condition:

P(c∣a,b)P(a)=P(a,c∣b),henceP(c∣b^)=∑aP(a,c∣b)=P(c∣b).(2)P(c \mid a,b)P(a)=P(a,c \mid b), \qquad\text{hence} \qquad P(c \mid\hat{b})=\sum_{a}P(a,c \mid b)=P(c \mid b). \tag*{(2)}

Every removal of a summation known to us follows this pattern, which we call the elimination of the variable: the terms are assembled into a joint distribution where the summed variable is a head, the variable is summed out, and the result is factorised again.

The procedure TK [8] performs these eliminations, by assembling terms in decreasing topological order of their heads by pairwise joins

P(J∣D) P(V∣C)=P(J,V∣Z),(3)P(J \mid D)\,P(V \mid C)=P(J,V \mid Z), \tag*{(3)}

applications of the chain rule whose conditioning set ZZ is searched for among the ancestors of VV and the subsets of a set of preceding vertices. When a join fails because the joint carries a condition MM that the next term cannot carry (the second independence condition of INSERT in TK fails), the procedure inserts MM: a term P(M∣E)P(M \mid E) free of the summed variable, with EE found by the same kind of search, is multiplied into the joint and divided out after the summation. The procedure assembles every term whose head lies between the summed variable and the last head (the summation head), and assumes that every term is conditioned on (at least) all the ancestors of its head (topological consistency).

Our first change is to assemble only the terms in which SS occurs, the participating terms, as one would do on paper, where to carry out a sum over SS one looks at the factors that contain SS, tries to combine them by the chain rule, supplies a missing factor where the chain rule requires one, and sums. Our second change is to write every term with a minimal conditioning set, from which no condition can be dropped without changing the term, and this fixes the rest of the procedure. As we will see in § 3, two minimal terms can be joined at a unique minimal set only, so that a single test replaces the search; the variables to insert and the term inserted for each are fixed in advance (§ 4). The resulting procedure, stated in § 5, is sound and, with respect to joins and insertions, complete: every expression that it returns is correct, and it eliminates a summation variable whenever joins and insertions can eliminate it (§ 6). Section 2 introduces the setting and the participating terms, and Section 7 concludes.

Setting, minimality and participating terms

This section defines the factors used to eliminate a summation variable and the joint distribution they must form.

Throughout, PP is positive and faithful to GG, so that conditional independences and d-separations coincide, and a topological order π\pi of the vertices of GG is fixed; we write u<vu<v when uu precedes vv in π\pi. A term is a factor P(W∣C)P(\mathbf{W}\mid\mathbf{C}) whose head set W\mathbf{W} is disjoint from its conditioning set C\mathbf{C}; a term with a single head is written P(h∣C)P(h\mid C). Besides the d-separation criterion we use three properties of conditional independence, valid for every distribution: symmetry, by which X⊥ ⁣ ⁣ ⁣⊥Y∣ZX \perp\!\!\!\perp Y \mid Z and Y⊥ ⁣ ⁣ ⁣⊥X∣ZY \perp\!\!\!\perp X \mid Z are equivalent; decomposition, by which X⊥ ⁣ ⁣ ⁣⊥Y∪W∣ZX \perp\!\!\!\perp Y \cup W \mid Z implies X⊥ ⁣ ⁣ ⁣⊥Y∣ZX \perp\!\!\!\perp Y \mid Z; and weak union, by which X⊥ ⁣ ⁣ ⁣⊥Y∪W∣ZX \perp\!\!\!\perp Y \cup W \mid Z implies X⊥ ⁣ ⁣ ⁣⊥Y∣Z∪WX \perp\!\!\!\perp Y \mid Z \cup W.

Definition 2.1. A condition c∈Cc\in C is idle in P(W∣C)P(W\mid C) when P(W∣C∖{c})=P(W∣C)P(W\mid C\setminus\{c\})=P(W\mid C), that is, when W⊥ ⁣ ⁣ ⁣⊥c∣C∖{c}W \perp\!\!\!\perp c \mid C\setminus\{c\}. The conditioning set CC is minimal when no condition is idle.

A minimal conditioning set is obtained from any conditioning set by dropping idle conditions one at a time until none is left: this is the function MINIMIZE of Section 5. Minimality is a property of the term and is not determined by the parents or ancestors of its head: a minimal conditioning set need not contain the ancestors of the head, contrary to the topological consistency assumed in [8].1 The uniqueness result of § 3 holds for minimal terms only.

Minimality is already imposed by the ID algorithm, as all the terms returned by it are minimal [6 Lemma 1]: to see that, let ViV_i be a vertex and TiT_i the c-component of ViV_i in the subgraph induced by ViV_i and its π\pi-predecessors, and let CiC_i consist of the other members of TiT_i and the parents of all members of TiT_i. By the c-component factorisation [6], the conditionals P(vi∣viπ)P(v_i \mid v_i^\pi) formed at lines 6 and 7 of ID [3] equal P(Vi∣Ci)P(V_i \mid C_i). No condition c∈Cic \in C_i is idle, because cc either belongs to TiT_i or is a parent of some t∈Tit \in T_i, and therefore reaches ViV_i through a bidirected path inside TiT_i, preceded in the second case by the edge c→tc \to t. Every intermediate vertex of this path lies in TiT_i, hence is conditioned, and is a collider, so that the path is open given Ci∖{c}C_i \setminus\{c\} and, under faithfulness, Vi⊥̸c∣Ci∖{c}V_i \not\perp c \mid C_i \setminus\{c\}. Since TiT_i lies among the predecessors of ViV_i, these terms are also conditioned only on variables below their heads. The procedure maintains this property (§ 4), and we assume it throughout.

The simplification uses four rewritings:

(R1) A conditional distribution sums to one over its head: ∑vP(v∣C)=1\sum_v P(v \mid C) = 1 whenever v∉Cv \notin C.

(R2) A factor in which the summed variable does not occur can be taken out of the sum: ∑U(EF)=E∑UF\sum_U (EF) = E\sum_U F when UU does not occur in EE.

(R3) Products and sums may be reordered and regrouped, by commutativity and associativity.

(R4) A summation over heads of a joint distribution is a marginalisation: if a product of terms equals P(W∣D0)P(W \mid D_0) and U⊆WU \subseteq W, its sum over UU is P(W∖U∣D0)P(W \setminus U \mid D_0), which the chain rule writes again as a product of terms; for instance ∑A,CP(A)P(B∣A)P(C∣A,B)=P(B)\sum_{A,C} P(A)P(B \mid A)P(C \mid A,B) = P(B).

The first three apply to any product of terms, while (R4) applies only to terms that together form a joint distribution. To eliminate a summation variable SS means to assemble terms into a joint distribution P(J∣D)P(J \mid D) with S∈JS \in J and S∉DS \notin D, to sum over SS, and to factorise the result. The factorisation writes each surviving term with all the variables that the chain rule assigns to it, a set that contains idle conditions in general: it is at this point that minimality must be restored.

We recall TK in the form needed for comparison [8 Algorithms 1–3]. Let ∑S∏iP(Vi∣Ci)\sum_S \prod_i P(V_i \mid C_i) be atomic, WW the set of its variables, and S∈SS \in\mathcal{S}. Terms in which no summation variable occurs are first extracted [8 Algorithm 5]. To eliminate SS, Simplify assembles, in decreasing order of their heads, every remaining term whose head lies between SS and the π\pi-last head; the variables of WW in that range that head no term are the missing variables. Join combines the current joint P(J∣D)P(J \mid D) with the next term P(V∣C)P(V \mid C) by trying, for each subset PP of Jπ∖An∗(V)J^\pi\setminus An^*(V), the conditioning set An(V)∪PAn(V) \cup P; a candidate is accepted when J⊥Y1∣D∖Y1J \perp Y_1 \mid D \setminus Y_1 and V⊥Y2∣C∖Y2V \perp Y_2 \mid C \setminus Y_2, with Y1=(An∗(V)∪P)△DY_1 = (An^*(V) \cup P)\triangle D and Y2=(An(V)∪P)△CY_2 = (An(V) \cup P)\triangle C. When no candidate is accepted, Insert tries a missing variable M∈D∖CM \in D \setminus C with the conditioning sets An(M)∪PAn(M) \cup P, accepting the first for which the joint absorbs the new term and M⊥SM \perp S given it. The summation is then carried out on the joint and the inserted terms are divided out; no minimality check is performed.

The first change we make concerns the first step, the choice of the terms to be assembled. Let ∑S∏t∈Tt\sum_S \prod_{t\in T} t be an atomic expression: SS is its set of summation variables, and TT is its set of terms, each a conditional distribution t=P(V∣C)t = P(V \mid C), given by its head VV and its conditioning set CC. Let S∈SS \in\mathcal{S} be the variable to be eliminated. Like every summation variable in an output of ID, SS is the head of one term of the expression: the output is a probabilistic expression, in which a summation marginalises a distribution over some of its own variables, and a variable that heads no term cannot be summed.

Definition 2.2. The participating terms PS⊆T\mathcal{P}_S \subseteq T are those in which SS occurs, as head or as condition; the others form OS=T∖PS\mathcal{O}_S = T \setminus\mathcal{P}_S. We write H\mathbf{H} for the heads of PS\mathcal{P}_S, ChC_h for the conditioning set of the term headed by h∈Hh \in\mathbf{H}, and

N:=(⋃h∈HCh)∖H\mathbf{N} := \left(\bigcup_{h\in\mathbf{H}} C_h\right) \setminus\mathbf{H}

for the variables on which participating terms are conditioned without heading one of them.

By (R2), ∑S∏t∈Tt=∏t∈OSt⋅∑S∏t∈PSt\sum_S \prod_{t\in T} t = \prod_{t\in\mathcal{O}_S} t \cdot\sum_S \prod_{t\in\mathcal{P}_S} t, so only PS\mathcal{P}_S has to be assembled into a joint distribution. TK assembles more: every term whose head lies between SS and the last head of the expression, together with terms inserted for missing variables. The end result of both procedures, if successful, is an assembly.

Definition 2.3. An assembly for SS is a joint distribution P(A∣B)P(\mathbf{A} \mid\mathbf{B}), with H⊆A\mathbf{H} \subseteq\mathbf{A} and S∈AS \in\mathbf{A}, whose heads are taken in decreasing topological order ar>⋯>a1a_r > \cdots> a_1, and which is written by the chain rule as

P(A∣B)=∏i=1rP(ai∣Eai),Eai:=B∪{a1,…,ai−1},P(\mathbf{A} \mid\mathbf{B}) = \prod_{i=1}^{r} P(a_i \mid\mathbf{E}_{a_i}), \qquad\mathbf{E}_{a_i} := \mathbf{B} \cup\{a_1,\ldots,a_{i-1}\},

where the factor of each participating head hh is its term, P(h∣Ch)=P(h∣Eh)P(h \mid C_h) = P(h \mid E_h), and the factor of every other head is a further term that does not depend on SS, either a term of OS\mathcal{O}_S or a term to be inserted.

The summation over SS is then a marginalisation of the joint, after which the inserted terms are divided out. Since every condition of a participating term is a variable of the joint, N⊆A∪B\mathbf{N} \subseteq\mathbf{A} \cup\mathbf{B}.

Definition 2.4. For R⊆N\mathbf{R} \subseteq\mathbf{N}, let L:=N∖R\mathbf{L} := \mathbf{N} \setminus\mathbf{R}. A reduced assembly is an assembly P(H∪R∣L)P(\mathbf{H} \cup\mathbf{R} \mid\mathbf{L}): its heads are the participating heads and the variables of R\mathbf{R}, its conditions are the other variables of N\mathbf{N}, and its further terms are only inserted terms for the variables of R\mathbf{R}. A full assembly P(A∣B)P(\mathbf{A} \mid\mathbf{B}) may contain, besides the participating terms, terms of OS\mathcal{O}_S, called retained terms, and inserted terms for missing variables, so that A\mathbf{A} and B\mathbf{B} may contain variables outside H∪N\mathbf{H} \cup\mathbf{N}. The reduction of a full assembly P(A∣B)P(\mathbf{A} \mid\mathbf{B}) is the reduced assembly with R:=A∩N\mathbf{R} := \mathbf{A} \cap\mathbf{N}, so that L=B∩N\mathbf{L} = \mathbf{B} \cap\mathbf{N}: it keeps the participating heads and the variables of R\mathbf{R} in the same order, conditions them on L\mathbf{L}, and drops the variables of U:=(A∪B)∖(H∪N)\mathbf{U} := (\mathbf{A} \cup\mathbf{B}) \setminus(\mathbf{H} \cup\mathbf{N}), namely the heads of retained terms, the missing variables outside H∪N\mathbf{H} \cup\mathbf{N}, and the conditions of the joint outside N\mathbf{N}.

TK produces full assemblies, and the procedure of § 5 reduced ones; the following proposition relates the two.

Proposition 2.5. If a full assembly for SS exists, its reduction is an assembly for SS, in the same order of assembly.

By the proposition, whatever a full assembly eliminates is eliminated by the participating terms alone, with inserted terms for the variables of R=A∩N\mathbf{R} = \mathbf{A} \cap\mathbf{N}. Only variables of N\mathbf{N} therefore need to be inserted. Such a variable may already exist in the expression and head a term of OS\mathcal{O}_S; in our procedure that term then remains outside the summation, and its head is inserted with the term that the chain rule requires (Example 4.3). Definition 2.3 takes the heads in decreasing topological order, as do Definition 5 of [8] and the procedure of § 5, and this choice is not a restriction, because every term depends only on variables below its head, so that a joint assembled in another order can be rearranged into this one without changing its terms (Appendix § 9.§ 2).

The converse of the proposition fails, because a retained term imposes two constraints that a reduced assembly avoids. First, it must fit, that is, it must be the factor that the chain rule assigns to its head in the full joint. Second, it adds conditions: its conditions enter the joint, and every participating term must then be independent of those it does not carry. In Example 2.6 below the added condition XX makes the join with the participating term P(B∣A)P(B \mid A) fail, and in Example 4.3 of § 4 the retained term does not fit: in both, a reduced assembly eliminates a variable that TK cannot eliminate. These comparisons concern one summation at a time, whereas the outcome of a whole run also depends on the order in which the summation variables are tried. In Example A.1 of the appendix, with the summation variables tried in a fixed order, the procedure of this paper removes fewer summations than TK, because it eliminates a variable that TK cannot and this blocks later eliminations; tried in another order, it reaches the same result as TK.

Example 2.6 (a retained term above the participating terms). Consider the graph below, with the topological order X<A<B<YX < A < B < Y, and the query P(Y∣X^)P(Y \mid\hat{X}).

Figure 2.

ID returns

P(Y∣X^)=∑A,BP(A) P(B∣A) P(Y∣X,B).P(Y \mid\hat{X}) = \sum_{A,B} P(A)\,P(B \mid A)\,P(Y \mid X,B).

The summation variables are tried in decreasing order, beginning with BB, whose participating terms are P(Y∣X,B)P(Y \mid X,B) and P(B∣A)P(B \mid A). Their join requires B⊥X∣AB \perp X \mid A, which fails because of X↔BX \leftrightarrow B; no variable is inserted, since the only condition of the joint that P(B∣A)P(B \mid A) does not carry is X<BX < B. The participating terms of AA are P(A)P(A) and P(B∣A)P(B \mid A) only, while P(Y∣X,B)P(Y \mid X,B) remains outside the summation. By the chain rule P(A)P(B∣A)=P(A,B)P(A)P(B \mid A) = P(A,B), and summing over AA gives P(B)P(B), so that

P(Y∣X^)=∑BP(B) P(Y∣X,B),P(Y \mid\hat{X}) = \sum_B P(B)\,P(Y \mid X,B),

the back-door formula. A second attempt on BB requires P(B)=P(B∣X)P(B) = P(B \mid X), which fails again; the remaining summation is the adjustment for BB, and no rewriting removes it.

To eliminate AA, TK must assemble the heads YY, BB and AA, beginning with the join of P(Y∣X,B)P(Y \mid X,B) and P(B∣A)P(B \mid A). Here An(B)={A}An(B)=\{A\} and Jπ∖An∗(B)={X}J^\pi\setminus An^* (B)=\{X\}, so the candidate sets are {A}\{A\}, which fails Y⊥ ⁣ ⁣⊥{A,X}∣BY \perp\!\!\perp\{A,X\} \mid B because of X→YX \to Y, and {A,X}\{A,X\}, which passes Y⊥ ⁣ ⁣⊥A∣X,BY \perp\!\!\perp A \mid X,B but fails B⊥ ⁣ ⁣⊥X∣AB \perp\!\!\perp X \mid A because of X↔BX \leftrightarrow B. No variable is missing between AA and YY, so the elimination fails; the elimination of BB begins with the same join and fails as well, and the expression is left unchanged. The same happens in each of the three topological orders of the graph; in those where XX follows AA, XX is missing and its insertion fails too. The failure is caused by the term P(Y∣X,B)P(Y \mid X,B), which is retained although it does not contain AA, and whose join with P(B∣A)P(B \mid A) is impossible at any set.

Participation is read off the conditioning sets as written. A term that carries an idle condition on SS therefore takes part in the elimination of SS, although it does not depend on SS, and must be assembled with the other participating terms; if that assembly is impossible, the elimination is lost. Such conditions do not occur in the terms emitted by ID, but they occur after a summation unless minimality is restored (Example 3.3), and they are written by the search of [8], whose joints are conditioned on all the ancestors of the joined head (Example A.1). In the procedure of § 5, every term written after a summation is minimised.

The conditioning set of a join

The first step in building a joint distribution in which SS is a head is to join terms, one at a time, by the chain rule. The highest term forms the initial joint, and each following term P(V∣C)P(V \mid C) is joined to the joint P(J∣D)P(J \mid D) assembled so far. A join must choose the conditioning set of the new joint: TK searches for it among the sets An(V)∪PAn(V) \cup P, whereas for minimal terms there is only one candidate, a fixed conditioning set at which two independences decide the join.

Since every term is conditioned only on variables below its head, and the heads of the joint lie above VV, the set JJ is disjoint from C∪{V}C \cup\{V\}. We write

C:=(D∪C)∖{V},so thatC⊆C,D⊆C∪{V}.\mathcal{C} := (\mathbf{D} \cup\mathbf{C}) \setminus\{V\}, \qquad\text{so that} \qquad\mathbf{C} \subseteq\mathcal{C}, \quad\mathbf{D} \subseteq\mathcal{C} \cup\{V\}.

Theorem 3.1 (The unique join set). Let P(J∣D)P(\mathbf{J} \mid\mathbf{D}) and P(V∣C)P(V \mid\mathbf{C}) be minimal.

(i) The two terms are joined at some set ZZ, that is, P(J∣D)P(V∣C)=P(J,V∣Z)P(\mathbf{J} \mid\mathbf{D})P(V \mid\mathbf{C}) = P(\mathbf{J},V \mid Z), if and only if they are joined at C\mathbf{C},

P(J∣D)P(V∣C)=P(J,V∣C),(4)P(\mathbf{J} \mid\mathbf{D})P(V \mid\mathbf{C}) = P(\mathbf{J},V \mid\mathbf{C}), \tag*{(4)}

and this holds if and only if

J⊥ ⁣ ⁣⊥(C∪{V})∖D∣DandV⊥ ⁣ ⁣⊥(D∖{V})∖C∣C.(5)\mathbf{J} \perp\!\!\perp(\mathbf{C} \cup\{V\}) \setminus\mathbf{D} \mid\mathbf{D} \qquad\text{and}\qquad V \perp\!\!\perp(\mathbf{D} \setminus\{V\}) \setminus\mathbf{C} \mid\mathbf{C}. \tag*{(5)}

In that case C⊆Z\mathbf{C} \subseteq Z, and every condition in Z∖CZ \setminus\mathbf{C} is idle in P(J,V∣Z)P(\mathbf{J},V \mid Z).

(ii) If (4) holds, C\mathbf{C} is a minimal conditioning set for P(J,V∣C)P(\mathbf{J},V \mid\mathbf{C}).

The two independences in (5) state that P(J∣D)=P(J∣C,V)P(\mathbf{J} \mid\mathbf{D}) = P(\mathbf{J} \mid\mathbf{C},V) and P(V∣C)=P(V∣C)P(V \mid\mathbf{C}) = P(V \mid\mathbf{C}): each term can be written with the conditioning set that the chain rule assigns to it in the joint P(J,V∣C)P(\mathbf{J},V \mid\mathbf{C}).

Proof. (i) The statement contains three assertions: the terms are joined at some set, they are joined at C\mathbf{C}, and the independences (5) hold. We prove that the third implies the second, the second the first, and the first the third, so that the three are equivalent and both equivalences of (i) hold. If (5) holds, the chain rule gives P(J∣D)P(V∣C)=P(J∣C,V)P(V∣C)=P(J,V∣C)P(\mathbf{J} \mid\mathbf{D})P(V \mid\mathbf{C}) = P(\mathbf{J} \mid\mathbf{C},V)P(V \mid\mathbf{C}) = P(\mathbf{J},V \mid\mathbf{C}), which is (4). If (4) holds, the terms are joined at a set, namely Z=C\mathbf{Z}=\mathbf{C}. Finally, suppose that P(J∣D)P(V∣C)=P(J,V∣Z)P(\mathbf{J} \mid\mathbf{D})P(V \mid\mathbf{C}) = P(\mathbf{J},V \mid\mathbf{Z}) for some Z\mathbf{Z}. Summing both sides over J\mathbf{J}, which does not occur in P(V∣C)P(V \mid\mathbf{C}), removes the first factor by (R1) and marginalises the right-hand side, leaving

P(V∣C)=P(V∣Z);(6)P(V \mid\mathbf{C}) = P(V \mid\mathbf{Z}); \tag*{(6)}

dividing the join identity by (6), which positivity permits, leaves

P(J∣D)=P(J∣V,Z).(7)P(\mathbf{J} \mid\mathbf{D}) = P(\mathbf{J} \mid V,\mathbf{Z}). \tag*{(7)}

If some c∈Cc \in\mathbf{C} were not in Z\mathbf{Z}, the right-hand side of (6) would not depend on cc, so that cc would be idle in P(V∣C)P(V \mid\mathbf{C}), against minimality; hence C⊆Z\mathbf{C} \subseteq\mathbf{Z}. The same argument applied to (7) gives D⊆Z∪{V}\mathbf{D} \subseteq\mathbf{Z} \cup\{V\}, and together these yield C⊆Z\mathbf{C} \subseteq\mathbf{Z}. Equation (6) states V⊥ ⁣ ⁣⊥Z∖C∣CV \perp\!\!\perp\mathbf{Z} \setminus\mathbf{C} \mid\mathbf{C}; since Z∖C\mathbf{Z} \setminus\mathbf{C} is the union of

C∖CC \setminus C and Z∖CZ \setminus C, decomposition gives V⊥ ⁣ ⁣ ⁣⊥C∖C∣CV \perp\!\!\!\perp C \setminus C \mid C, which is the second independence of (5) because (D∖{V})∖C=C∖C(D \setminus\{V\}) \setminus C = C \setminus C. Equation (7) states J⊥ ⁣ ⁣ ⁣⊥(Z∪{V})∖D∣DJ \perp\!\!\!\perp(Z \cup\{V\}) \setminus D \mid D; since (C∪{V})∖D(C \cup\{V\}) \setminus D is contained in (Z∪{V})∖D(Z \cup\{V\}) \setminus D, decomposition gives the first independence of (5), which closes the cycle. Moreover (4) then holds, and since both P(J,V∣Z)P(J,V \mid Z) and P(J,V∣C)P(J,V \mid C) equal the product of the two terms, the conditions in Z∖CZ \setminus C are idle.

(ii) If a condition c∈Cc \in C were idle in P(J,V∣C)P(J,V \mid C), the two terms would be joined at Z=C∖{c}Z = C \setminus\{c\}, and (i) would give C⊆C∖{c}C \subseteq C \setminus\{c\}, which is impossible.

By (ii), a join of minimal terms at CC produces a minimal joint, so that along a sequence of joins every joint is minimal, the theorem applies at every step, and no minimality check is needed between joins. The theorem also reduces the search of [8] to a single set. Suppose the search joins P(J∣D′)P(J \mid D') with P(V∣C)P(V \mid C) at some set Z=An(V)∪PZ = An(V) \cup P, where D′D' may contain, besides a minimal set DD, conditions that earlier joins have written although they are idle. The two products have the same value, so the minimal pair is joined at ZZ as well, and (i) gives C⊆ZC \subseteq Z and the join at CC. The test at CC therefore succeeds whenever the search does, and it is a single test, whereas the search examines up to 2∣Jπ∖An∗(V)∣2^{|J^\pi\setminus An^*(V)|} candidate sets before finding that the join is possible or impossible (Example 3.2). The single test is conclusive for minimal terms only, as we shall see in Example 3.3 below.

Example 3.2 (one test instead of a search). Consider the graph below, with the topological order X<Z<W<A<B<YX < Z < W < A < B < Y, and the query P(W,Y∣X^,Z^)P(W,Y \mid\hat{X},\hat{Z}).

Figure 1.

ID returns

P(W,Y∣X^,Z^)=∑A,BP(W∣Z) P(A) P(B) P(Y∣X,W,A,B).P(W,Y \mid\hat{X},\hat{Z}) = \sum_{A,B} P(W \mid Z)\,P(A)\,P(B)\,P(Y \mid X,W,A,B).

The participating terms of BB are P(Y∣X,W,A,B)P(Y \mid X,W,A,B) and P(B)P(B). By Theorem 3.1 their join is fixed at C=({X,W,A,B}∪∅)∖{B}={X,W,A}C = (\{X,W,A,B\} \cup\varnothing) \setminus\{B\} = \{X,W,A\}; the first independence of (5) is vacuous, and the second, B⊥ ⁣ ⁣ ⁣⊥{X,W,A}B \perp\!\!\!\perp\{X,W,A\}, holds, since B→YB \to Y is the only edge at BB. The joint is P(Y,B∣X,W,A)P(Y,B \mid X,W,A), and summing over BB gives P(Y∣X,W,A)P(Y \mid X,W,A), which is minimal. The participating terms of AA are then P(Y∣X,W,A)P(Y \mid X,W,A) and P(A)P(A); their join is fixed at C={X,W}C = \{X,W\}, and its second independence, A⊥ ⁣ ⁣ ⁣⊥{X,W}A \perp\!\!\!\perp\{X,W\}, fails because of X↔AX \leftrightarrow A. By the theorem no set joins the two terms, and the procedure stops at

P(W,Y∣X^,Z^)=∑AP(W∣Z) P(A) P(Y∣X,W,A).P(W,Y \mid\hat{X},\hat{Z}) = \sum_A P(W \mid Z)\,P(A)\,P(Y \mid X,W,A).

after two tests.

The procedure of TK reaches the same expression after 22 candidate sets, 14 for BB and 8 for AA. For BB it joins the same two terms; An(B)=∅An(B) = \varnothing and Jπ∖An∗(B)={X,Z,W,A}J^\pi\setminus An^*(B) = \{X,Z,W,A\}, so the candidates are the 16 subsets of {X,Z,W,A}\{X,Z,W,A\}, which we enumerate from the smallest. Every set that omits XX, WW or AA fails, because YY depends on the omitted variable, and {X,W,A}\{X,W,A\}, the fourteenth, is accepted; it is CC. For AA the candidates are the 8 subsets of {X,Z,W}\{X,Z,W\}. Those that omit XX or WW fail on the dependence of YY, and {X,W}\{X,W\} and {X,Z,W}\{X,Z,W\} fail because A̸ ⁣⊥ ⁣ ⁣ ⁣⊥XA \not\!\perp\!\!\!\perp X; all eight must be tried before the join is abandoned, and no variable is missing between AA and YY. Every set that the two searches reject is excluded beforehand by Theorem 3.1.

The difference grows with the graph, as the following family shows. Add mm intervened variables X1,…,XmX_1,\ldots,X_m, placed after XX in the order, each with the single edge Xi→YX_i \to Y, and consider P(W,Y∣X^,X^1,…,X^m,Z^)P(W,Y \mid\hat{X},\hat{X}_1,\ldots,\hat{X}_m,\hat{Z}). ID returns the same expression with X1,…,XmX_1,\ldots,X_m among the conditions of the term for YY, and the procedure of this paper still performs two tests, at C={X,X1,…,Xm,W,A}C = \{X,X_1,\ldots,X_m,W,A\} and at C={X,X1,…,Xm,W}C = \{X,X_1,\ldots,X_m,W\}. For TK the join of BB now has 2m+42^{m+4} candidate sets and is accepted at CC, only after every smaller set (2m+4−m−32^{m+4}-m-3 sets) has failed; the join of AA is abandoned only after all the 2m+32^{m+3} subsets of {X,X1,…,Xm,Z,W}\{X,X_1,\ldots,X_m,Z,W\} have failed.

Example 3.3 (the fixed join needs minimal terms). Consider the graph below, with the topological order A<B<X<Z<V<W<YA < B < X < Z < V < W < Y, and the query P(Z,Y∣A^,B^,X^,V^,W^)P(Z,Y \mid\hat{A},\hat{B},\hat{X},\hat{V},\hat{W}).

Figure 3 (PDF p. 7).

ID returns

P(Z,Y∣A^,B^,X^,V^,W^)=∑A,X,V,YQ∑A,X,Z,V,YQ∑A,XQ∑A,X,YQ.P(Z,Y \mid\hat{A},\hat{B},\hat{X},\hat{V},\hat{W}) = \frac{\sum_{A,X,V,Y} Q}{\sum_{A,X,Z,V,Y} Q} \frac{\sum_{A,X} Q}{\sum_{A,X,Y} Q}.
Q=P(A)P(X∣B)P(Z∣A,B,X)P(V∣A,B,X,Z)P(Y∣A,B,X,Z,V,W),Q = P(A)P(X \mid B)P(Z \mid A,B,X)P(V \mid A,B,X,Z)P(Y \mid A,B,X,Z,V,W),

where the summations of the fractions bind their own variables. The outcomes ZZ and YY form the only c-component of the graph without the intervened variables, and their c-component in GG is {A,X,Z,V,Y}\{A,X,Z,V,Y\}, so that ID reaches line 7 at once, with the product QQ of the five terms of this c-component, written with the minimal conditioning sets of Section 2. In the subgraph on the c-component, AA and XX are not ancestors of ZZ or YY and are summed at line 2, and line 6 writes the distribution of ZZ, and that of YY given ZZ and VV, as the two ratios. The first denominator sums every term to one, so that the first fraction, the distribution of ZZ, is its numerator,

∑A,X,V,YP(A)P(X∣B)P(Z∣A,B,X)P(V∣A,B,X,Z)P(Y∣A,B,X,Z,V,W),\sum_{A,X,V,Y} P(A)P(X \mid B)P(Z \mid A,B,X)P(V \mid A,B,X,Z)P(Y \mid A,B,X,Z,V,W),

an atomic expression with minimal terms, whose summation variables are tried in decreasing order.

The term for YY is the only one that contains YY, and it sums to one; the same then holds for VV. This leaves ∑A,XP(A)P(X∣B)P(Z∣A,B,X)\sum_{A,X} P(A)P(X \mid B)P(Z \mid A,B,X). The participating terms of XX are P(Z∣A,B,X)P(Z \mid A,B,X) and P(X∣B)P(X \mid B). By Theorem 3.1 their join is fixed at C=({A,B,X}∪{B})∖{X}={A,B}C = (\{A,B,X\} \cup\{B\}) \setminus\{X\} = \{A,B\}; the first independence of (5) is vacuous, since {B,X}⊆{A,B,X}\{B,X\} \subseteq\{A,B,X\}, and the second, X⊥ ⁣ ⁣ ⁣⊥A∣BX \perp\!\!\!\perp A \mid B, holds: the path X←B←AX \leftarrow B \leftarrow A is blocked at BB, and every other path at a collider, ZZ or YY, that is not given. The joint is P(Z,X∣A,B)P(Z,X \mid A,B), and summing over XX gives P(Z∣A,B)P(Z \mid A,B).

This term is not minimal: Z⊥ ⁣ ⁣ ⁣⊥B∣AZ \perp\!\!\!\perp B \mid A, because B←A↔ZB \leftarrow A \leftrightarrow Z is blocked at AA, and every path through XX at a collider, XX or YY, that is not conditioned on. The condition AA cannot be dropped, because of A↔ZA \leftrightarrow Z, so the minimal term is P(Z∣A)P(Z \mid A). With it, the participating terms of AA are P(Z∣A)P(Z \mid A) and P(A)P(A), their join at ∅\varnothing involves only vacuous tests, and summing over AA gives P(Z)P(Z): the four summations are removed, and the first fraction is P(Z)P(Z).

Suppose instead that the term is kept as the chain rule writes it, P(Z∣A,B)P(Z \mid A,B), with the idle condition BB inherited from P(X∣B)P(X \mid B). The participating terms of AA are P(Z∣A,B)P(Z \mid A,B) and P(A)P(A), and the set of Theorem 3.1 is C=({A,B}∪∅)∖{A}={B}C = (\{A,B\} \cup\varnothing) \setminus\{A\} = \{B\}. The first independence of (5) is vacuous, and the second, A⊥ ⁣ ⁣ ⁣⊥BA \perp\!\!\!\perp B, fails because of A→BA \to B; the insertion of BB, which lies above AA, requires the same independence (Section 4). The two terms can nevertheless be joined, since P(Z∣A,B)P(A)=P(Z∣A)P(A)=P(Z,A)P(Z \mid A,B)P(A) = P(Z \mid A)P(A) = P(Z,A). They are joined at ∅\varnothing, a set that does not contain CC, which Theorem 3.1 excludes for minimal terms only. For a term that is not minimal the test at CC is therefore not conclusive, and here it would leave the summation in ∑AP(A)P(Z∣A,B)\sum_A P(A)P(Z \mid A,B), a correct expression, equal to P(Z)P(Z). For this reason the procedure of Section 5 minimises every term that it writes after a summation.3

The procedure of TK removes the four summations as well, with a search in place of the minimisation. It sums YY and VV as above, and for XX it joins P(Z∣A,B,X)P(Z \mid A,B,X) with P(X∣B)P(X \mid B); here An(X)={A,B}An(X) = \{A,B\} and Jπ∖An∗(X)=∅J^{\pi} \setminus An^{*}(X) = \varnothing, so the only candidate set is {A,B}\{A,B\}, which is accepted, and the summation leaves P(Z∣A,B)P(Z \mid A,B), which TK does not minimise. For AA it joins P(Z∣A,B)P(Z \mid A,B) with P(A)P(A); now An(A)=∅An(A) = \varnothing and Jπ∖An∗(A)={B}J^{\pi} \setminus An^{*}(A) = \{B\}, so the candidate sets are ∅\varnothing and {B}\{B\}. At the first test of TK is Z⊥ ⁣ ⁣ ⁣⊥B∣AZ \perp\!\!\!\perp B \mid A, the statement that BB is idle, and the second is vacuous; the candidate is accepted, the joint is P(Z,A)P(Z,A), and the result is P(Z)P(Z). The search thus performs at each join the check that a minimisation performs once after each summation, and the single test of Theorem 3.1 replaces the search only if the terms are kept minimal.

In the second fraction no summation can be removed from the numerator, by either procedure. Its denominator behaves like the expression above: with the minimisation it reduces to P(Z)P(V)P(Z)P(V), without it the procedure stops at ∑AP(A)P(Z∣A,B)P(V∣A,B,Z)\sum_A P(A)P(Z \mid A,B)P(V \mid A,B,Z), and TK returns P(Z)P(V∣Z)P(Z)P(V \mid Z), in which ZZ is idle.

Insertion

By Theorem 3.1, the join of the joint P(J∣D)P(\mathbf{J}\mid\mathbf{D}) with the next term P(V∣C)P(V\mid C) fails when one of the two independences (5) fails. When the second one fails, VV depends, given CC, on a condition MM of the joint, M∉CM\notin C. If MM lies above VV, this dependence can be removed by turning MM into a head of the joint: a term for MM is multiplied into the joint, and divided out after the summation, which requires it not to depend on SS. This is the insertion of [8], and by Proposition 2.5 the only variables that need to be inserted are those of N\mathbf{N}, the conditions of participating terms that head none of them.

A participating term contains SS, as its head or as a condition below its head, so every participating head lies at or above SS. The procedure inserts the variables of N\mathbf{N} above SS and keeps the others as conditions:

R:={x∈N:x>S},L:={x∈N:x<S}.\mathbf{R}:=\{x\in\mathbf{N}:x>S\},\qquad\mathbf{L}:=\{x\in\mathbf{N}:x<S\}.

The final joint is then P(H∪R∣L)P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L}), a reduced assembly in the sense of Definition 2.4. Let h1<⋯<hmh_1<\cdots<h_m be its heads in topological order; the joint is assembled from hmh_m down to h1h_1, and the chain rule conditions each head on L\mathbf{L} and on the heads below it:

Eh:=L∪{x∈H∪R:x<h},h∈H∪R.(8)\mathbf{E}_h:=\mathbf{L}\cup\{x\in\mathbf{H}\cup\mathbf{R}:x<h\},\qquad h\in\mathbf{H}\cup\mathbf{R}. \tag*{(8)}

Since L\mathbf{L} lies below SS and every head lies at or above SS, this set consists of all the variables of H∪N\mathbf{H}\cup\mathbf{N} below hh:

Eh={x∈H∪N:x<h},h∈H∪R.\mathbf{E}_h=\{x\in\mathbf{H}\cup\mathbf{N}:x<h\},\qquad h\in\mathbf{H}\cup\mathbf{R}.

Lemma 4.1 (Elimination through insertions). There exist terms tMt_M, with M∈RM\in\mathbf{R}, each a conditional distribution of MM given variables of EM\mathbf{E}_M and free of SS, such that

∏h∈HP(h∣Ch)∏M∈RtM=P(H∪R∣L),(9)\prod_{h\in\mathbf{H}}P(h\mid C_h)\prod_{M\in\mathbf{R}}t_M=P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L}), \tag*{(9)}

if and only if

(a) P(h∣Ch)=P(h∣Eh)P(h\mid C_h)=P(h\mid\mathbf{E}_h) for every h∈Hh\in\mathbf{H}, and

(b) M⊥ ⁣ ⁣ ⁣⊥S∣EM∖{S}M\perp\!\!\!\perp S\mid\mathbf{E}_M\setminus\{S\} for every M∈RM\in\mathbf{R}.

In that case tM=P(M∣EM)=P(M∣EM∖{S})t_M=P(M\mid\mathbf{E}_M)=P(M\mid\mathbf{E}_M\setminus\{S\}) for every M∈RM\in\mathbf{R}, and

∑S∏h∈HP(h∣Ch)=∏h∈H∖{S}P(h∣Eh∖{S}),(10)\sum_S\prod_{h\in\mathbf{H}}P(h\mid C_h)=\prod_{h\in\mathbf{H}\setminus\{S\}}P(h\mid\mathbf{E}_h\setminus\{S\}), \tag*{(10)}

where no term on the right-hand side contains SS.

Proof. If the terms tMt_M exist, every factor of the product is conditioned only on variables below its head, so the highest head hmh_m occurs only in its own factor. Summing both sides over hmh_m removes that factor by (R1) and shows that the product of the other factors is P({h1,…,hm−1}∣L)P(\{h_1,\ldots,h_{m-1}\}\mid\mathbf{L}); dividing (9) by this product (which positivity permits), the factor of hmh_m is P(hm∣L∪{h1,…,hm−1})=P(hm∣Ehm)P(h_m\mid\mathbf{L}\cup\{h_1,\ldots,h_{m-1}\})=P(h_m\mid\mathbf{E}_{h_m}). Descending induction shows that every factor is the one that the chain rule assigns to its head: for h∈Hh\in\mathbf{H} this is (a), and for M∈RM\in\mathbf{R} it gives tM=P(M∣EM)t_M=P(M\mid\mathbf{E}_M), which is free of SS, that is, (b).

Conversely, under (a) and (b) the terms tM=P(M∣EM)=P(M∣EM∖{S})t_M=P(M\mid\mathbf{E}_M)=P(M\mid\mathbf{E}_M\setminus\{S\}) are free of SS, and by the chain rule and (a) they complete the participating terms to P(H∪R∣L)P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L}). Dividing by the terms tMt_M and summing over SS, which occurs neither in them nor in L\mathbf{L}, gives by (R2) and (R4)

∑S∏h∈HP(h∣Ch)=P((H∪R)∖{S}∣L)∏M∈RP(M∣EM∖{S}).\sum_S\prod_{h\in\mathbf{H}}P(h\mid C_h)=\frac{P((\mathbf{H}\cup\mathbf{R})\setminus\{S\}\mid\mathbf{L})}{\prod_{M\in\mathbf{R}}P(M\mid\mathbf{E}_M\setminus\{S\})}.

The chain rule for the numerator assigns to each h≠Sh\ne S the set Eh∖{S}\mathbf{E}_h\setminus\{S\}, and the factors with h∈Rh\in\mathbf{R} cancel against the denominator, which gives (10). ▫

Condition (a), on the participating terms, states that h⊥ ⁣ ⁣⊥Eh∖Ch∣Chh \perp\!\!\perp E_h \setminus C_h \mid C_h, since Ch⊆EhC_h \subseteq E_h; in other words, a term must be independent on every variable of the joint below its head that its minimal conditioning set ChC_h does not carry. Condition (b), on the inserted terms, requires the term inserted for MM, which by the lemma is necessarily P(M∣EM)P(M \mid E_M), not to depend on SS, so that it can be divided out after the summation. As for the join set in Theorem 3.1, the conditioning set of an inserted term is fixed, so that the insertion is decided at a single set, without a search: condition (b) for the inserted term, and condition (a) for the terms already assembled, which must not depend on the conditions that enter the joint with it. The procedure of TK searches for this set among the sets An(M)∪PAn(M) \cup P, P⊆Jπ∖An∗(M)P \subseteq J^{\pi} \setminus An^{*}(M); by the lemma, whatever set the search accepts, the inserted term is P(M∣EM)P(M \mid E_M). The set EME_M is determined by all the participating terms, including those joined after MM (Example 4.2). The lemma and its proof hold unchanged for any R⊆NR \subseteq N, with L=N∖RL = N \setminus R and the sets (8).

The terms written by (10) are conditioned on Eh∖{S}E_h \setminus\{S\}, below their heads, so the procedure maintains the property assumed in § 2. They need not be minimal: Eh∖{S}E_h \setminus\{S\} contains every variable of the joint below hh, and the summation over SS can make some of them idle (Example 3.3). Neither the lemma nor its proof uses minimality; conditions (a) and (b) refer to the conditioning sets as they are written. In the rest of the section we work out two examples. In Example 4.2 the inserted term needs a condition that only a term joined later carries, which shows the importance of considering the full sets RR and LL ab initio. Example 4.3 shows again the importance of participation when insertions are used: a term of OS\mathcal{O}_S cannot be joined, while its head can be inserted with another conditioning set.

Example 4.2 (the conditioning set of an inserted term). Consider the graph below, with the topological order v0<v1<⋯<v5v_0 < v_1 < \cdots< v_5, and the query P(v2,v5∣v^0,v^4)P(v_2, v_5 \mid\hat{v}_0, \hat{v}_4).

Figure 1 (PDF p. 9).

ID returns

P(v2,v5∣v^0,v^4)=∑v1P(v1∣v0) P(v2∣v1) P(v5∣v1,v4).P(v_2, v_5 \mid\hat{v}_0, \hat{v}_4) = \sum_{v_1} P(v_1 \mid v_0)\,P(v_2 \mid v_1)\,P(v_5 \mid v_1, v_4).

All three terms contain v1v_1, so that H={v1,v2,v5}\mathbf{H} = \{v_1, v_2, v_5\} and N={v0,v4}\mathbf{N} = \{v_0, v_4\}; hence R={v4}\mathbf{R} = \{v_4\} and L={v0}\mathbf{L} = \{v_0\}, and the variables are assembled in the order v5,v4,v2,v1v_5, v_4, v_2, v_1.

  1. The term P(v5∣v1,v4)P(v_5 \mid v_1, v_4) forms the initial joint, with J={v5}\mathbf{J} = \{v_5\} and D={v1,v4}\mathbf{D} = \{v_1, v_4\}.

  2. To insert the variable v4v_4, (8) gives Ev4={v0,v1,v2}E_{v_4} = \{v_0, v_1, v_2\}, and condition (b) requires v4⊥ ⁣ ⁣⊥v1∣v0,v2v_4 \perp\!\!\perp v_1 \mid v_0, v_2, which

Example 4.3 (a retained term between the participating terms). Consider the graph below, with the topological order v0<v1<v2<v3<v4v_0 < v_1 < v_2 < v_3 < v_4, and the query P(v2,v4∣v^0)P(v_2, v_4 \mid\hat{v}_0).

Figure 4.

ID returns

P(v2,v4∣v^0)=∑v1,v3P(v1)P(v2∣v1)P(v3∣v2)P(v4∣v0,v1,v3).P(v_2, v_4 \mid\hat{v}_0) = \sum_{v_1,v_3} P(v_1) P(v_2 \mid v_1) P(v_3 \mid v_2) P(v_4 \mid v_0,v_1,v_3).

The summation variables are tried in decreasing order. The participating terms of v3v_3 are P(v4∣v0,v1,v3)P(v_4 \mid v_0,v_1,v_3) and P(v3∣v2)P(v_3 \mid v_2); their join is fixed at {v0,v1,v2}\{v_0,v_1,v_2\}, and its second independence, v3⊥ ⁣ ⁣ ⁣⊥{v0,v1}∣v2v_3 \mathrel{\perp\!\!\!\perp} \{v_0,v_1\} \mid v_2, fails because of v0↔v3v_0 \leftrightarrow v_3. No variable of N={v0,v1,v2}N = \{v_0,v_1,v_2\} lies above v3v_3, so nothing is inserted, and v3v_3 cannot be eliminated: v0v_0 lies below v3v_3, and no insertion removes it from Ev3E_{v_3}.

The participating terms of v1v_1 are P(v4∣v0,v1,v3)P(v_4 \mid v_0,v_1,v_3), P(v2∣v1)P(v_2 \mid v_1) and P(v1)P(v_1), while P(v3∣v2)P(v_3 \mid v_2), the term that could not be joined, remains outside the summation; here H={v1,v2,v4}H = \{v_1,v_2,v_4\} and N={v0,v3}N = \{v_0,v_3\}, so that R={v3}R = \{v_3\} and L={v0}L = \{v_0\}, and the order of assembly is v4,v3,v2,v1v_4,v_3,v_2,v_1.

  1. The term P(v4∣v0,v1,v3)P(v_4 \mid v_0,v_1,v_3) forms the initial joint, with J={v4}J = \{v_4\} and D={v0,v1,v3}D = \{v_0,v_1,v_3\}.

  2. To insert the variable v3v_3, (8) gives Ev3={v0,v1,v2}E_{v_3} = \{v_0,v_1,v_2\}, and condition (b) requires v3⊥ ⁣ ⁣ ⁣⊥v1∣v0,v2v_3 \mathrel{\perp\!\!\!\perp} v_1 \mid v_0,v_2, which holds: the path v1→v2→v3v_1 \to v_2 \to v_3 is blocked at v2v_2, and the paths through v4v_4 are blocked at the collider v4v_4, which is not given. The inserted term is P(v3∣v0,v2)P(v_3 \mid v_0,v_2), which by (b) equals P(v3∣v0,v1,v2)P(v_3 \mid v_0,v_1,v_2); it is joined at {v0,v1,v2}\{v_0,v_1,v_2\}, both independences holding, and the joint becomes P(v4,v3∣v0,v1,v2)P(v_4,v_3 \mid v_0,v_1,v_2).

  3. The join with P(v2∣v1)P(v_2 \mid v_1) is fixed at C={v0,v1}C = \{v_0,v_1\}; its second independence, v2⊥ ⁣ ⁣ ⁣⊥v0∣v1v_2 \mathrel{\perp\!\!\!\perp} v_0 \mid v_1, holds, and the joint becomes P(v4,v3,v2∣v0,v1)P(v_4,v_3,v_2 \mid v_0,v_1).

  4. The join with P(v1)P(v_1) at C={v0}C = \{v_0\} requires v1⊥ ⁣ ⁣ ⁣⊥v0v_1 \mathrel{\perp\!\!\!\perp} v_0, which holds, and the joint becomes P(v4,v3,v2,v1∣v0)P(v_4,v_3,v_2,v_1 \mid v_0).

  5. Summing over v1v_1 and factorising in the order of assembly gives P(v4∣v0,v2,v3)P(v3∣v0,v2)P(v2)P(v_4 \mid v_0,v_2,v_3) P(v_3 \mid v_0,v_2) P(v_2), where P(v2∣v0)P(v_2 \mid v_0) has been minimised to P(v2)P(v_2); the factor of v3v_3 is the inserted term and is divided out. With P(v3∣v2)P(v_3 \mid v_2) restored by (R2),

P(v2,v4∣v^0)=∑v3P(v2)P(v3∣v2)P(v4∣v0,v2,v3).P(v_2,v_4 \mid\hat{v}_0) = \sum_{v_3} P(v_2) P(v_3 \mid v_2) P(v_4 \mid v_0,v_2,v_3).

Here the insertion of v3v_3 is forced: without it, the join of P(v4∣v0,v1,v3)P(v_4 \mid v_0,v_1,v_3) with P(v2∣v1)P(v_2 \mid v_1) would fail, since v2̸ ⁣⊥ ⁣ ⁣ ⁣⊥v3∣v1v_2 \not\!\perp\!\!\!\perp v_3 \mid v_1 because of v2→v3v_2 \to v_3. A further attempt on v3v_3 fails as before, since the join of P(v4∣v0,v2,v3)P(v_4 \mid v_0,v_2,v_3) with P(v3∣v2)P(v_3 \mid v_2) at {v0,v2}\{v_0,v_2\} requires v3⊥ ⁣ ⁣ ⁣⊥v0∣v2v_3 \mathrel{\perp\!\!\!\perp} v_0 \mid v_2. The term P(v3∣v2)P(v_3 \mid v_2) cannot be joined because of v0↔v3v_0 \leftrightarrow v_3; left outside the summation, it leaves its head free to be inserted with the conditioning set {v0,v1,v2}\{v_0,v_1,v_2\} that the chain rule requires, and the inserted term P(v3∣v0,v2)P(v_3 \mid v_0,v_2) differs from it by the condition v0v_0.

For TK the term P(v3∣v2)P(v_3 \mid v_2) takes part in the elimination of v3v_3 and, as a retained term, in that of v1v_1. To eliminate v3v_3, it joins P(v4∣v0,v1,v3)P(v_4 \mid v_0,v_1,v_3) with P(v3∣v2)P(v_3 \mid v_2), and both candidate sets, {v1,v2}\{v_1,v_2\} and {v0,v1,v2}\{v_0,v_1,v_2\}, fail; no variable is missing. To eliminate v1v_1, it must assemble v4,v3,v2v_4,v_3,v_2 and v1v_1, and, beginning with the same join, which fails again, and no variable between v1v_1 and v4v_4 is missing, since v2v_2 and v3v_3 head terms and v0v_0 lies below v1v_1, so that the expression is left unchanged. In the topological order v1<v2<v3<v0<v4v_1 < v_2 < v_3 < v_0 < v_4, however, v0v_0 lies between v1v_1 and v4v_4 and heads no term; the procedure then inserts it and eliminates v1v_1 as well.

The procedure

The previous sections determine every step of an elimination: the terms to assemble (Proposition 2.5), the set of each join (Theorem 3.1), and the term of each insertion (Lemma 4.1). This section combines them into a procedure that keeps the structure of TK, a loop over the summation variables that calls a join, which calls an insertion where one is required, followed by a factorisation, so that the two procedures can be compared step by step; the difference is that every set is computed and none is searched for.

Algorithms 1–5 state the procedure, under the names used in [8]. A term P(V∣C)P(V \mid C) is written ⟨V,C⟩\langle V,C\rangle, and a joint P(J∣D)P(J \mid D) is written ⟨J,D⟩\langle J,D\rangle, with conditioning set DD and heads JJ kept as a sequence in the order of assembly; (J,V)(J,V) denotes the sequence JJ followed by VV, and in set operations and independence statements JJ stands for the set of its elements. FAIL marks an unsuccessful call, and (⋅⊥ ⁣ ⁣ ⁣⊥⋅∣⋅)G(\cdot\mathrel{\perp\!\!\!\perp} \cdot\mid\cdot)_G a d-separation test in GG with its latent variables, true when either of its first two arguments is empty or contained in the third, and false when they share a variable outside the third.

Algorithm 1 Simplification of an atomic expression ∑S∏t∈Tt\sum_{S}\prod_{t\in T}t given graph GG and topological ordering π\pi.

1: function SIMPLIFY(T,S,G,π)(\mathbf{T},S,G,\pi) 2: j←0j \leftarrow0 3: while j<∣S∣j < |S| do 4: j←j+1j \leftarrow j+1 ▷ SjS_j: the jj-th of SS, in decreasing order of π\pi 5: P←{⟨V,C⟩∈T:V=Sj or Sj∈C}\mathcal{P} \leftarrow\{\langle V,C\rangle\in T: V=S_j\text{ or }S_j\in C\}; O←T∖P\mathcal{O}\leftarrow T\setminus\mathcal{P} ▷ participating terms 6: H←{V:⟨V,C⟩∈P}\mathbf{H}\leftarrow\{V:\langle V,C\rangle\in\mathcal{P}\}; N←(⋃⟨V,C⟩∈PC)∖H\mathbf{N}\leftarrow\left(\bigcup_{\langle V,C\rangle\in\mathcal{P}}C\right)\setminus\mathbf{H} 7: R←{x∈N:x>Sj}\mathbf{R}\leftarrow\{x\in\mathbf{N}:x>S_j\}; L←N∖R\mathbf{L}\leftarrow\mathbf{N}\setminus\mathbf{R} ▷ inserted variables 8: J←();D←∅;Q←∅;k←1\mathbf{J}\leftarrow(); \mathbf{D}\leftarrow\emptyset; \mathbf{Q}\leftarrow\emptyset; k\leftarrow1 9: while k≤∣P∣k\leq|\mathcal{P}| do ▷ ⟨Vk,Ck⟩\langle V_k,C_k\rangle: the kk-th term of P\mathcal{P}, by decreasing head 10: r←JOIN⁡(J,D,Vk,Ck,H,R,L,Sj,G)r\leftarrow\operatorname{JOIN}(\mathbf{J},\mathbf{D},V_k,C_k,\mathbf{H},\mathbf{R},\mathbf{L},S_j,G) 11: if r=FAIL⁡r=\operatorname{FAIL} then break 12: ⟨J,D,Q′⟩←r\langle\mathbf{J},\mathbf{D},\mathbf{Q}'\rangle\leftarrow r; Q←Q∪Q′\mathbf{Q}\leftarrow\mathbf{Q}\cup\mathbf{Q}'; k←k+1k\leftarrow k+1 13: if k>∣P∣k>|\mathcal{P}| then ▷ ∏P⋅∏Q=P(J∣D)\prod\mathcal{P}\cdot\prod\mathbf{Q}=P(\mathbf{J}\mid\mathbf{D}) 14: T←O∪FACTORIZE⁡(J,D,Sj,Q,G)T\leftarrow\mathcal{O}\cup\operatorname{FACTORIZE}(\mathbf{J},\mathbf{D},S_j,\mathbf{Q},G) ▷ sum out SjS_j, divide by Q\mathbf{Q} 15: S←S∖{Sj}S\leftarrow S\setminus\{S_j\}; j←0j\leftarrow0 ▷ restart on the new terms 16: return ⟨T,S⟩\langle T,S\rangle

For each summation variable SjS_j, lines 5–7 determine the participating terms, their heads H\mathbf{H}, the set N\mathbf{N} of Definition 2.2, and the inserted variables R\mathbf{R} of Section 4; the terms of O\mathcal{O} are put back unchanged after the summation, by (R2). The loop of lines 9–12 takes the participating terms in decreasing order of their heads and calls JOIN for each; JOIN calls INSERT for the variables of R\mathbf{R} that lie above the head, so that the participating heads and the inserted variables are assembled in decreasing order. When the loop completes, the participating terms times the inserted terms equal P(J∣D)P(\mathbf{J}\mid\mathbf{D}), and FACTORIZE sums out SjS_j and divides by the inserted terms (line 14); SjS_j is removed, and the summation variables are tried again from the first, since one elimination may enable another.

Algorithm 2 Join of P(J∣D)P(\mathbf{J}\mid\mathbf{D}) with P(V∣C)P(V\mid C) at the set CC of Theorem 3.1, after the insertion of the variables of R\mathbf{R} above VV.

1: function JOIN(J,D,V,C,H,R,L,S,G)(\mathbf{J},\mathbf{D},V,C,\mathbf{H},\mathbf{R},\mathbf{L},S,G) 2: if J=()\mathbf{J}=() then return ⟨(V),C,∅⟩\langle(V),C,\emptyset\rangle ▷ the initial joint 3: Q′←∅\mathbf{Q}'\leftarrow\emptyset 4: for M∈DM\in\mathbf{D} with M>VM>V, in decreasing order do ▷ conditions above VV: inserted first 5: r←INSERT⁡(J,D,M,H,R,L,S,G)r\leftarrow\operatorname{INSERT}(\mathbf{J},\mathbf{D},M,\mathbf{H},\mathbf{R},\mathbf{L},S,G) 6: if r=FAIL⁡r=\operatorname{FAIL} then return FAIL 7: ⟨J,D,q⟩←r\langle\mathbf{J},\mathbf{D},q\rangle\leftarrow r; Q′←Q′∪{q}\mathbf{Q}'\leftarrow\mathbf{Q}'\cup\{q\} 8: C←(D∪C)∖{V}C\leftarrow(\mathbf{D}\cup C)\setminus\{V\} ▷ the set of Theorem 3.1 9: if (J⊥ ⁣ ⁣ ⁣⊥(C∪{V})∖D∣D)G(J\mathrel{\perp\!\!\!\perp}(C\cup\{V\})\setminus\mathbf{D}\mid\mathbf{D})_G and (V⊥ ⁣ ⁣ ⁣⊥(D∖{V})∖C∣C)G(V\mathrel{\perp\!\!\!\perp}(\mathbf{D}\setminus\{V\})\setminus C\mid C)_G then 10: return ⟨(J,V),C,Q′⟩\langle(\mathbf{J},V),C,\mathbf{Q}'\rangle ▷ P(J,V∣C)P(\mathbf{J},V\mid C) 11: return FAIL

JOIN returns the term itself when the joint is empty (line 2). Otherwise it first inserts the conditions of the joint that lie above VV, from the highest down (lines 4–7). These are the variables of R\mathbf{R} above VV, and each must become a head before VV is joined, so that every head is conditioned only on variables below it. It then tests the two independences of Theorem 3.1 at the set CC and nowhere else (lines 8–9). By Theorem 3.1(ii) a join of minimal terms produces a minimal joint.

Lines 4–7 insert every condition MM of the joint that lies above VV, whether or not the insertion is necessary. It is necessary when a term P(V∣C)P(V\mid C) with head below MM depends on MM without having it among its conditions (V̸ ⁣⊥ ⁣ ⁣ ⁣⊥M∣C(V\not\!\perp\!\!\!\perp M\mid C, so that the second independence of (5) fails), and otherwise each remaining join would succeed with MM kept as a condition (V⊥ ⁣ ⁣ ⁣⊥M∣C(V\mathrel{\perp\!\!\!\perp}M\mid C, as a⊥ ⁣ ⁣ ⁣⊥ba\mathrel{\perp\!\!\!\perp}b in (2)), which is how TK proceeds, inserting only after a join has failed. We insert in both cases because this fixes the conditioning set of each inserted term in advance, at no cost in eliminations (Corollary 6.1).

Algorithm 3 Insertion of a term for MM into the joint P(J∣D)P(\mathbf{J}\mid\mathbf{D}).

  1. function Insert⁡(J,D,M,H,R,L,S,G)\operatorname{Insert}(\mathbf{J},\mathbf{D},M,\mathbf{H},\mathbf{R},L,S,G)

  2. E←(L∪{x∈H∪R:x<M})∖{S}\mathbf{E}\leftarrow\left(L\cup\{x\in\mathbf{H}\cup\mathbf{R}:x<M\}\right)\setminus\{S\} ▷ the set (8), without SS

  3. if not (M⊥ ⁣ ⁣ ⁣⊥S∣E)G(M\mathrel{\perp\!\!\!\perp}S\mid\mathbf{E})_{G} then return fail ▷ condition (b)

  4. if not (J⊥ ⁣ ⁣ ⁣⊥E∖D∣D)G(\mathbf{J}\mathrel{\perp\!\!\!\perp}\mathbf{E}\setminus\mathbf{D}\mid\mathbf{D})_{G} then return fail ▷ condition (a) for the heads of J\mathbf{J}

  5. return ⟨(J,M),(D∪E)∖{M},⟨M,E⟩⟩\langle(\mathbf{J},M),(\mathbf{D}\cup\mathbf{E})\setminus\{M\},\langle M,\mathbf{E}\rangle\rangle

Insert computes the conditioning set (8) without SS, fixed by Lemma 4.1 (line 2), and performs two tests. The first is condition (b): the inserted term P(M∣E)P(M\mid\mathbf{E}) does not depend on SS (line 3). The second asks that the joint assembled so far keep its value when it is conditioned on E\mathbf{E} as well (line 4): the terms already absorbed may not depend on the variables below MM that enter the joint with the inserted term, which is condition (a) for their heads. When MM is inserted, MM and SS are conditions of the joint and every other condition lies in E\mathbf{E}, so that the new conditioning set (D∪E)∖{M}(\mathbf{D}\cup\mathbf{E})\setminus\{M\} is E∪{S}\mathbf{E}\cup\{S\} (line 5). The two tests are those of Theorem 3.1 for the join of P(J∣D)P(\mathbf{J}\mid\mathbf{D}) with P(M∣E)P(M\mid\mathbf{E}) at this set, and those of the insertion of TK⁡\operatorname{TK} at the single candidate E∪{S}\mathbf{E}\cup\{S\}. The inserted term is not minimised: its conditioning set is fixed by the chain rule, and the term is later divided out.

Algorithm 4 Summation over SS of the joint P(J∣D)P(\mathbf{J}\mid\mathbf{D}), inserted terms divided out.

  1. function Factorize⁡(J,D,S,Q,G)\operatorname{Factorize}(\mathbf{J},\mathbf{D},S,\mathbf{Q},G)

  2. T′←∅\mathbf{T}'\leftarrow\varnothing ▷ J=(jm,…,j1)\mathbf{J}=(j_m,\ldots,j_1) in the order of assembly, jm>⋯>j1j_m>\cdots>j_1

  3. for i=m,…,1i=m,\ldots,1 do

  4. if ji=Sj_i=S or a term with head jij_i is in Q\mathbf{Q} then

  5. continue ▷ summed out, or divided out

  6. T′←T′∪{⟨ji,Minimize⁡({ji},(D∪{j1,…,ji−1})∖{S},G)⟩}\mathbf{T}'\leftarrow\mathbf{T}'\cup\{ \langle j_i,\operatorname{Minimize}(\{j_i\},(\mathbf{D}\cup\{j_1,\ldots,j_{i-1}\})\setminus\{S\},G)\rangle\} ▷ its factor, minimal

  7. return T′\mathbf{T}'

Factorize carries out the summation by the argument of Lemma 4.1. The joint assembled by the loop is a product of the participating terms and of the inserted terms, and each of them is the factor that the chain rule assigns to its head, that is, the factor of jij_i given D\mathbf{D} and ji+1,…,jmj_{i+1},\ldots,j_m. Summing over SS leaves a joint distribution of the other heads, whose chain rule assigns to jij_i the set (D∪{ji+1,…,jm})∖{S}(\mathbf{D}\cup\{j_{i+1},\ldots,j_m\})\setminus\{S\}. For an inserted head this factor equals the inserted term, which does not depend on SS; it cancels against the division by that term, and the head is skipped (lines 4–5). Every other factor is returned with a minimal conditioning set (line 6).

Algorithm 5 A minimal conditioning set for a term or joint with heads W\mathbf{W}.

  1. function Minimize⁡(W,C,G)\operatorname{Minimize}(\mathbf{W},\mathbf{C},G)

  2. repeat

  3. removed ←\leftarrow false

  4. for c∈Cc\in\mathbf{C} do

  5. if (W⊥ ⁣ ⁣ ⁣⊥c∣C∖{c})G(\mathbf{W}\mathrel{\perp\!\!\!\perp}c\mid\mathbf{C}\setminus\{c\})_{G} then ▷ cc is idle: P(W∣C)=P(W∣C∖{c})P(\mathbf{W}\mid\mathbf{C})=P(\mathbf{W}\mid\mathbf{C}\setminus\{c\})

  6. C←C∖{c}\mathbf{C}\leftarrow\mathbf{C}\setminus\{c\}; removed ←\leftarrow true; break

  7. until removed = false

  8. return C\mathbf{C} ▷ no single condition can be dropped

Minimize drops idle conditions one at a time; dropping one may make another droppable, so it repeats until none can be dropped, and the result is minimal in the sense of Definition 2.1. Only Factorize calls it, for every term it returns: a condition left idle by the summation would be read as a condition at the next join, and the test at C\mathbf{C} could then fail for terms that can be joined (Example 3.3).

The next proposition states that the procedure is correct, and that it decides the two conditions of Lemma 4.1: the loop of Simplify completes whenever the summation can be carried out through the joint P(H∪R∣L)P(\mathbf{H}\cup\mathbf{R}\mid L), and the expression that it then writes equals the original one.

Proposition 5.1. If the participating terms are minimal and the loop of lines 9–12 of Simplify completes for SjS_j, line 14 replaces the terms by an expression equal to ∑Sj∏t∈Tt\sum_{S_j}\prod_{t\in T}t, in which SjS_j does not occur and every term is minimal. Conversely, if conditions (a) and (b) of Lemma 4.1 hold for the set R\mathbf{R} of line 7, the loop completes.

Proof. Each absorbed term is the factor that the chain rule, in the order of assembly, assigns to its head. Indeed, suppose this holds for the joint P(J∣D)P(\mathbf{J}\mid\mathbf{D}), and let Join absorb the next term at CC, so that J⊥ ⁣ ⁣ ⁣⊥W∣D\mathbf{J}\perp\!\!\!\perp\mathbf{W}\mid\mathbf{D} with W=(C∪{V})∖D\mathbf{W}=(C\cup\{V\})\setminus\mathbf{D}. For a head aa of J\mathbf{J} and the set Y\mathbf{Y} of heads absorbed after it, decomposition gives {a}∪Y⊥ ⁣ ⁣ ⁣⊥W∣D\{a\}\cup\mathbf{Y}\perp\!\!\!\perp\mathbf{W}\mid\mathbf{D}, and symmetry and weak union give a⊥ ⁣ ⁣ ⁣⊥W∣D∪Ya\perp\!\!\!\perp\mathbf{W}\mid\mathbf{D}\cup\mathbf{Y}, so that the factor of aa given D∪Y\mathbf{D}\cup\mathbf{Y} is also its factor given C∪{V}∪YC\cup\{V\}\cup\mathbf{Y}, which is the set that the chain rule assigns to it after the join; the new term is the factor of VV given CC by the second independence. An insertion is the same step for the term P(M∣E)P(M\mid E). When Insert is called for MM, the heads of the joint are the variables of H∪R\mathbf{H}\cup\mathbf{R} above MM; MM and SjS_j are conditions of participating terms already absorbed, and every other condition of the joint lies below MM, hence in E\mathbf{E}. The term is thus absorbed at (D∪E)∖{M}=E∪{Sj}(\mathbf{D}\cup\mathbf{E})\setminus\{M\}=\mathbf{E}\cup\{S_j\}; line 4 of Insert is the first independence, with W=E∖D\mathbf{W}=\mathbf{E}\setminus\mathbf{D}, and line 3 is the second, since (D∖{M})∖E={Sj}(\mathbf{D}\setminus\{M\})\setminus\mathbf{E}=\{S_j\}. When the loop completes, the participating terms times the inserted terms therefore equal P(J∣D)P(\mathbf{J}\mid\mathbf{D}); the inserted terms are free of SjS_j, so they leave the summation by (R2), and the summation removes SjS_j from the heads. Factorize writes the result by the chain rule, divides by the inserted terms as explained above, and minimises; Minimize drops only idle conditions, and the terms of O\mathcal{O} are restored by (R2).

Conversely, under (a) and (b) the factors P(h∣Eh)P(h\mid E_h) of Lemma 4.1, taken from the highest variable of H∪R\mathbf{H}\cup\mathbf{R} down to any variable gg, multiply to the joint distribution of these variables given EgE_g, so that the joint assembled when gg has been absorbed satisfies P(J∣D)=P(J∣Eg)P(\mathbf{J}\mid\mathbf{D})=P(\mathbf{J}\mid E_g), with D⊆Eg\mathbf{D}\subseteq E_g. The next variable to be absorbed, VV, is the next one below gg in H∪R\mathbf{H}\cup\mathbf{R}, so that Eg=EV∪{V}E_g=E_V\cup\{V\}. The first test of Join, and line 4 of Insert, ask that J\mathbf{J} be independent, given D\mathbf{D}, of variables of Eg∖DE_g\setminus\mathbf{D}, which follows by decomposition. The second test of Join asks that VV be independent, given CC, of variables of EV∖CE_V\setminus C, which follows from (a) by decomposition, and line 3 of Insert is (b); hence every test succeeds, and the loop completes. □

The procedure makes no search: every set it tests is computed, so its cost is polynomial, whereas a join of TK may examine up to 2∣Jπ∖An⁡∗(V)∣2^{|\mathbf{J}^{\pi}\setminus\operatorname{An}^{*}(V)|} candidate sets (Example 3.2). We count d-separation tests, each of which takes time linear in the size of GG [9].

Proposition 5.2 (Cost). Let GG have nn variables, and let one attempt, for one summation variable, assemble m=∣H∪R∣m=|\mathbf{H}\cup\mathbf{R}| heads. The attempt performs at most 2m2m tests in Join and Insert and at most m−1m-1 calls of Minimize, each of which performs at most c(c+1)c(c+1) tests for a set of c≤nc\le n conditions. A run with kk summation variables makes at most k(k+1)/2k(k+1)/2 attempts, and therefore O(k2n3)O(k^2n^3) tests in all.

Proof. The loop calls Join, with two tests, once for each participating term, and Join calls Insert, with two tests, once for each variable of R\mathbf{R}, so that there are at most 2(∣H∣+∣R∣)=2m2(|\mathbf{H}|+|\mathbf{R}|)=2m tests. Factorize calls Minimize once for each head of the joint that is neither summed out nor divided out, that is, for each participating head other than SjS_j; since SjS_j is itself one of the mm heads, there are at most ∣H∣−1≤m−1|\mathbf{H}|-1\le m-1 calls. Each pass of the loop of Minimize performs at most cc tests and either removes a condition or ends the call, so there are at most c+1c+1 passes. Between two successful eliminations, Simplify tries each remaining summation variable at most once, so a run makes at most k+(k−1)+⋯+1k+(k-1)+\cdots+1 attempts; since m≤nm\le n, each attempt makes O(n3)O(n^3) tests. □

The next example traces a whole run through the algorithms, on a graph for which TK removes no summation in any topological order.

Example 5.3 (a run of the procedure). Consider the graph below, with the topological order v0<v1<⋯<v5v_0<v_1<\cdots<v_5, and the query P(v4,v5∣v2)P(v_4,v_5\mid v_2).

Figure 5.3.

ID returns

P(v4,v5∣v^2)=∑v0,v1,v3P(v0)P(v1∣v0)P(v3∣v1)P(v4∣v0,v1,v3)P(v5∣v1,v2,v3),P(v_{4},v_{5}\mid\hat{v}_{2})=\sum_{v_{0},v_{1},v_{3}}P(v_{0})P(v_{1}\mid v_{0})P(v_{3}\mid v_{1})P(v_{4}\mid v_{0},v_{1},v_{3})P(v_{5}\mid v_{1},v_{2},v_{3}),

and Simplify tries the summation variables in the order v3,v1,v0v_{3},v_{1},v_{0}.

v3v_{3}. Line 5 selects the terms that contain v3v_{3}, namely P(v3∣v1)P(v_{3}\mid v_{1}), P(v4∣v0,v1,v3)P(v_{4}\mid v_{0},v_{1},v_{3}) and P(v5∣v1,v2,v3)P(v_{5}\mid v_{1},v_{2},v_{3}). Lines 6–7 give H={v3,v4,v5}\mathbf{H}=\{v_{3},v_{4},v_{5}\} and N={v0,v1,v2}\mathbf{N}=\{v_{0},v_{1},v_{2}\}, which lies below v3v_{3}, so that R=∅\mathbf{R}=\varnothing and L=N\mathbf{L}=\mathbf{N}. The loop begins with v5v_{5}, whose term is the initial joint ⟨(v5),{v1,v2,v3}⟩\langle(v_{5}),\{v_{1},v_{2},v_{3}\}\rangle, and calls Join for P(v4∣v0,v1,v3)P(v_{4}\mid v_{0},v_{1},v_{3}) at C={v0,v1,v2,v3}C=\{v_{0},v_{1},v_{2},v_{3}\}. The first test, v5⊥ ⁣ ⁣ ⁣⊥{v0,v4}∣v1,v2,v3v_{5}\perp\!\!\!\perp\{v_{0},v_{4}\}\mid v_{1},v_{2},v_{3}, holds; the second, v4⊥ ⁣ ⁣ ⁣⊥v2∣v0,v1,v3v_{4}\perp\!\!\!\perp v_{2}\mid v_{0},v_{1},v_{3}, fails, because the path v4↔v0↔v2v_{4}\leftrightarrow v_{0}\leftrightarrow v_{2} is open when its collider v0v_{0} is given, and the loop breaks at line 11.

v1v_{1}. Now P(v1∣v0)P(v_{1}\mid v_{0}) participates as well, H={v1,v3,v4,v5}\mathbf{H}=\{v_{1},v_{3},v_{4},v_{5}\}, N={v0,v2}\mathbf{N}=\{v_{0},v_{2}\}, R={v2}\mathbf{R}=\{v_{2}\} and L={v0}\mathbf{L}=\{v_{0}\}. The loop again begins with v5v_{5} and v4v_{4}, and the same join fails: v2v_{2}, which lies below v4v_{4}, is inserted only later, and is still a condition of the joint when v4v_{4} is joined.

v0v_{0}. Line 5 selects P(v0)P(v_{0}), P(v1∣v0)P(v_{1}\mid v_{0}) and P(v4∣v0,v1,v3)P(v_{4}\mid v_{0},v_{1},v_{3}), and puts P(v3∣v1)P(v_{3}\mid v_{1}) and P(v5∣v1,v2,v3)P(v_{5}\mid v_{1},v_{2},v_{3}) in O\mathcal{O}. Then H={v0,v1,v4}\mathbf{H}=\{v_{0},v_{1},v_{4}\}, N={v3}\mathbf{N}=\{v_{3}\}, R={v3}\mathbf{R}=\{v_{3}\} and L=∅\mathbf{L}=\varnothing, and the loop calls Join for the terms of v4v_{4}, v1v_{1} and v0v_{0}.

  1. The term for v4v_{4} is the initial joint ⟨(v4),{v0,v1,v3}⟩\langle(v_{4}),\{v_{0},v_{1},v_{3}\}\rangle.

  1. Called for P(v1∣v0)P(v_{1}\mid v_{0}), Join first inserts v3v_{3}, the variable of R\mathbf{R} above v1v_{1}. Insert computes E={v1}\mathbf{E}=\{v_{1}\} (line 2) and tests v3⊥ ⁣ ⁣ ⁣⊥v0∣v1v_{3}\perp\!\!\!\perp v_{0}\mid v_{1} (line 3), which holds: v3←v1←v0v_{3}\leftarrow v_{1}\leftarrow v_{0} is blocked at v1v_{1}, and v3↔v4↔v0v_{3}\leftrightarrow v_{4}\leftrightarrow v_{0} at the collider v4v_{4}, which is not given. The test of line 4 is vacuous, since E⊆D\mathbf{E}\subseteq\mathbf{D}. The joint is ⟨(v4,v3),{v0,v1}⟩\langle(v_{4},v_{3}),\{v_{0},v_{1}\}\rangle, and the inserted term is ⟨v3,{v1}⟩\langle v_{3},\{v_{1}\}\rangle.

  1. Join then adds P(v1∣v0)P(v_{1}\mid v_{0}) at {v0}\{v_{0}\} and, called for the last term, P(v0)P(v_{0}) at ∅\varnothing, with vacuous tests only; the joint is ⟨(v4,v3,v1,v0),∅⟩\langle(v_{4},v_{3},v_{1},v_{0}),\varnothing\rangle.

  1. Factorize (line 14) writes v4v_{4} with Minimize⁡({v4},{v1,v3})={v1,v3}\operatorname{Minimize}(\{v_{4}\},\{v_{1},v_{3}\})=\{v_{1},v_{3}\}, skips v3v_{3}, which is in Q\mathbf{Q}, writes v1v_{1} with the empty set, and skips v0v_{0}. With the terms of O\mathcal{O} restored,

P(v4,v5∣v^2)=∑v1,v3P(v1)P(v3∣v1)P(v4∣v1,v3)P(v5∣v1,v2,v3).P(v_{4},v_{5}\mid\hat{v}_{2})=\sum_{v_{1},v_{3}}P(v_{1})P(v_{3}\mid v_{1})P(v_{4}\mid v_{1},v_{3})P(v_{5}\mid v_{1},v_{2},v_{3}).

After line 15 has removed v0v_{0}, the new attempts on v3v_{3} and v1v_{1} again begin with the join of P(v5∣v1,v2,v3)P(v_{5}\mid v_{1},v_{2},v_{3}) and P(v4∣v1,v3)P(v_{4}\mid v_{1},v_{3}), now at {v1,v2,v3}\{v_{1},v_{2},v_{3}\}, whose second test v4⊥ ⁣ ⁣ ⁣⊥v2∣v1,v3v_{4}\perp\!\!\!\perp v_{2}\mid v_{1},v_{3} fails, since the collider v0v_{0} on v4↔v0↔v2v_{4}\leftrightarrow v_{0}\leftrightarrow v_{2} has the given descendant v1v_{1}; the run ends with the expression above. The insertion of v3v_{3} is forced: without it, the join of P(v1∣v0)P(v_{1}\mid v_{0}) in step 3 would have failed, since v1⊥̸ ⁣ ⁣ ⁣⊥v3∣v0v_{1}\not\perp\!\!\!\perp v_{3}\mid v_{0} because of v1→v3v_{1}\to v_{3}.

TK must assemble v5v_{5}, v4v_{4} and v3v_{3} to eliminate v3v_{3}, and its join of P(v5∣v1,v2,v3)P(v_{5}\mid v_{1},v_{2},v_{3}) with P(v4∣v0,v1,v3)P(v_{4}\mid v_{0},v_{1},v_{3}) rejects all four candidate sets {v0,v1}∪P\{v_{0},v_{1}\}\cup\mathbf{P}, P⊆{v2,v3}\mathbf{P}\subseteq\{v_{2},v_{3}\}; no variable is missing. To eliminate v1v_{1} or v0v_{0}, it must assemble the same two terms first, the same join fails, and the missing variable v2v_{2} cannot be inserted with any of its candidate sets. The expression is left unchanged, in each of the eight topological orders of the graph, whereas the elimination of v0v_{0} above succeeds in all of them.

Simplify tries the summation variables in a fixed order, from the highest down, and starts again from the top after each elimination. The result of a run can depend on this order, since an elimination can prevent a later one (Example A.1). A variant of the procedure could explore several orders, for instance by backtracking over the eliminations that succeed and keeping the expression with the fewest summations. Each attempt keeps the cost of Proposition 5.2, but the number of orders can grow as k!k! (in Example A.1 such an exploration recovers the expression that TK reaches). For simplicity, We have not included such a search in the algorithms above.

Soundness and completeness

This section collects what the previous ones establish about the procedure as a whole. It never writes a wrong expression, and for a single summation variable it does everything that joins and insertions can do: it eliminates the variable whenever some assembly eliminates it. We then state what remains open, the existence of steps of another kind and the order in which the summation variables are tried.

The procedure is sound: it rewrites the expression through identities only. Terms free of SS leave the summation by (R2); a join is the chain rule, valid exactly when the independences (5) hold (Theorem 3.1); an inserted term is positive and free of SS, so that multiplying by it and dividing by it after the summation changes nothing; the summation is a marginalisation by (R1) and (R4); and minimisation drops only idle conditions.

Corollary 6.1. If some assembly eliminates SS from an atomic expression of the ID algorithm, the procedure of this paper eliminates SS from that expression.

Proof. As noted after Proposition 2.5, the assembly may be taken in decreasing topological order. By Proposition 2.5, its reduction eliminates SS as well: the participating terms are assembled with inserted terms for a set R′⊆NR' \subseteq N, the variables of L′=N∖R′L' = N \setminus R' being conditions. By Lemma 4.1, which holds for any such choice, conditions (a) and (b) hold for R′R', with the sets Eh′=L′∪{x∈H∪R′:x<h}E'_h = L' \cup\{x \in H \cup R' : x < h\}. To pass from R′R' to the set RR of the procedure, observe for (a) that the set EhE_h consists of the variables of H∪NH \cup N below hh, all of which belong to Eh′E'_h, so that P(h∣Ch)=P(h∣Eh′)P(h \mid C_h) = P(h \mid E'_h) gives P(h∣Ch)=P(h∣Eh)P(h \mid C_h) = P(h \mid E_h) by decomposition. For (b), the chain rule and (a) give

∏M∈RP(M∣EM)=P(H∪R∣L)∏h∈HP(h∣Ch)=P(H∪N)P(L)∏h∈HP(h∣Ch).\prod_{M \in R} P(M \mid E_M) = \frac{P(H \cup R \mid L)}{\prod_{h \in H} P(h \mid C_h)} = \frac{P(H \cup N)}{P(L)\prod_{h \in H} P(h \mid C_h)}.

and the same identity holds for R′R' and L′L'. The two products of inserted terms thus differ by the factor P(L′)/P(L)P(L')/P(L), which does not contain SS, and the product for R′R' is free of SS by (b). Hence the product for RR is free of SS, and so is each of its factors, by the argument that ends the proof of Proposition 2.5 in Appendix A.1; this is (b). By Lemma 4.1 and Proposition 5.1 the procedure eliminates SS. □

The corollary applies to every expression that the procedure meets: the terms of the output of ID are minimal (§ 2), and along a run they remain so, because Factorize minimises the terms it returns (Example 3.3); minimisation does not prevent an elimination, since a joint assembled from terms with idle conditions is an assembly for the minimal terms, in which the terms that contain SS only as an idle condition count among the retained terms of Definition 2.4. The corollary carries two qualifications: it concerns a single elimination, and it is relative to joins and insertions. The first matters because a run is a sequence of eliminations, whose result can depend on their order, for both procedures alike (Example A.1); the end of § 5 describes how several orders could be explored, and the completeness of the single elimination is not affected.

As for joins and insertions, every part of an elimination that uses them is fixed: the terms to assemble (Proposition 2.5), the set of each join (Theorem 3.1), the variables to insert and the term inserted for each (§ 4); what remains open is whether steps of another kind exist to create an assembly. A summation disappears only through (R1), a joint distribution in which the summed variable is a head, and joins and insertions are the only steps we know that produce such a joint from the terms of an atomic expression by the rules (R1)–(R4) and the conditional independences implied by GG. We conjecture that no other step of this kind exists; if so, the procedure is complete among rewritings by conditional independences.4

Conclusion

The only rule by which a summation disappears is (R1): a conditional distribution sums to one over its head. Removing a summation therefore amounts to assembling terms into a joint distribution in which the summed variable is a head, and TK builds it by joins and by the insertion of missing variables, an effective device that supplies heads that no term provides. We have made two changes: only the terms that contain the summed variable are assembled, and every term is kept minimal, minimality being restored after every summation. Together they fix the rest: the join set, the inserted variables and the inserted terms are each decided without a search, and topological consistency is not needed. The resulting procedure is sound, removes summations that the original procedure leaves in place.

Within joins and insertions the procedure is complete for each elimination (Corollary 6.1), although the result of a whole run can depend on the order of the eliminations (Example A.1); and if, as we conjecture, no other step based on conditional independences can bring a summation to the form that (R1) requires, it is complete among such rewritings. Equality constraints that are not independences, such as the Verma constraint, lie outside this scope (§ 6). Some summations cannot be removed at all, such as the adjustment for BB in Example 2.6, which expresses an average over the summed variable; simplifications of other kinds, such as identities between the numerator and the denominator of a ratio, lie outside this scope.

Acknowledgements

We thank S. Tikka for early discussions about [8] and E. Armengol for suggesting that two minimal terms are joined at the unique minimal set CC of Theorem 3.1. The graphs and queries presented as examples were found with the help of the AI model Claude (Anthropic), after dozens of hours of discussion under the guidance of the authors. The authors are supported by UKRI Future Leaders Fellowship Grant No. 10128920.

Comparison with TK

This appendix contains the proof of Proposition 2.5, by which the terms and variables that TK assembles besides the participating ones never help an elimination (Appendix § 9.§ 1), and the argument, used after that proposition and in the proof of Corollary 6.1, that an assembly can always be rearranged into decreasing topological order (Appendix § 9.§ 2). With Corollary 6.1, these two results establish that the procedure of this paper eliminates a summation variable from an expression whenever TK does. Appendix § 9.§ 3 then turns to sequences of eliminations, through an example in which their order changes the result.

Full and reduced assemblies

Let P(A∣B)P(\mathbf{A}\mid\mathbf{B}) be a full assembly for SS and P(H∪R∣L)P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L}) its reduction (Definition 2.4). The two joints have different chain rules, and a prime marks the full one. By Definition 2.3, a head gg is conditioned in the full joint on

Eg′:=B∪{x∈A:x assembled after g},\mathbf{E}'_g := \mathbf{B}\cup\{x\in\mathbf{A}:x\text{ assembled after }g\},

and in the reduced joint on Eg:=L∪{x∈H∪R:x assembled after g}\mathbf{E}_g:=\mathbf{L}\cup\{x\in\mathbf{H}\cup\mathbf{R}:x\text{ assembled after }g\}, which in decreasing topological order is the set (8). The variables of H∪N\mathbf{H}\cup\mathbf{N} among the conditions of the full joint are those of L\mathbf{L}, and among its heads those of H∪R\mathbf{H}\cup\mathbf{R}, so that

Eg=Eg′∩(H∪N):\mathbf{E}_g=\mathbf{E}'_g\cap(\mathbf{H}\cup\mathbf{N}):

the reduction conditions each term on the same variables of H∪N\mathbf{H}\cup\mathbf{N} as the full assembly, and on none of U\mathbf{U}. In Example 2.6, for instance, TK tries to eliminate AA through the full joint P(Y,B,A∣X)P(Y,B,A\mid X), assembled in the order Y,B,AY,B,A, with H={A,B}\mathbf{H}=\{A,B\}, N=∅\mathbf{N}=\varnothing and U={X,Y}\mathbf{U}=\{X,Y\}; the participating term P(B∣A)P(B\mid A) must equal P(B∣EB′)=P(B∣A,X)P(B\mid\mathbf{E}'_B)=P(B\mid A,X), which fails because of X↔BX\leftrightarrow B, whereas in the reduction it must equal only P(B∣EB)=P(B∣A)P(B\mid\mathbf{E}_B)=P(B\mid A).

Proof of Proposition 2.5. The participating terms. For h∈Hh\in\mathbf{H}, P(h∣Ch)=P(h∣Eh′)P(h\mid C_h)=P(h\mid\mathbf{E}'_h), since the term is the factor of hh in the full joint, and Ch⊆Eh′∩(H∪N)=EhC_h\subseteq\mathbf{E}'_h\cap(\mathbf{H}\cup\mathbf{N})=\mathbf{E}_h. The term does not depend on the conditions in Eh′∖Ch\mathbf{E}'_h\setminus C_h, hence, by decomposition, not on those in the subset Eh∖Ch\mathbf{E}_h\setminus C_h, and P(h∣Ch)=P(h∣Eh)P(h\mid C_h)=P(h\mid\mathbf{E}_h). By the chain rule, the participating terms and the terms P(M∣EM)P(M\mid\mathbf{E}_M), M∈RM\in\mathbf{R}, multiply to P(H∪R∣L)P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L}).

The inserted terms. The full assembly uses for M∈RM\in\mathbf{R} the term P(M∣EM′)P(M\mid\mathbf{E}'_M), free of SS; the reduction inserts P(M∣EM)P(M\mid\mathbf{E}_M), which lacks the conditions in U\mathbf{U}, and dropping a condition may create a dependence on SS. As in Corollary 6.1, we compare products rather than single terms. Let QQ be the product of the terms of the full assembly other than the participating ones, which is free of SS, so that P(A∣B)=∏h∈HP(h∣Ch) QP(\mathbf{A}\mid\mathbf{B})=\prod_{h\in\mathbf{H}}P(h\mid C_h)\,Q. Multiplying by P(B)P(\mathbf{B}) and summing over the variables of U\mathbf{U}, which occur in no participating term and do not include SS, gives P(H∪N)=∏h∈HP(h∣Ch)∑UP(B)QP(\mathbf{H}\cup\mathbf{N})=\prod_{h\in\mathbf{H}}P(h\mid C_h)\sum_{\mathbf{U}}P(\mathbf{B})Q. Since P(H∪R∣L)=P(H∪N)/P(L)P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L})=P(\mathbf{H}\cup\mathbf{N})/P(\mathbf{L}), the first part gives

∏M∈RP(M∣EM)=P(H∪R∣L)∏h∈HP(h∣Ch)=1P(L)∑UP(B)Q,\prod_{M\in\mathbf{R}}P(M\mid\mathbf{E}_M)=\frac{P(\mathbf{H}\cup\mathbf{R}\mid\mathbf{L})}{\prod_{h\in\mathbf{H}}P(h\mid C_h)}=\frac{1}{P(\mathbf{L})}\sum_{\mathbf{U}}P(\mathbf{B})Q,

which is free of SS, as none of P(L)P(\mathbf{L}), P(B)P(\mathbf{B}) and QQ contains it. Each factor is then free of SS: the variable of R\mathbf{R} assembled first occurs only in its own factor, so summing over it shows that the other factors multiply to a function free of SS, and the argument proceeds down the order. The reduction is therefore an assembly for SS, whose participating terms are the factors of their heads and whose inserted terms are free of SS. □

The order of assembly

Definition 2.3 takes the heads in decreasing topological order. A joint assembled in another order, such as the one that TK builds in Example A.1, can be rearranged into this order without changing its terms. Let uu be assembled immediately before ww, with u<wu < w, and let ZZ consist of the conditions of the joint and of the heads assembled after ww. The chain rule gives uu the term P(u∣Z,w)P(u \mid Z,w) and ww the term P(w∣Z)P(w \mid Z). The term of uu depends only on variables below uu, hence not on ww, so that u⊥ ⁣ ⁣⊥w∣Zu \perp\!\!\perp w \mid Z; then P(w∣Z,u)=P(w∣Z)P(w \mid Z,u)=P(w \mid Z) and P(u∣Z)=P(u∣Z,w)P(u \mid Z)=P(u \mid Z,w). Assembling ww before uu therefore leaves both terms unchanged, and exchanging in this way every adjacent pair in the wrong order brings the joint into decreasing topological order, with the same inserted terms. The argument fails for an inserted term that depends on a variable above its head, which could not be moved; TK, however, could not divide out such a term either, since its factorisation writes the result by the chain rule in topological order.

Sequences of eliminations

The results above compare the two procedures on one elimination, from one expression, whereas a run is a sequence of eliminations, each applied to the expression that the previous one has written. Sequences deserve a study of their own, which we do not attempt here: an elimination can prevent a later one, for both procedures alike, so that the result of a run depends on the order in which the summation variables are tried, and the order followed by the procedure of this paper, from the highest summation variable down, is not always the best one. In the following example the procedure of this paper, tried in its default order, ends with two summations where TK ends with one, because it eliminates a variable that TK cannot eliminate, whereas in the order that TK ends up following it reaches the same expression as TK.

Example A.1 (the order of the eliminations matters). Consider the graph below, with the topological order v0<v1<⋯<v6v_0 < v_1 < \cdots< v_6, and the query P(v3,v6∣v^5)P(v_3,v_6 \mid\hat{v}_5).

Figure A.1.

ID returns

∑v0,v1,v2,v4P(v0)P(v1∣v0)P(v2∣v0)P(v3∣v0,v1,v2)P(v4∣v1,v3)P(v6∣v0,v1,v3,v4,v5).\sum_{v_0,v_1,v_2,v_4} P(v_0)P(v_1 \mid v_0)P(v_2 \mid v_0)P(v_3 \mid v_0,v_1,v_2)P(v_4 \mid v_1,v_3)P(v_6 \mid v_0,v_1,v_3,v_4,v_5).

The procedure of this paper, Simplify (Algorithm 1), tries v4v_4 first. Its participating terms are P(v4∣v1,v3)P(v_4 \mid v_1,v_3) and P(v6∣v0,v1,v3,v4,v5)P(v_6 \mid v_0,v_1,v_3,v_4,v_5), so that H={v4,v6}\mathbf{H}=\{v_4,v_6\}, N={v0,v1,v3,v5}\mathbf{N}=\{v_0,v_1,v_3,v_5\}, R={v5}\mathbf{R}=\{v_5\} and L={v0,v1,v3}\mathbf{L}=\{v_0,v_1,v_3\}, and the loop runs through v6,v5,v4v_6,v_5,v_4. The term for v6v_6 is the initial joint; Insert computes Ev5={v0,v1,v3,v4}E_{v_5}=\{v_0,v_1,v_3,v_4\}, finds that conditional on v3v_3, v5⊥ ⁣ ⁣⊥v4∣v0,v1,v3v_5 \perp\!\!\perp v_4 \mid v_0,v_1,v_3, and joins the inserted term P(v5∣v0,v1,v3)P(v_5 \mid v_0,v_1,v_3). Join then joins v4v_4 at {v0,v1,v3}\{v_0,v_1,v_3\}, since v4⊥ ⁣ ⁣⊥v0∣v1,v3v_4 \perp\!\!\perp v_0 \mid v_1,v_3, and Factorize sums out v4v_4 and divides by the inserted term:

∑v0,v1,v2P(v0)P(v1∣v0)P(v2∣v0)P(v3∣v0,v1,v2)P(v6∣v0,v1,v3,v5).(11)\sum_{v_0,v_1,v_2} P(v_0)P(v_1 \mid v_0)P(v_2 \mid v_0)P(v_3 \mid v_0,v_1,v_2)P(v_6 \mid v_0,v_1,v_3,v_5). \tag*{(11)}

The procedure starts again from the highest summation variable, v2v_2. Its participating terms are P(v2∣v0)P(v_2 \mid v_0) and P(v3∣v0,v1,v2)P(v_3 \mid v_0,v_1,v_2); the term for v6v_6 does not contain v2v_2 and is not assembled. Here R=∅\mathbf{R}=\varnothing, and v2v_2 is joined to v3v_3 at {v0,v1}\{v_0,v_1\}, since v2⊥ ⁣ ⁣⊥v1∣v0v_2 \perp\!\!\perp v_1 \mid v_0, which gives

∑v0,v1P(v0)P(v1∣v0)P(v3∣v0,v1)P(v6∣v0,v1,v3,v5).(12)\sum_{v_0,v_1} P(v_0)P(v_1 \mid v_0)P(v_3 \mid v_0,v_1)P(v_6 \mid v_0,v_1,v_3,v_5). \tag*{(12)}

From here neither v1v_1 nor v0v_0 can be eliminated, because each needs the insertion of v5v_5. For v1v_1, H={v1,v3,v6}\mathbf{H}=\{v_1,v_3,v_6\}, R={v5}\mathbf{R}=\{v_5\} and L={v0}\mathbf{L}=\{v_0\}, and this insertion, with Ev5={v0,v1,v3}E_{v_5}=\{v_0,v_1,v_3\}, requires v5⊥ ⁣ ⁣⊥v1∣v0,v3v_5 \perp\!\!\perp v_1 \mid v_0,v_3, which fails on the path v5←v2↔v3↔v1v_5 \leftarrow v_2 \leftrightarrow v_3 \leftrightarrow v_1, where v3v_3 is a conditioned collider and v2v_2 is not given. For $v_0

the insertion of v5v_{5} requires v5⊥ ⁣ ⁣⊥v0∣v1,v3v_{5} \perp\!\!\perp v_{0} \mid v_{1}, v_{3}, which fails on v5←v2←v0v_{5} \leftarrow v_{2} \leftarrow v_{0}, and the procedure stops at (12), with two summations.

Suppose instead that, after v4v_{4}, the procedure tries v1v_{1} on (11). Since v2v_{2} still occurs, now N={v0,v2,v5}\mathbf{N} = \{v_{0}, v_{2}, v_{5}\}, R={v2,v5}\mathbf{R} = \{v_{2}, v_{5}\} and L={v0}\mathbf{L} = \{v_{0}\}, and the loop runs through v6,v5,v3,v2,v1v_{6}, v_{5}, v_{3}, v_{2}, v_{1}. The insertion of v5v_{5}, with Ev5={v0,v1,v2,v3}\mathbf{E}_{v_{5}} = \{v_{0}, v_{1}, v_{2}, v_{3}\}, requires v5⊥ ⁣ ⁣⊥v1∣v0,v2,v3v_{5} \perp\!\!\perp v_{1} \mid v_{0}, v_{2}, v_{3}, which holds because v2v_{2} blocks the path above, and the inserted term is P(v5∣v0,v2,v3)P(v_{5} \mid v_{0}, v_{2}, v_{3}), which equals P(v5∣v2)P(v_{5} \mid v_{2}). Then v3v_{3} is joined, v2v_{2} is inserted with P(v2∣v0)P(v_{2} \mid v_{0}), since v2⊥ ⁣ ⁣⊥v1∣v0v_{2} \perp\!\!\perp v_{1} \mid v_{0}, and v1v_{1} is joined at {v0}\{v_{0}\}, which gives

∑v0,v2P(v0) P(v2∣v0) P(v3∣v0,v2) P(v6∣v0,v2,v3,v5).(13)\sum_{v_{0},v_{2}} P(v_{0})\,P(v_{2} \mid v_{0})\,P(v_{3} \mid v_{0},v_{2})\,P(v_{6} \mid v_{0},v_{2},v_{3},v_{5}). \tag*{(13)}

In the same way v0v_{0} is eliminated, inserting v5v_{5} with P(v5∣v2,v3)=P(v5∣v2)P(v_{5} \mid v_{2}, v_{3}) = P(v_{5} \mid v_{2}), since v5⊥ ⁣ ⁣⊥v0∣v2,v3v_{5} \perp\!\!\perp v_{0} \mid v_{2}, v_{3}, and the result is

∑v2P(v2) P(v3∣v2) P(v6∣v2,v3,v5),(14)\sum_{v_{2}} P(v_{2})\,P(v_{3} \mid v_{2})\,P(v_{6} \mid v_{2},v_{3},v_{5}), \tag*{(14)}

with one summation instead of two; v2v_{2} can no longer be eliminated, since v5⊥ ⁣ ⁣⊥v2∣v3v_{5} \perp\!\!\perp v_{2} \mid v_{3} fails. Both (12) and (14) are correct, and neither can be simplified further by joins and insertions. A summation variable above SS can thus be needed, in the conditioning set of an inserted term, for the elimination of SS.

TK, recalled in § 2, assembles for each summation variable SS the full joint of the terms whose heads lie between SS and the highest head (Definition 2.4), from the top down, inserts a missing variable when a join fails, and does not minimise.

For v4v_{4} it joins v4v_{4} to v6v_{6} at {v0,v1,v2,v3,v5}\{v_{0}, v_{1}, v_{2}, v_{3}, v_{5}\}: v2v_{2} enters as an ancestor of v4v_{4}, and remains, idle, in the new term P(v6∣v0,v1,v2,v3,v5)P(v_{6} \mid v_{0}, v_{1}, v_{2}, v_{3}, v_{5}).

For v2v_{2} it fails, because the full assembly contains, besides the terms for v3v_{3} and v2v_{2}, the term for v6v_{6}, which the reduced assembly leaves out and which depends on v5v_{5}; the join of v3v_{3} then keeps v5v_{5} among the conditions of the joint. A candidate set for the join of v2v_{2} either drops v5v_{5}, on which the joint depends, or keeps it, and then requires v2v_{2} to be independent of v5v_{5} given v0v_{0}; the insertion of v5v_{5} requires v5v_{5} to be independent of v2v_{2} given v0v_{0} and possibly v1v_{1}; both are excluded by the edge v2→v5v_{2} \to v_{5}. The idle condition plays no part: the failure occurs as well when the term for v6v_{6} is minimal.

For v1v_{1} it succeeds, in a way that the procedure of this paper never follows. After the join of v3v_{3} at {v0,v1,v2,v5}\{v_{0}, v_{1}, v_{2}, v_{5}\}, the joint P(v6,v3∣v0,v1,v2,v5)P(v_{6}, v_{3} \mid v_{0}, v_{1}, v_{2}, v_{5}) conditions v3v_{3} on v5v_{5}, which lies above it. The join of v2v_{2} fails, and v5v_{5}, a condition of the joint, is inserted at {v0,v1,v2}\{v_{0}, v_{1}, v_{2}\}, after v3v_{3}, that is, out of topological order; then v2v_{2} is joined at {v0,v1}\{v_{0}, v_{1}\} and v1v_{1} at {v0}\{v_{0}\}, and the result is (13). The procedure of this paper inserts v5v_{5} before v3v_{3}, since its loop runs from the top, and never conditions a head on a variable above it. The two orders are equivalent here, because the join of v3v_{3} has checked that v3⊥ ⁣ ⁣⊥v5∣v0,v1,v2v_{3} \perp\!\!\perp v_{5} \mid v_{0}, v_{1}, v_{2}, so that the condition v5v_{5} is idle, and by Appendix A.2 the two orders of assembly give the same terms. After another failed attempt on v2v_{2}, TK eliminates v0v_{0} in the same way and ends at (14).

The greater power of the reduced assembly is thus an obstacle in this example: by removing v2v_{2}, which TK cannot remove, the procedure of this paper loses the variable that the later insertions of v5v_{5} need, while TK, held up at v2v_{2}, keeps it. As shown above, the procedure of this paper reaches (14) when it follows the same sequence, and a search over orders, as described at the end of § 5, finds it.

References

  1. [1]J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–710, 1995.
  2. [2]J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd edition, 2009.
  3. [3]I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semi-Markovian causal models. In Proceedings of the 21st National Conference on Artificial Intelligence, pages 1219–1226, 2006.
  4. [4]Y. Huang and M. Valtorta. Pearl’s calculus of intervention is complete. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, pages 217–224, 2006.
  5. [5]J. Tian and J. Pearl. A general identification condition for causal effects. In Proceedings of the 18th National Conference on Artificial Intelligence, pages 567–573, 2002.DOI
  6. [6]J. Tian and J. Pearl. On the identification of causal effects. Technical Report R-290-L, Cognitive Systems Laboratory, University of California, Los Angeles, 2003.
  7. [7]I. Lodato and A. V. Iyer and I. Z. To. Bounding interventional queries from generalized incomplete contingency tables. https://arxiv.org/abs/2511.05755, 2025.
  8. [8]S. Tikka and J. Karvanen. Simplifying probabilistic expressions in causal inference. Journal of Machine Learning Research, 18(36):1–30, 2017.arxiv.org/abs/1806.07082
  9. [9]D. Geiger, T. Verma and J. Pearl. Identifying independence in Bayesian networks. Networks, 20(5):507–534, 1990.
  10. [10]T. Verma and J. Pearl. Equivalence and synthesis of causal models. In Proceedings of the 6th Conference on Uncertainty in Artificial Intelligence, pages 255–270, 1990.
  11. [11]T. S. Richardson, R. J. Evans, J. M. Robins and I. Shpitser. Nested Markov properties for acyclic directed mixed graphs. The Annals of Statistics, 51(1):334–361, 2023.DOI

Paper details

vlnc:W_wfc3jft5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…
Contents