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 , whose directed edges represent direct causal influence and whose bidirected edges represent latent common causes, an interventional distribution is identifiable if it can be computed from the observational distribution and 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 , the maximal sets of vertices connected by bidirected paths, over which the observational distribution factorises [5, 6], and returns a formula for in the identifiable cases.
The formula is always correct but rarely in its simplest form. It is built from conditional distributions , which we call terms, with head and conditioning set , 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
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 on the simple collider graph with topological order . ID returns
Since and are independent, , and the chain rule combines the two terms into a joint distribution in which is a head and nowhere a condition:
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
applications of the chain rule whose conditioning set is searched for among the ancestors of and the subsets of a set of preceding vertices. When a join fails because the joint carries a condition that the next term cannot carry (the second independence condition of INSERT in TK fails), the procedure inserts : a term free of the summed variable, with 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 occurs, the participating terms, as one would do on paper, where to carry out a sum over one looks at the factors that contain , 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, is positive and faithful to , so that conditional independences and d-separations coincide, and a topological order of the vertices of is fixed; we write when precedes in . A term is a factor whose head set is disjoint from its conditioning set ; a term with a single head is written . Besides the d-separation criterion we use three properties of conditional independence, valid for every distribution: symmetry, by which and are equivalent; decomposition, by which implies ; and weak union, by which implies .
Definition 2.1. A condition is idle in when , that is, when . The conditioning set 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 be a vertex and the c-component of in the subgraph induced by and its -predecessors, and let consist of the other members of and the parents of all members of . By the c-component factorisation [6], the conditionals formed at lines 6 and 7 of ID [3] equal . No condition is idle, because either belongs to or is a parent of some , and therefore reaches through a bidirected path inside , preceded in the second case by the edge . Every intermediate vertex of this path lies in , hence is conditioned, and is a collider, so that the path is open given and, under faithfulness, . Since lies among the predecessors of , 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: whenever .
(R2) A factor in which the summed variable does not occur can be taken out of the sum: when does not occur in .
(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 and , its sum over is , which the chain rule writes again as a product of terms; for instance .
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 means to assemble terms into a joint distribution with and , to sum over , 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 be atomic, the set of its variables, and . Terms in which no summation variable occurs are first extracted [8 Algorithm 5]. To eliminate , Simplify assembles, in decreasing order of their heads, every remaining term whose head lies between and the -last head; the variables of in that range that head no term are the missing variables. Join combines the current joint with the next term by trying, for each subset of , the conditioning set ; a candidate is accepted when and , with and . When no candidate is accepted, Insert tries a missing variable with the conditioning sets , accepting the first for which the joint absorbs the new term and 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 be an atomic expression: is its set of summation variables, and is its set of terms, each a conditional distribution , given by its head and its conditioning set . Let be the variable to be eliminated. Like every summation variable in an output of ID, 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 are those in which occurs, as head or as condition; the others form . We write for the heads of , for the conditioning set of the term headed by , and
for the variables on which participating terms are conditioned without heading one of them.
By (R2), , so only has to be assembled into a joint distribution. TK assembles more: every term whose head lies between 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 is a joint distribution , with and , whose heads are taken in decreasing topological order , and which is written by the chain rule as
where the factor of each participating head is its term, , and the factor of every other head is a further term that does not depend on , either a term of or a term to be inserted.
The summation over 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, .
Definition 2.4. For , let . A reduced assembly is an assembly : its heads are the participating heads and the variables of , its conditions are the other variables of , and its further terms are only inserted terms for the variables of . A full assembly may contain, besides the participating terms, terms of , called retained terms, and inserted terms for missing variables, so that and may contain variables outside . The reduction of a full assembly is the reduced assembly with , so that : it keeps the participating heads and the variables of in the same order, conditions them on , and drops the variables of , namely the heads of retained terms, the missing variables outside , and the conditions of the joint outside .
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 exists, its reduction is an assembly for , 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 . Only variables of therefore need to be inserted. Such a variable may already exist in the expression and head a term of ; 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 makes the join with the participating term 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 , and the query .
Figure 2.
ID returns
The summation variables are tried in decreasing order, beginning with , whose participating terms are and . Their join requires , which fails because of ; no variable is inserted, since the only condition of the joint that does not carry is . The participating terms of are and only, while remains outside the summation. By the chain rule , and summing over gives , so that
the back-door formula. A second attempt on requires , which fails again; the remaining summation is the adjustment for , and no rewriting removes it.
To eliminate , TK must assemble the heads , and , beginning with the join of and . Here and , so the candidate sets are , which fails because of , and , which passes but fails because of . No variable is missing between and , so the elimination fails; the elimination of 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 follows , is missing and its insertion fails too. The failure is caused by the term , which is retained although it does not contain , and whose join with is impossible at any set.
Participation is read off the conditioning sets as written. A term that carries an idle condition on therefore takes part in the elimination of , although it does not depend on , 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 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 is joined to the joint assembled so far. A join must choose the conditioning set of the new joint: TK searches for it among the sets , 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 , the set is disjoint from . We write
Theorem 3.1 (The unique join set). Let and be minimal.
(i) The two terms are joined at some set , that is, , if and only if they are joined at ,
and this holds if and only if
In that case , and every condition in is idle in .
(ii) If (4) holds, is a minimal conditioning set for .
The two independences in (5) state that and : each term can be written with the conditioning set that the chain rule assigns to it in the joint .
Proof. (i) The statement contains three assertions: the terms are joined at some set, they are joined at , 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 , which is (4). If (4) holds, the terms are joined at a set, namely . Finally, suppose that for some . Summing both sides over , which does not occur in , removes the first factor by (R1) and marginalises the right-hand side, leaving
dividing the join identity by (6), which positivity permits, leaves
If some were not in , the right-hand side of (6) would not depend on , so that would be idle in , against minimality; hence . The same argument applied to (7) gives , and together these yield . Equation (6) states ; since is the union of
and , decomposition gives , which is the second independence of (5) because . Equation (7) states ; since is contained in , decomposition gives the first independence of (5), which closes the cycle. Moreover (4) then holds, and since both and equal the product of the two terms, the conditions in are idle.
(ii) If a condition were idle in , the two terms would be joined at , and (i) would give , which is impossible.
By (ii), a join of minimal terms at 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 with at some set , where may contain, besides a minimal set , conditions that earlier joins have written although they are idle. The two products have the same value, so the minimal pair is joined at as well, and (i) gives and the join at . The test at therefore succeeds whenever the search does, and it is a single test, whereas the search examines up to 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 , and the query .
Figure 1.
ID returns
The participating terms of are and . By Theorem 3.1 their join is fixed at ; the first independence of (5) is vacuous, and the second, , holds, since is the only edge at . The joint is , and summing over gives , which is minimal. The participating terms of are then and ; their join is fixed at , and its second independence, , fails because of . By the theorem no set joins the two terms, and the procedure stops at
after two tests.
The procedure of TK reaches the same expression after 22 candidate sets, 14 for and 8 for . For it joins the same two terms; and , so the candidates are the 16 subsets of , which we enumerate from the smallest. Every set that omits , or fails, because depends on the omitted variable, and , the fourteenth, is accepted; it is . For the candidates are the 8 subsets of . Those that omit or fail on the dependence of , and and fail because ; all eight must be tried before the join is abandoned, and no variable is missing between and . 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 intervened variables , placed after in the order, each with the single edge , and consider . ID returns the same expression with among the conditions of the term for , and the procedure of this paper still performs two tests, at and at . For TK the join of now has candidate sets and is accepted at , only after every smaller set ( sets) has failed; the join of is abandoned only after all the subsets of have failed.
Example 3.3 (the fixed join needs minimal terms). Consider the graph below, with the topological order , and the query .
Figure 3 (PDF p. 7).
ID returns
where the summations of the fractions bind their own variables. The outcomes and form the only c-component of the graph without the intervened variables, and their c-component in is , so that ID reaches line 7 at once, with the product of the five terms of this c-component, written with the minimal conditioning sets of Section 2. In the subgraph on the c-component, and are not ancestors of or and are summed at line 2, and line 6 writes the distribution of , and that of given and , as the two ratios. The first denominator sums every term to one, so that the first fraction, the distribution of , is its numerator,
an atomic expression with minimal terms, whose summation variables are tried in decreasing order.
The term for is the only one that contains , and it sums to one; the same then holds for . This leaves . The participating terms of are and . By Theorem 3.1 their join is fixed at ; the first independence of (5) is vacuous, since , and the second, , holds: the path is blocked at , and every other path at a collider, or , that is not given. The joint is , and summing over gives .
This term is not minimal: , because is blocked at , and every path through at a collider, or , that is not conditioned on. The condition cannot be dropped, because of , so the minimal term is . With it, the participating terms of are and , their join at involves only vacuous tests, and summing over gives : the four summations are removed, and the first fraction is .
Suppose instead that the term is kept as the chain rule writes it, , with the idle condition inherited from . The participating terms of are and , and the set of Theorem 3.1 is . The first independence of (5) is vacuous, and the second, , fails because of ; the insertion of , which lies above , requires the same independence (Section 4). The two terms can nevertheless be joined, since . They are joined at , a set that does not contain , which Theorem 3.1 excludes for minimal terms only. For a term that is not minimal the test at is therefore not conclusive, and here it would leave the summation in , a correct expression, equal to . 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 and as above, and for it joins with ; here and , so the only candidate set is , which is accepted, and the summation leaves , which TK does not minimise. For it joins with ; now and , so the candidate sets are and . At the first test of TK is , the statement that is idle, and the second is vacuous; the candidate is accepted, the joint is , and the result is . 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 , without it the procedure stops at , and TK returns , in which is idle.
Insertion
By Theorem 3.1, the join of the joint with the next term fails when one of the two independences (5) fails. When the second one fails, depends, given , on a condition of the joint, . If lies above , this dependence can be removed by turning into a head of the joint: a term for is multiplied into the joint, and divided out after the summation, which requires it not to depend on . This is the insertion of [8], and by Proposition 2.5 the only variables that need to be inserted are those of , the conditions of participating terms that head none of them.
A participating term contains , as its head or as a condition below its head, so every participating head lies at or above . The procedure inserts the variables of above and keeps the others as conditions:
The final joint is then , a reduced assembly in the sense of Definition 2.4. Let be its heads in topological order; the joint is assembled from down to , and the chain rule conditions each head on and on the heads below it:
Since lies below and every head lies at or above , this set consists of all the variables of below :
Lemma 4.1 (Elimination through insertions). There exist terms , with , each a conditional distribution of given variables of and free of , such that
if and only if
(a) for every , and
(b) for every .
In that case for every , and
where no term on the right-hand side contains .
Proof. If the terms exist, every factor of the product is conditioned only on variables below its head, so the highest head occurs only in its own factor. Summing both sides over removes that factor by (R1) and shows that the product of the other factors is ; dividing (9) by this product (which positivity permits), the factor of is . Descending induction shows that every factor is the one that the chain rule assigns to its head: for this is (a), and for it gives , which is free of , that is, (b).
Conversely, under (a) and (b) the terms are free of , and by the chain rule and (a) they complete the participating terms to . Dividing by the terms and summing over , which occurs neither in them nor in , gives by (R2) and (R4)
The chain rule for the numerator assigns to each the set , and the factors with cancel against the denominator, which gives (10). ▫
Condition (a), on the participating terms, states that , since ; in other words, a term must be independent on every variable of the joint below its head that its minimal conditioning set does not carry. Condition (b), on the inserted terms, requires the term inserted for , which by the lemma is necessarily , not to depend on , 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 , ; by the lemma, whatever set the search accepts, the inserted term is . The set is determined by all the participating terms, including those joined after (Example 4.2). The lemma and its proof hold unchanged for any , with and the sets (8).
The terms written by (10) are conditioned on , below their heads, so the procedure maintains the property assumed in § 2. They need not be minimal: contains every variable of the joint below , and the summation over 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 and ab initio. Example 4.3 shows again the importance of participation when insertions are used: a term of 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 , and the query .
Figure 1 (PDF p. 9).
ID returns
All three terms contain , so that and ; hence and , and the variables are assembled in the order .
The term forms the initial joint, with and .
To insert the variable , (8) gives , and condition (b) requires , which
Example 4.3 (a retained term between the participating terms). Consider the graph below, with the topological order , and the query .
Figure 4.
ID returns
The summation variables are tried in decreasing order. The participating terms of are and ; their join is fixed at , and its second independence, , fails because of . No variable of lies above , so nothing is inserted, and cannot be eliminated: lies below , and no insertion removes it from .
The participating terms of are , and , while , the term that could not be joined, remains outside the summation; here and , so that and , and the order of assembly is .
The term forms the initial joint, with and .
To insert the variable , (8) gives , and condition (b) requires , which holds: the path is blocked at , and the paths through are blocked at the collider , which is not given. The inserted term is , which by (b) equals ; it is joined at , both independences holding, and the joint becomes .
The join with is fixed at ; its second independence, , holds, and the joint becomes .
The join with at requires , which holds, and the joint becomes .
Summing over and factorising in the order of assembly gives , where has been minimised to ; the factor of is the inserted term and is divided out. With restored by (R2),
Here the insertion of is forced: without it, the join of with would fail, since because of . A further attempt on fails as before, since the join of with at requires . The term cannot be joined because of ; left outside the summation, it leaves its head free to be inserted with the conditioning set that the chain rule requires, and the inserted term differs from it by the condition .
For TK the term takes part in the elimination of and, as a retained term, in that of . To eliminate , it joins with , and both candidate sets, and , fail; no variable is missing. To eliminate , it must assemble and , and, beginning with the same join, which fails again, and no variable between and is missing, since and head terms and lies below , so that the expression is left unchanged. In the topological order , however, lies between and and heads no term; the procedure then inserts it and eliminates 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 is written , and a joint is written , with conditioning set and heads kept as a sequence in the order of assembly; denotes the sequence followed by , and in set operations and independence statements stands for the set of its elements. FAIL marks an unsuccessful call, and a d-separation test in 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 given graph and topological ordering .
1: function SIMPLIFY 2: 3: while do 4: ▷ : the -th of , in decreasing order of 5: ; ▷ participating terms 6: ; 7: ; ▷ inserted variables 8: 9: while do ▷ : the -th term of , by decreasing head 10: 11: if then break 12: ; ; 13: if then ▷ 14: ▷ sum out , divide by 15: ; ▷ restart on the new terms 16: return
For each summation variable , lines 5–7 determine the participating terms, their heads , the set of Definition 2.2, and the inserted variables of Section 4; the terms of 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 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 , and FACTORIZE sums out and divides by the inserted terms (line 14); is removed, and the summation variables are tried again from the first, since one elimination may enable another.
Algorithm 2 Join of with at the set of Theorem 3.1, after the insertion of the variables of above .
1: function JOIN 2: if then return ▷ the initial joint 3: 4: for with , in decreasing order do ▷ conditions above : inserted first 5: 6: if then return FAIL 7: ; 8: ▷ the set of Theorem 3.1 9: if and then 10: return ▷ 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 , from the highest down (lines 4–7). These are the variables of above , and each must become a head before 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 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 of the joint that lies above , whether or not the insertion is necessary. It is necessary when a term with head below depends on without having it among its conditions , so that the second independence of (5) fails), and otherwise each remaining join would succeed with kept as a condition , as 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 into the joint .
function
▷ the set (8), without
if not then return fail ▷ condition (b)
if not then return fail ▷ condition (a) for the heads of
return
Insert computes the conditioning set (8) without , fixed by Lemma 4.1 (line 2), and performs two tests. The first is condition (b): the inserted term does not depend on (line 3). The second asks that the joint assembled so far keep its value when it is conditioned on as well (line 4): the terms already absorbed may not depend on the variables below that enter the joint with the inserted term, which is condition (a) for their heads. When is inserted, and are conditions of the joint and every other condition lies in , so that the new conditioning set is (line 5). The two tests are those of Theorem 3.1 for the join of with at this set, and those of the insertion of at the single candidate . 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 of the joint , inserted terms divided out.
function
▷ in the order of assembly,
for do
if or a term with head is in then
continue ▷ summed out, or divided out
▷ its factor, minimal
return
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 given and . Summing over leaves a joint distribution of the other heads, whose chain rule assigns to the set . For an inserted head this factor equals the inserted term, which does not depend on ; 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 .
function
repeat
removed false
for do
if then ▷ is idle:
; removed true; break
until removed = false
return ▷ 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 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 , 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 , line 14 replaces the terms by an expression equal to , in which does not occur and every term is minimal. Conversely, if conditions (a) and (b) of Lemma 4.1 hold for the set 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 , and let Join absorb the next term at , so that with . For a head of and the set of heads absorbed after it, decomposition gives , and symmetry and weak union give , so that the factor of given is also its factor given , which is the set that the chain rule assigns to it after the join; the new term is the factor of given by the second independence. An insertion is the same step for the term . When Insert is called for , the heads of the joint are the variables of above ; and are conditions of participating terms already absorbed, and every other condition of the joint lies below , hence in . The term is thus absorbed at ; line 4 of Insert is the first independence, with , and line 3 is the second, since . When the loop completes, the participating terms times the inserted terms therefore equal ; the inserted terms are free of , so they leave the summation by (R2), and the summation removes 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 are restored by (R2).
Conversely, under (a) and (b) the factors of Lemma 4.1, taken from the highest variable of down to any variable , multiply to the joint distribution of these variables given , so that the joint assembled when has been absorbed satisfies , with . The next variable to be absorbed, , is the next one below in , so that . The first test of Join, and line 4 of Insert, ask that be independent, given , of variables of , which follows by decomposition. The second test of Join asks that be independent, given , of variables of , 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 candidate sets (Example 3.2). We count d-separation tests, each of which takes time linear in the size of [9].
Proposition 5.2 (Cost). Let have variables, and let one attempt, for one summation variable, assemble heads. The attempt performs at most tests in Join and Insert and at most calls of Minimize, each of which performs at most tests for a set of conditions. A run with summation variables makes at most attempts, and therefore 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 , so that there are at most 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 ; since is itself one of the heads, there are at most calls. Each pass of the loop of Minimize performs at most tests and either removes a condition or ends the call, so there are at most passes. Between two successful eliminations, Simplify tries each remaining summation variable at most once, so a run makes at most attempts; since , each attempt makes 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 , and the query .
Figure 5.3.
ID returns
and Simplify tries the summation variables in the order .
. Line 5 selects the terms that contain , namely , and . Lines 6–7 give and , which lies below , so that and . The loop begins with , whose term is the initial joint , and calls Join for at . The first test, , holds; the second, , fails, because the path is open when its collider is given, and the loop breaks at line 11.
. Now participates as well, , , and . The loop again begins with and , and the same join fails: , which lies below , is inserted only later, and is still a condition of the joint when is joined.
. Line 5 selects , and , and puts and in . Then , , and , and the loop calls Join for the terms of , and .
The term for is the initial joint .
Called for , Join first inserts , the variable of above . Insert computes (line 2) and tests (line 3), which holds: is blocked at , and at the collider , which is not given. The test of line 4 is vacuous, since . The joint is , and the inserted term is .
Join then adds at and, called for the last term, at , with vacuous tests only; the joint is .
Factorize (line 14) writes with , skips , which is in , writes with the empty set, and skips . With the terms of restored,
After line 15 has removed , the new attempts on and again begin with the join of and , now at , whose second test fails, since the collider on has the given descendant ; the run ends with the expression above. The insertion of is forced: without it, the join of in step 3 would have failed, since because of .
TK must assemble , and to eliminate , and its join of with rejects all four candidate sets , ; no variable is missing. To eliminate or , it must assemble the same two terms first, the same join fails, and the missing variable 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 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 (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 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 , 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 from an atomic expression of the ID algorithm, the procedure of this paper eliminates 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 as well: the participating terms are assembled with inserted terms for a set , the variables of being conditions. By Lemma 4.1, which holds for any such choice, conditions (a) and (b) hold for , with the sets . To pass from to the set of the procedure, observe for (a) that the set consists of the variables of below , all of which belong to , so that gives by decomposition. For (b), the chain rule and (a) give
and the same identity holds for and . The two products of inserted terms thus differ by the factor , which does not contain , and the product for is free of by (b). Hence the product for is free of , 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 . □
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 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 . 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 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 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 be a full assembly for and 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 is conditioned in the full joint on
and in the reduced joint on , which in decreasing topological order is the set (8). The variables of among the conditions of the full joint are those of , and among its heads those of , so that
the reduction conditions each term on the same variables of as the full assembly, and on none of . In Example 2.6, for instance, TK tries to eliminate through the full joint , assembled in the order , with , and ; the participating term must equal , which fails because of , whereas in the reduction it must equal only .
Proof of Proposition 2.5. The participating terms. For , , since the term is the factor of in the full joint, and . The term does not depend on the conditions in , hence, by decomposition, not on those in the subset , and . By the chain rule, the participating terms and the terms , , multiply to .
The inserted terms. The full assembly uses for the term , free of ; the reduction inserts , which lacks the conditions in , and dropping a condition may create a dependence on . As in Corollary 6.1, we compare products rather than single terms. Let be the product of the terms of the full assembly other than the participating ones, which is free of , so that . Multiplying by and summing over the variables of , which occur in no participating term and do not include , gives . Since , the first part gives
which is free of , as none of , and contains it. Each factor is then free of : the variable of assembled first occurs only in its own factor, so summing over it shows that the other factors multiply to a function free of , and the argument proceeds down the order. The reduction is therefore an assembly for , whose participating terms are the factors of their heads and whose inserted terms are free of . □
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 be assembled immediately before , with , and let consist of the conditions of the joint and of the heads assembled after . The chain rule gives the term and the term . The term of depends only on variables below , hence not on , so that ; then and . Assembling before 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 , and the query .
Figure A.1.
ID returns
The procedure of this paper, Simplify (Algorithm 1), tries first. Its participating terms are and , so that , , and , and the loop runs through . The term for is the initial joint; Insert computes , finds that conditional on , , and joins the inserted term . Join then joins at , since , and Factorize sums out and divides by the inserted term:
The procedure starts again from the highest summation variable, . Its participating terms are and ; the term for does not contain and is not assembled. Here , and is joined to at , since , which gives
From here neither nor can be eliminated, because each needs the insertion of . For , , and , and this insertion, with , requires , which fails on the path , where is a conditioned collider and is not given. For $v_0
the insertion of requires , which fails on , and the procedure stops at (12), with two summations.
Suppose instead that, after , the procedure tries on (11). Since still occurs, now , and , and the loop runs through . The insertion of , with , requires , which holds because blocks the path above, and the inserted term is , which equals . Then is joined, is inserted with , since , and is joined at , which gives
In the same way is eliminated, inserting with , since , and the result is
with one summation instead of two; can no longer be eliminated, since fails. Both (12) and (14) are correct, and neither can be simplified further by joins and insertions. A summation variable above can thus be needed, in the conditioning set of an inserted term, for the elimination of .
TK, recalled in § 2, assembles for each summation variable the full joint of the terms whose heads lie between and the highest head (Definition 2.4), from the top down, inserts a missing variable when a join fails, and does not minimise.
For it joins to at : enters as an ancestor of , and remains, idle, in the new term .
For it fails, because the full assembly contains, besides the terms for and , the term for , which the reduced assembly leaves out and which depends on ; the join of then keeps among the conditions of the joint. A candidate set for the join of either drops , on which the joint depends, or keeps it, and then requires to be independent of given ; the insertion of requires to be independent of given and possibly ; both are excluded by the edge . The idle condition plays no part: the failure occurs as well when the term for is minimal.
For it succeeds, in a way that the procedure of this paper never follows. After the join of at , the joint conditions on , which lies above it. The join of fails, and , a condition of the joint, is inserted at , after , that is, out of topological order; then is joined at and at , and the result is (13). The procedure of this paper inserts before , 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 has checked that , so that the condition is idle, and by Appendix A.2 the two orders of assembly give the same terms. After another failed attempt on , TK eliminates in the same way and ends at (14).
The greater power of the reduced assembly is thus an obstacle in this example: by removing , which TK cannot remove, the procedure of this paper loses the variable that the later insertions of need, while TK, held up at , 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]J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–710, 1995.
- [2]J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd edition, 2009.
- [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]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]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]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]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]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]D. Geiger, T. Verma and J. Pearl. Identifying independence in Bayesian networks. Networks, 20(5):507–534, 1990.
- [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]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






