WorksMathematics
On the trajectories of the ID algorithm
Abstract
The ID algorithm decides whether an interventional distribution can be computed from observational data and, when it can, returns a formula in which products, ratios and summations of conditional probabilities are nested inside one another. We study these formulas by following the trajectories of the calls of the algorithm, each of which ends with a tail (an alternation of lines 7 and 2) and an exit, and we derive two main results. First, line~4 and the exit lines fix the single outer summation of the output, while the tail forms everything inside it, both the inner summations and the ratios. Second, a ratio keeps a summation in its denominator only when a repetition of the tail is entangled, and a test of ancestry in the original graph decides, before any formula is computed, whether a topological order can be chosen so as to avoid it. We also derive a bound on the nesting depth of the output, and show a simple ``dimensional'' count that every output has to satisfy. Together, these results constrain the form of an ID output and guide its implementation and simplification.
Introduction
The effect of an action, a decision or a policy is most reliably measured by an experiment, but experiments are often costly, unethical or infeasible, and one is then led to ask whether the same effect can be inferred from data that have merely been observed. The question acquires a precise form when the causal assumptions are encoded in a diagram , whose directed edges represent direct causal influence and whose bidirected edges represent latent common causes. The quantity of interest is the effect of an intervention, that is, the distribution that a set of outcomes would have if the variables were set by an external action rather than observed, and this effect is identifiable if it can be computed from the observational distribution and alone [3]. The do-calculus [3] is complete for this task [5, 1], but it does not prescribe the order in which its rules should be applied, and the decisive step towards an algorithm was the observation of Tian and Pearl [9, 10] that factorises over the -components of , the maximal sets of vertices connected by bidirected paths. The ID algorithm of Shpitser and Pearl [5, 7] turns this factorisation into a recursive procedure of seven lines, which decides identifiability in polynomial time (Section 2) and, when the effect is identifiable, returns a formula for it.1 The correctness of this procedure is well established, whereas much less is known about the formula that it returns, whose structure has so far been examined only in order to simplify it, and this formula is the subject of the present paper.
The formula that ID returns is built from (possibly nested) products, ratios and summations of conditional distributions , which we call terms. A familiar instance is the front-door graph for which ID returns
a formula whose two summations have different origins. The outer one, over , is written by line 4 of the algorithm and marginalises the variables that are neither intervened on nor queried. The inner one, over , arises at a later stage of the execution, where line 7, having isolated the c-component of , rebuilds a distribution on it, and the line 2 that follows marginalises , which is not an ancestor of within that component. We call such an alternation of lines 7 and 2 a tail, and each pair of lines a repetition of it. In larger graphs the tail has several repetitions, each of which, after the first, takes conditionals of a distribution that already carries a summation, and this is how ratios of sums come to appear inside further sums. Here and throughout, every variable is written with a capital letter. The letter thus occurs in (1) in two roles, as the intervened variable in , where it stands for the value set by the intervention, and as a summation variable inside the brackets.
Any implementation of the ID algorithm, such as the R package causaleffect (Tikka and Karvanen [12]) or the Python library of the same name (Pedemonte et al. [4]), has to store such formulas and, as far as possible, to simplify them. The ID algorithm writes a summation wherever a marginalisation is called for and a ratio wherever a conditional of a summed distribution is called for, whether or not the summation can be carried out or the ratio cancelled. Storing such formulas requires a class of expressions, and the available choices differ. For instance, Tikka and Karvanen [11] nest products and summations of terms into expressions and treat a quotient of two expressions separately, as a last operation, whereas Pedemonte et al. [4] use a recursive probability object, which may be summed over a set of variables and may carry a divisor of the same kind. Simplifying those expressions means carrying out summations ([11, 2]), cancelling factors within a single ratio, or cancelling factors between different ratios. These simplifications are applied to the finished formula or, at best, step by step while it is assembled, and in either case without regard to the way in which the algorithm produces it.
Here we study the formula at its source, by following the trajectories of the algorithm, that is, the sequences of lines through which it arrives at the formula, and we determine where the summations and the ratios of an output are created, which terms they involve and how deeply they can be nested. The trajectories, and the sets of vertices on which each of their lines acts, are obtained from the graph and the query by graph operations alone, so that this information is available before any formula is written; it constrains the expressions that an implementation has to represent and indicates where each kind of simplification can act. § 2 determines the trajectories that are possible and where the summations of the output are created. § 3 studies the ratios, which arise when the rebuild-and-marginalise step of the tail is repeated, and decides on the graph when they can be avoided. § 4 shows what simplification can do with the ratios that remain, and § 5 bounds the nesting depth of the output. All the proofs are collected in Appendix § 8.
The trajectories of ID
A term is a factor with a single variable , its head, and a set , its conditioning set. A call is an execution of , with , in which is the outcome set, the intervention set and the distribution argument, and it returns a formula built from terms unless it fails. Each call executes exactly one of the seven lines of the algorithm, namely the first whose test succeeds. Lines 2, 3 and 7 make one further call, the child of the call that executes them, line 4 makes of them, and lines 1 and 6 make none, while line 5 reports failure. The calls therefore follow one another along a single path or, when line 4 is executed, along the branches of a tree, the recursion tree. A trajectory is the sequence of the lines executed along a path from the root to a leaf. Figure 1 shows the recursion tree of the front-door query, whose trajectories are 4, 2, 6 and 4, 7, 2, 1. Throughout, the query is assumed identifiable, so that line 5 is never executed, and interventional, so that at the root.

Figure 1. The recursion tree of ID for the front-door query, with the line executed by each call and its arguments. The root, the only branching point, returns the product of the formulas and returned by its two branches, summed over its leftover set .
We write for the joint observational distribution of the vertices of the graph at hand. Until a line 6 or a line 7 is executed, a summation only reduces this joint distribution to the joint distribution of fewer vertices, which we still denote by and for which no explicit summation is written, as in the upper branch of Figure 1. These two lines are the first to break into terms, and line 7 passes the product of these terms on as the new distribution argument. The line 2 that follows places on this product a summation that is not a marginalisation of , so that the distribution argument differs from only in the tail.
The terms are formed with respect to a topological order of the vertex set of the query, which is fixed once and for all, and means that precedes in . If are the vertices of the vertex set of a call, we write , with , for the c-component of in the subgraph of induced on , and
where consists of and of the parents in of its members. Lines 6 and 7 form the Tian factors of the distribution argument (Tian and Pearl, [10], Lemmas 1 and 4). Every member of precedes , so that a Tian factor involves only variables up to its head. When , the Tian factor is the term (whose conditioning set is minimal under faithfulness; [10, 2]). In the front-door graph with the order , for instance, the c-component of is , the only parent that it adds is , and , which gives the term of (1). In the tail, where is no longer equivalent to , the Tian factors have to be computed from , and § 3 is devoted to this computation.
Two sets derived from the arguments of a call govern the analysis, the live set and the leftover set ,
which consist of the vertices that are not intervened on and, among these, of those that are not outcomes; at the root of Figure 1, and . We write for the subgraph of induced on and for the set of the c-components of a graph . When the test of line 4 fails, has a single c-component, which is the set denoted in lines 5–7 of the pseudocode, and at line 7 denotes the c-component of that strictly contains it. The table below lists, for each line, its test and the formula returned or the arguments , , , of its child. Two features of the table deserve a remark. First, a set formed at line 7 may contain vertices outside , which in the product passed on by line 7 are no longer variables but fixed values, as is in Figure 1; like every variable, they keep their capital letter. Second, summations enter the output in two ways: lines 1, 4 and 6 return a summation over the leftover set of their own call (at line 1 this set is , because is empty), and line 2 places one inside the distribution argument.
| line | test | ||||
| 1 | return | ||||
| 2 | |||||
| 3 | |||||
| 4 | return | ||||
| 5 | |||||
| 6 | return | ||||
| 7 |
Table 1.
The course of a trajectory is controlled by two properties of the live set of a call:
(A) every has a directed path to in with all its vertices in , where a path may have length zero, so that the vertices of always meet the requirement;
(B) has exactly one c-component, that is, has a single element.
We also say that a call is saturated when its leftover set is empty, that is, when , in which case (A) holds through paths of length zero. At the root of Figure 1, (A) holds because of the edge , whereas (B) fails, since and are not joined by a bidirected edge, and the two children of the root are saturated. Conditions (A) and (B) are identified with the outcomes of the tests of lines 3 and 4, as the following lemma shows.
Lemma 2.1. Condition (A) holds if and only if the test of line 3 fails, and (B) holds if and only if the test of line 4 fails, so that every call reaching line 5 or beyond satisfies both.
Lemma 2.1 describes a single call, whereas to follow a trajectory we also need to know what becomes of the two conditions when a call hands over to its child or children, which is the content of the next lemma. As it turns out, once both conditions hold they hold for the rest of the trajectory, which can then execute only lines 2 and 7 until it exits; the trajectory remains, so to speak, trapped, and this gives the lemma its name.
Lemma 2.2 (Trap Lemma). Line 2 under (A) and line 7 leave the live set and the graph induced on it unchanged, and therefore preserve (A), (B) and saturation. Each child of a line 4 is saturated and satisfies (A) and (B), while line 3 gives its child (A) but not necessarily (B).
Together, the two lemmas restrict the order in which the lines can follow one another, and the next lemma collects these restrictions; its item (iv) is the only one that uses identifiability.
Lemma 2.3 (Control flow). Along every trajectory
(i) line 2 is never immediately followed by line 2;
(ii) line 1 is immediately preceded by line 2;
(iii) condition (A) persists once established, and line 3 is executed at most once, at step 1 or 2;
(iv) the call immediately following a line 7 executes line 2.
Moreover, line 4 is executed at most once in the entire recursion tree.
To see why item (iv) holds, note that the child of a line 7 inherits (A) and (B), and that the test of line 5 succeeds there, because the vertex set of the child is a single c-component of its graph. Since the query is identifiable, the child has to be stopped by an earlier line, and line 2 is the only one that it can execute. The three lemmas, which are proved in Appendix § 8, leave little freedom to a trajectory, and Theorem 2.4 below shows that it consists of the four phases of Figure 2.

Figure 2. The four phases of a trajectory for an identifiable interventional query (Theorem 2.4).
Theorem 2.4 (Shape of a trajectory). Every trajectory consists of four consecutive phases: a clean-up, one of , 2, 3, 23; a branching, which is either empty or consists of line 4 followed, separately in each of its branches, by at most one line 2; a tail, in which the pair 7 2 is repeated times, each occurrence of the pair being a repetition; and an exit, line 6 or line 1, where line 1 is immediately preceded by a line 2 and neither exit is immediately preceded by line 7. If is the intervention set of the call at which the tail begins, then .
Consider again Figure 1: the upper trajectory has the branching 4 2, an empty tail and the exit 6, and the lower one has the branching 4, a tail with and the exit 1. Theorem 2.4 also bounds the total number of calls in the trajectories of a query, because it bounds each phase separately. The clean-up and line 4 account for at most three calls, and they are followed by branches ( if line 4 is not executed), each of which consists of at most one line 2, of the calls of its tail and of one exit. Since (at least one vertex is an outcome), the recursion tree has at most calls, with . Each call computes a bounded number of ancestral sets and of decompositions into c-components, so that ID decides identifiability in polynomial time, as Tian [8] observes for his identification algorithm.
Finally, Theorem 2.4 locates the two kinds of summation of an output, those over a leftover set and those that a line 2 places inside the distribution argument. The former are written at line 4 and at the exits, but if line 4 is executed the exits of its branches sum over the empty set, because every call after the branching is saturated (Lemma 2.2). The output thus carries exactly one such summation, written by line 4 if it is executed and by the single exit otherwise, and in both cases it runs over the leftover set of the call at which the clean-up ends, since neither the live set nor the outcome set changes along the tail. The latter remain in the output only when the line 2 belongs to a tail, where it acts on the product built by the preceding line 7. The following proposition records these observations, and expresses the set of the outer summation through the original graph alone.
Proposition 2.5. Every ID output has the form , with , where , and are the outcome set, the intervention set and the graph of the query. The summation over is written by line 4, if line 4 is executed, in which case is the product of the formulas returned by its branches, and by the exit of the only trajectory otherwise. Every summation inside is created by a line 2 of a tail and acts on the product built by the line 7 that precedes it.
In the front-door formula (1), line 4 is executed, the root sums over , and the summation over is created by the line 2 of the lower trajectory of Figure 1. When line 4 is not executed, the same set is summed by either of the exit lines 1 and 6. If the bidirected edge of the front-door graph joins and instead of and , for instance, the query is answered by line 6 alone, which returns , again with . In Example 3.5 below line 4 is not executed either, but the exit is saturated and all three summations arise in the tail.
Ratios along the tail
As we have seen in § 2, and in Theorem 2.4 in particular, the topological order plays no role in the trajectories. Every test, and every set passed to a child, is computed from , , and alone, so that the recursion tree, its trajectories and the sets on which each line acts are obtained from the graph and the query by graph operations, before any formula is written. The order enters only through the Tian factors formed at lines 6 and 7, and this section shows how these factors are written along the tail, when they are ratios, and when the order can prevent it.
The Tian factors of a summed product
The first call of a trajectory that executes line 6 or line 7 has , and its Tian factors are the terms . If this call executes line 7, the line 2 that follows sums out some vertices, and from then on the distribution argument is a summed product, which is not a marginal of . Its Tian factors are given by the generalised -decomposition of Tian and Pearl [10]. Let be the vertices of the call under consideration, that is, the elements of its own vertex set , which along the tail is a proper subset of the vertex set of the query. The lemma states that
where and the sets are called the prefixes of ; in its item (iii), the lemma adds that this ratio is a function of and only. As written, (2) divides by the marginal on the whole prefix , although by item (iii) the factor depends only on . What matters is therefore the prefix that ends at the last vertex of in the order , which we denote by , and (2) can be rewritten accordingly. Since the factor does not depend on the vertices , the identity can be summed over them, which gives
Two special cases are worth noting. When is empty there is no denominator, and the summation runs over all of ; when belongs to (as it does for every nonempty in the examples of this paper), and (3) coincides with (2). The following example shows what these formulas give when is a summed product.
Example 3.1. Consider the query on the graph of Figure 3. The root executes line 4, since the graph without , and has the c-components and . The branch for has the trajectory 4, 2, 6 and returns . The branch for has the trajectory 4, 7, 2, 7, 2, 1. Its first line 7 finds the c-component of , and becomes a fixed value. Inside this component the only directed edges are , and , so that is not an ancestor of , and the line 2 that follows sums it out. The next call has the vertex set , with the edges , and . It executes line 7 with , so that it has to form the Tian factors of and of , whose conditioning sets are and .
Take first the topological order . The first line 7 forms the terms , , and , so that the distribution argument of the second line 7 is
Figure 3. The graph of Example 3.1; dashed edges are bidirected.
The vertices of are , and , and its prefixes are , and .
By (2),
In the term of , which no other term mentions, has summed to one, whereas the summation over remains, because lies below and occurs in the term of . In the terms of , and have summed to one in turn. The Tian factors are therefore and
and after the last line 2 has summed out , the branch returns , a summation placed over a ratio. The same result is obtained in the topological order .
Take now the order . The first line 7 forms , , and , and is the sum over of their product. The set and its prefixes are the same, but now lies above , so that in the terms of and of sum to one in turn, and . This product, which carries no summation, divides , so that , and ID returns
which contains no quotient. The two formulas are equal, and they differ in form only because the summed vertex lies below , the last vertex of , in the first order and above it in the other.
The example already displays the main features of the general case, namely that the factors formed after a line 7 and a line 2 are ratios of sums of one and the same product, and that the position of the summed vertices in the topological order decides whether the sums of the denominators disappear. To describe the general case we first fix the notation for such a call.
Definition 3.2. Let be the calls of a trajectory that execute line 6 or line 7, in their order. For the call is a round. By Theorem 2.4, executes line 7 and is separated from by a single call, which executes line 2. The line 7 of retains a c-component and forms a factor for each of its vertices . The line 2 that follows splits into the set that it sums out and the set that it keeps, so that the round has the vertex set and the distribution argument . We write for the vertices of , and for the set of vertices whose Tian factors the round forms, which is its own set if it executes line 7 and if it executes line 6.
The following scheme summarises where the sets of a round come from.
line 7 (call ) line 2 line 6 or 7 (the round )
retains , forms the sums out , keeps forms the factors of
In Example 3.1 the second line 7 is a round. The first line 7 retains , whose four terms are the factors , line 2 sums out and keeps , and the round forms the factors of .
In a round, the sums (2) are computed as in the example, thanks to two properties of the factors . The distribution argument that a line 7 passes on is always a joint distribution of the vertices that it retains, written as a product of conditionals taken in the order , so that each factor sums to one over its head and involves only variables up to its head. The terms have these two properties, and (2) passes them on to the factors of every round, because involves only the variables of and sums to over . Summing over the vertices of above therefore removes, from the highest head down, every factor whose head lies above , and leaves2
The sum on a prefix is thus a truncation of the product at , which keeps the summations over the vertices of below . In the first order of Example 3.1, the truncation at keeps the summation over , and in the second it keeps no summation.
Entangled rounds
By (3) and (5), the factor that a round forms for is the ratio of two truncations of the same product, at and at the last vertex of . Its denominator is the shorter truncation, and it is a sum, rather than a plain product, exactly when a vertex of lies below .
Definition 3.3. A round is entangled at when is not empty and some vertex of precedes the last vertex of in the order . A round is entangled when it is so at one of its vertices.
Whether a round is entangled can be read off its last vertex alone. To see this, note that is an outcome, because every vertex of a round is an ancestor of in the graph of the round and no vertex lies above , and the c-component of an outcome in this graph is . The vertex then belongs to , because it is a member of , or a parent of , or both; indeed, if it is not a member of it is not an outcome, and its only way to reach passes through , the only vertex above it. The last vertex of is therefore (so that, for , (3) always has and coincides with (2)), and the last vertex of every other set precedes it, so that
a round is entangled if and only if some vertex of precedes ,
that is, if and only if a summed vertex has at least two vertices of above it. In Example 3.1, where , the round is entangled in the two orders in which precedes , and it is not entangled in the order . The proposition below gives the form of the factors of a round in the absence of entanglement.
Proposition 3.4. Consider a round, with the notation of Definition 3.2.
(i) If the round is not entangled, it creates no new ratio. The factor of every vertex of other than is the factor that the previous call formed for that vertex, unchanged, and the factor of absorbs the summation,
where is the set of the vertices of that precede .
(ii) In any round, the factor of a vertex at which the round is not entangled is formed without any division, and reads
where runs over the vertices of and is the last vertex of , the lower bounds being dropped when is empty.
The proof, a direct computation with (2), (3) and (5), is given in Appendix § 8. The factors in these formulas are those of the previous call, and they may themselves be ratios when an earlier round was entangled; a round that is not entangled hands such ratios on as they are and adds none of its own.
Two consequences of these formulas are useful in practice, the first of which concerns the factors that remain ratios. Written as in (2), the factors of two consecutive vertices and of that both belong to share a sum, the denominator of the second being the numerator of the first, so that in a product of the factors of consecutive vertices of only the last numerator and the first denominator remain (in graph (b) of Example 3.5 below, three ratios reduce in this way to one). An implementation should carry out this cancellation, which involves equal sums and requires no test.
The second consequence concerns the trajectories none of whose rounds is entangled. Along such a trajectory, statement (i) shows that each round hands on unchanged the terms formed by , except for the factor of the last vertex, which absorbs the summation over the vertices that have just been summed out, and the successive summations can be merged into one. The part of the output produced along such a trajectory is then a single summation over a product of terms formed by , and a query without entangled rounds is answered by a formula that contains no quotient. The following example shows a tail of two rounds, first without and then with entanglement, and makes both consequences explicit.
Example 3.5. Consider the query on each of the two graphs of Figure 4, which give rise to the same trajectory. The root call has and satisfies (A) and (B), so that neither line 3 nor line 4 is executed, and the trajectory is 7, 2, 7, 2, 7, 2, 1, a tail of the maximal length allowed by Theorem 2.4. The first line 7 retains the c-component of , so that becomes a fixed value, and the line 2 that follows sums out , which reaches only through . The second line 7 is a round with and . It retains , so that becomes a fixed value, and line 2 sums out , which reaches only through . The third line 7 is a round with , and , after which line 2 sums out and line 1 returns. The two graphs differ in the topological orders that they admit, and therefore in the formulas that ID returns.
Graph (a). Take the order , in which the first line 7 forms the six terms
In the first round lies above , the last but one vertex of , so that the round is not entangled. By Proposition 3.4(i) the factors of , and are their terms, and the factor of is, by (6), . In the second round $H_2
Figure 4. The two graphs of Example 3.5; dashed edges are bidirected. Graph (b) is graph (a) with the two additional edges and .
lies above , so that this round is not entangled either, the factor of is again , and the factor of is
where the two summations merge because , which lies above , does not occur in the term of . The summation over merges with them for the same reason, and line 1 returns
a single summation over a product of four of the six terms, the terms of and having left the product together with their heads.
Graph (b). The two additional edges leave a single topological order, . In it precedes every vertex of the first round and every vertex of the second, so that both rounds are entangled. The first line 7 forms the six terms
By (5), the sums of the first round on the prefixes ending at , , , and are , where , and its factors are for , for , for and for . The last three telescope, as observed above (each numerator cancels the denominator of the next factor), and their product is . The sums of the second round on the prefixes ending at , and are then , and , where , its factors are for and for , and the output is
Three summations are nested, and the ratios contain ratios, where (7) has a single summation and no ratio. None of the sums is a marginal of , because the product lacks the term of the fixed value , which depends on . Adding further pairs , , connected to their neighbours and to as in graph (b), gives for every the trajectory , whose rounds are all entangled, and an output with nested summations and nested ratios.
Entanglement from the graph
Whether a round is entangled depends on the topological order , while the sets and of Definition 3.2, like the outcome set of the round and the graph of the query, are the same in every order. As we have seen, a round is not entangled in exactly when every vertex of other than the last one precedes every vertex of . An order with this property may or may not exist, and the following theorem decides the matter from , , and ancestry in .
Theorem 3.6 (Entanglement from the graph). Consider a round with sets and and with outcome set , and let be one of its outcomes.
(i) Some topological order of leaves the round unentangled, with as the last outcome in this order, if and only if neither nor any vertex of is an ancestor in of a vertex of other than $z.
(ii) A single topological order of leaves all the rounds of the trajectory unentangled, with as the last outcome in this order, if and only if the condition of (i) holds at every round.
Since the last vertex of is always the last of the outcomes, a round can be freed of its entanglement by the choice of the order exactly when the condition of (i) holds for one of its outcomes; with a single outcome there is no choice, and the condition is that no vertex of be an ancestor in of a vertex of other than . In other words, the vertices that a round sums out must not be ancestors of the vertices that it retains, the last outcome excepted. The proof, given in Appendix § 8, is constructive, in that it builds the order whenever the condition holds, by listing first the vertices of other than together with all their ancestors in , and then the remaining vertices, among which are and the vertices of (for several rounds, whose sets are nested, the same is done from the innermost set outwards). The criterion is local, since it involves only the two sets of the round, which the trajectory provides, and it is evaluated before any formula is computed.
We now apply the criterion to the two examples, beginning with Example 3.1, where and . There the vertex is an ancestor of and of only, the condition holds, and the order that lists and first is . In graph (a) of Example 3.5, is an ancestor of and only and of and only, so that the condition holds at both rounds with ; the construction lists and , then and , then the remaining vertices, and gives the order used in the example. In graph (b), is an ancestor of , through , and is an ancestor of , through , so that the condition fails at both rounds. These two paths show how a failure arises when there is a single outcome. A summed vertex is not an ancestor of the outcome inside the component retained by the previous line 7, whereas the vertices of the round are. A directed path of from to one of them therefore has to leave that component, and to pass through a vertex that a line 7 of the tail has removed (as and are here).
The same example shows that the entanglement of a round has no consequence for the rounds that follow it, since each of the two additional edges of graph (b) governs one round. If only is added to graph (a), the first round is entangled in every order, because becomes an ancestor of , while the second is not entangled in the order . If only is added, it is the second round that is entangled in every order, while the first is not entangled in the order . The reason is that the tests of two successive rounds concern different paths. At a round with sets and , the test asks whether a directed path of leads from into . The vertices summed out before the next round belong to themselves, as do the vertices that the next round retains, so that the next test asks about paths between two parts of , which the first test neither constrains nor involves. Every round of a trajectory therefore has to be tested separately, which Theorem 3.6 allows for all of them at once, since the trajectory provides all their sets.
What an entangled round does hand on to the next is its ratios, which are among the factors of that round. A round that is not entangled leaves them as they are (Proposition 3.4(i)), and an entangled one places them inside new ratios, as on graph (b) of Example 3.5 in formula (8); in either case they remain in the output unless a later simplification removes them.
A last remark concerns the queries for which line 4 is executed, and whose recursion tree therefore has several trajectories. Theorem 3.6 applies to each trajectory separately, but ID uses a single topological order for all of them, and the requirements of two trajectories may be incompatible. This happens, for instance, when one branch sums out a vertex and retains a vertex , while another sums out and retains , since the first then needs to precede and the second needs the opposite. Each branch could then be freed of its entanglement by an order of its own, but no single order does so for both, and one of them keeps an entangled round.
Simplifying the ratios
Theorem 3.6 decides whether the entanglement of a round can be avoided, but it takes into account only the trivial summations, those of a factor that sums to one over its head. The summations in the denominator of an entangled ratio may still be carried out by other means, through the conditional independences among its terms, and this is found only by attempting the simplification [11, 2]. In Example 3.1, in the order , they can, since the terms of the denominator join into , and the denominator becomes . This section shows that a denominator freed of its summations in this way never has to be kept, and then gives two properties of the terms of an output on which a simplifier can rely, and by which the correctness of its result can be checked.
By (5), a ratio of a round, or the product of the ratios of consecutive vertices of , has the form
where is a product of factors, is a set of summed vertices and is the set of the heads that are free in and summed in . We consider simplifications of made of steps of two kinds, which together cover the four rewritings (R1)–(R4) of Lodato et al. [2]. A rearrangement replaces the product, or a part of it, by an expression that is equal to it for all values of the variables, and leaves the summation untouched. It may reorder and regroup the factors (R3), assemble terms into a joint distribution by the chain rule and by conditional independences (the joins and insertions of [11, 2]), factorise a joint distribution back into terms, or cancel equal factors. A summation eliminates a summed variable from a joint distribution of which it is one of the heads, replacing it by , when occurs in no other factor. This is the marginalisation (R4), applied once the other factors have been taken out of the sum (R2), and it reduces to (R1) when is the only head. The following theorem states that whatever these steps achieve on the denominator can be carried over to the numerator, by replaying them there one by one.
Theorem 4.1 (Replay). Let and be as in (9), where is a product of terms, some of which may be divisors. If rearrangements and summations remove all the summations of , the ratio equals a formula without quotient,
with one term, for a suitable set , for each variable summed out of . More generally, if these steps bring to the form , where is a product of terms, then with , and every factor of that does not involve cancels from .
In the proof, given in Appendix § 8, the chain rule sets aside one term for each variable that is summed out of . To see the theorem at work, take the ratio of Example 3.1 in the order , for which , and . The denominator is simplified in three steps: a summation over removes the term of , a rearrangement joins the three remaining terms into by the chain rule, and a summation over leaves , without summation. The replay sets aside one term at each summation, at the first and at the second, and the theorem gives
which is the factor that ID forms directly in the order . In the term the condition follows the head in the order of the computation; in general the terms need be neither minimal nor conditioned only on preceding variables, which a simplifier relying on either property has to take into account. The ratio of an entangled round thus survives simplification only if its denominator retains a summation that none of these steps removes.
The Replay theorem tells a simplifier what to do with a ratio once its denominator has been simplified. To find the simplifications in the first place, it helps to know which terms can occur in an output, and the two properties announced above concern them, the first being about conditioning sets. Each round writes its factors through those of the previous call, so that every term produced within a single branch is one of the terms formed by its call c1. Within a single branch every head therefore carries a single conditioning set, and the terms of the denominator of a ratio are among those of its numerator, so that cancelling factors within a ratio compares identical terms. Different branches of line 4, on the contrary, form their own terms and may give different conditioning sets to the same head, so that a cancellation between branches may not be available. Since the terms are minimal under faithfulness, conditions that can be dropped are created only by simplifying steps, such as those of Theorem 4.1, after which minimality has to be restored [2].
The second property is a count that every output satisfies, in the spirit of a dimensional check. For each variable, count for every term of which it is the head and for every summation over it, adding the counts of the factors of a product and subtracting that of a denominator from that of its numerator; the result is called the weight of the variable. A term behaves like a density in its head and a summation like an integration, so that the weight records whether an expression is still a density in the variable. By (2) and (5), the factor that ID forms for has weight 1 in and 0 in every other variable, and every summation of ID lowers a weight from 1 to 0, so that
in every ID output, each outcome of the query has weight 1 and every other variable has weight 0.
Let us count on the nested formula (8) of Example 3.5. The intervened variable is never a head and has weight 0. In every , the variable is the head of and is summed once, which gives , while each of the other heads of counts . The two tables below count the remaining variables, first in and then in the output .
| in | ||||||
| 0 | 0 | 0 | 0 | |||
| 0 | 0 | 0 | ||||
| 0 | 0 | 0 | 0 | |||
| weight | 0 | 0 | 1 | 1 | 1 |
Table 2.
| in the output | ||||
| 0 | 0 | |||
| 0 | ||||
| 0 | 0 | |||
| weight | 0 | 0 | 1 |
Table 3.
The rows of and in the second table are obtained as in the first, with and in the place of . The variable is the head of three factors of , two in the numerator and one in the denominator, and is summed once, which gives . The outcome ends with weight 1 and all the intervened variables with weight 0, although several of them occur as heads many times. The rewritings used in simplification preserve the weights, so that this count (a necessary, though not sufficient, condition for an expression to be a correct answer to the query) provides an inexpensive check on any implementation.3
Depth
The trajectories also bound how deeply the summations and ratios of an output are nested. The nesting depth of an expression is defined by
a summation over the empty set being omitted, and it has to be read up to the rearrangements that the formula allows. Summation indices are vertices of and are not renamed, so that a factor standing beside can be moved inside the summation only if no variable of occurs in , not even as a fixed value. In (1), contains the intervened variable , which is summed in the neighbouring factor, and the formula has depth two. By the depth of an ID output we therefore mean the least depth among the expressions obtained from it by such moves, by merging consecutive summations and by trivial summations.
The obstruction that keeps the two summations of (1) apart occurs only between the branches of line 4. Within a single branch, what becomes of the summation created by a line 2 depends on the round that follows it. If this round is not entangled, the summation is absorbed by the factor of the last vertex (Proposition 3.4(i)) and merges with the summation that later encloses this factor, as on graph (a) of Example 3.5, so that no level is added. If the round is entangled, the summation enters the numerator and the denominator of ratios, out of which it cannot be moved, and the depth increases by at most one.
Theorem 5.1 (Depth of an ID output). Let be the largest number of entangled rounds on a trajectory of the query, and the largest length of a tail. The output has depth at most if line 4 is not executed and at most if it is, and in both cases at most .
The proof is given in Appendix A, and it follows at once from the theorem that an output of depth three or more requires and , that is, an entangled round and a tail of at least two repetitions, which in turn requires an intervention set of at least four vertices at the beginning of the tail (Theorem 2.4). The bounds and are attained by the front-door formula (1), in which line 4 is executed, and , and the bound by graph (b) of Example 3.5 and its extensions, in which line 4 is not executed and the depth is with . Graph (a) of the same example, with the same trajectory and no entangled round, gives depth one. In Example 3.1 the branch for has depth one in the order and depth two in the order , where the summation over is placed over a ratio.
The number counts the entangled rounds of a trajectory wherever they occur along it, since, as we saw in Section 3, the entanglement of one round implies nothing about the others; with only one of the two additional edges of graph (b), for instance, the orders given there leave a single entangled round, and the output has depth at most two. The bound also refers to the formula as ID writes it, and therefore overestimates what remains after simplification, because Theorem 4.1 removes the quotients of every entangled round whose denominators are freed of their summations. The rounds that really force quotients inside summations are thus those whose entanglement resists simplification, and we have not proved a bound on the depth in terms of these rounds alone.
For an implementation, Proposition 2.5, Proposition 3.4 and Theorem 5.1 determine the mathematical structure of the output, and hence the kind of object that is needed to store it. After the trivial summations, the output reads , with one factor for each branch of line 4, or a single factor if line 4 is not executed. Without entangled rounds, each is a single summation over a product of terms, and two nested levels of summation, without any quotient, suffice. With entangled rounds, the object has to admit quotients inside summations, each quotient being the ratio of two sums (5) of the same product, nested to a depth that grows with the number of entangled rounds, and the recursive probability object of Pedemonte et al. [4] has this form. The expressions of Tikka and Karvanen [11] (which nest products and summations and admit a quotient only between two expressions, as a last operation) do not, so that neither the first formula of Example 3.1 nor the nested formula (8) fits their grammar.
Conclusion
We set out to understand the formula returned by the ID algorithm at its source, in order to know what such a formula can contain before it is stored or simplified. The answer lies in the trajectories of the algorithm, and the possible trajectories are few. Every trajectory consists of a clean-up, at most one branching, a tail in which lines 7 and 2 alternate, and an exit (Theorem 2.4), and this pattern, together with the sets on which each line acts, is obtained from the graph and the query by graph operations, independently of the topological order. The pattern accounts for every summation of the output: one outer summation, written by line 4 or, when line 4 is not executed, by the exit, runs in either case over the same set, which is read off the original graph, and all the others are created along the tail, each by a line 2 that marginalises the distribution rebuilt by the preceding line 7 (Proposition 2.5).
The ratios are created along the tail as well, and here the topological order matters. From the second repetition of the tail on, that is, at every round, each factor is the ratio of two sums of the same product, truncated at two vertices of the round, and its denominator carries a summation only where the round is entangled, that is, where a summed vertex precedes the last conditioning vertex of the factor (Proposition 3.4). Whether the order can be chosen so as to avoid the entanglement of a round is decided by a test of ancestry in the original graph, applied to the two sets of that round (Theorem 3.6); the test has to be made at every round, because the entanglement of one round implies nothing about the next. When the entanglement cannot be avoided, the summations of a denominator may still be removed by simplification, and a denominator that has been freed of its summations can always be cancelled (Theorem 4.1). Finally, the nesting depth of the output exceeds one, or two when line 4 is executed, by at most the number of entangled rounds (Theorem 5.1).
For an implementation these results fix what has to be represented and where simplification can act: quotients inside summations are needed only for entangled rounds, cancellation within a branch compares identical terms, and the weights of § 4 give a test that every output has to pass.
Acknowledgements
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.
Proofs
As in the table of § 2, unprimed symbols refer to the call that executes the line under consideration and primed symbols to the call that this line makes, its child. Thus is the live set of the child and its graph.
Proof of Lemma 2.1. A directed path of that starts outside contains no vertex of , because each of its later vertices is entered by an edge of the path, and has no edge entering . The test of line 3 fails when every vertex of is an ancestor of in . If (A) holds, the path that it provides for a vertex lies in , hence outside , so that it is also a path of and makes an ancestor of there; the test then fails. If, on the other hand, the test fails, every has a directed path to in . This path avoids by the remark above, so that it lies in , and it is a path of , since is with some edges deleted; this is (A). Both implications have been proved one vertex at a time, so that the same proof, applied to a single live vertex, shows that it is an ancestor of Y in if and only if it has a directed path to Y inside . This fact is used again below, in the proof of Lemma 2.2 (for line 3) and in that of Proposition 2.5. As for (B), the set contains Y and is not empty, so that has a c-component, and line 4 tests whether it has more than one.
Proof of Lemma 2.2. Line 2. Line 2 deletes the vertices that are not ancestors of Y. Under (A) every live vertex is an ancestor of Y, so that the deleted vertices are all intervened, and the child has the same live set as the call and the same graph induced on it (in formulas, and , so that , because ). Conditions (A) and (B) are properties of this graph, in which the paths required by (A) lie, and they therefore pass to the child; so does saturation, since the outcome set is not changed either.
Line 7. Line 7 deletes the vertices outside , which are all intervened, because . As at line 2, the live set and the graph induced on it are unchanged, so that (A) and (B), which hold at every call that reaches line 7, hold at the child, and saturation is preserved.
Line 4. The -th child has the graph , the outcome set Y and the intervention set , so that Y and the child is saturated. Condition (A) then holds through paths of length zero, and (B) holds because the vertices of , a c-component of , are connected by bidirected paths inside .
Line 3. The child has the graph , the outcome set Y and the intervention set , so that consists of the vertices of that are ancestors of Y in . A directed path from to Y in avoids , by the remark that opens the proof of Lemma 2.1, and every vertex of this path reaches Y along the remainder of the path, hence belongs to . Each vertex of thus reaches Y along a path that lies in , which is (A) for the child. Nothing can be said about (B), for two reasons. The test of line 3 precedes that of line 4, so that (B) need not hold at the call itself; and even when has a single c-component, may have several, because the bidirected paths that connected the vertices of may have passed through the removed set . The child of a line 3 can therefore execute line 4.
Proof of Lemma 2.3. (i) The child of a line 2 has the vertex set , and in the graph induced on this set every vertex is still an ancestor of Y, since a directed path to Y consists of ancestors of Y. The test of line 2 therefore fails at the child.
(ii) Line 1 requires an empty intervention set. The root has a nonempty one by assumption, and so has the child of a line 3, where , and of a line 4, where . The same holds for the child of a line 7, whose intervention set consists of the vertices of outside and is never empty, because line 7 is executed only when is a proper subset of . A call that executes line 1 can therefore only be the child of a line 2.
(iii) A call that satisfies (A) does not execute line 3 (Lemma 2.1), and if it executes line 2, 4 or 7 it passes (A) on to its children (Lemma 2.2), so that (A), once it holds, holds at all the descendants. Since line 3 gives (A) to its child, it is executed at most once on a trajectory. Moreover a call that executes line 3 does not satisfy (A), so that it is either the root or the child of a line 2, the only line whose child can fail to satisfy (A), since lines 3, 4 and 7 give (A) to theirs. In the second case the call that executes this line 2 does not satisfy (A) either, since line 2 would have passed it on, and by (i) it is not itself the child of a line 2, so that it is the root. Line 3 is therefore executed at step 1 or 2.
(iv) A call that executes line 7 satisfies (A) and (B), and so does its child (Lemma 2.2). At the child, the test of line 1 fails by (ii) and those of lines 3 and 4 fail by Lemma 2.1, whereas the test of line 5 succeeds, because the vertex set of the child is a single c-component of its graph. Since the query is identifiable, line 5 is not executed, so that the child is stopped by an earlier test, and only that of line 2 is left.
Line 4. A call that executes line 4 gives (A) and (B) to its children. Among the lines that make further calls, a call satisfying both conditions can execute only lines 2 and 7, which pass them on, so that no descendant of a line 4 executes line 4. Suppose now that two calls executed line 4. If one were a descendant of the other, this would contradict what has just been shown. Otherwise their paths from the root would separate at some call, which, being a branching point, would execute line 4 and have both of them among its descendants, which is again a contradiction, so that line 4 is executed at most once. □
Proof of Theorem 2.4. Let the clean-up be the initial run of lines 2 and 3 of the trajectory. By Lemma 2.3(iii), line 3 occurs in it at most once, as the first call or as the second after a line 2, and by Lemma 2.3(i) line 2 does not occur twice in a row. Nor does line 2 follow line 3, which changes neither the graph nor the outcome set, so that the test of line 2, which has just failed, fails again. The clean-up is therefore one of , 2, 3 and 2 3, and the call that follows it executes line 1, 4, 6 or 7. Lines 1 and 6 end the trajectory, whereas line 4 is executed at most once (Lemma 2.3), and not below a line 7, all of whose descendants satisfy (A) and (B); hence it occurs, if at all, immediately after the clean-up. Each of its children satisfies (A) and (B) and has a nonempty intervention set, so that it executes line 2, 6 or 7, and a line 2 is not followed by another.
From this point on every call satisfies (A) and (B), and the next line is 6, 7 or, after a line 2, line 1. A line 7 is followed by a line 2 (Lemma 2.3(iv)), after which the same three possibilities recur, so that the pair 7 2 is repeated until the trajectory exits at line 6 or at line 1; line 1 follows a line 2 by Lemma 2.3(ii), and neither exit follows a line 7.
For the bound on , the line 7 of a repetition deletes the set , which is not empty, since otherwise the test of line 5 would have succeeded, and is contained in , since . Its line 2 deletes the vertices of that are not ancestors of in , a set which is not empty, since the line was executed, and is contained in the intervention set, since by (A) all the live vertices are ancestors of . The sets deleted along the tail are disjoint subsets of , so that , with equality when they are single vertices that exhaust , as in Example 3.5 (, ). □
Proof of Proposition 2.5. The form of the output and the origin of its summations were established before the statement, and only the expression of remains to be proved. Let be the call at which the clean-up ends, that is, the first call after it, and its live set. The outcome set of this call is that of the query, and the output is summed over its leftover set, so that . Let be the set of the vertices from which can be reached by a directed path of , the original graph, that avoids the intervention set of the query, the vertices of included. It suffices to prove that , and we do so by following along the clean-up the set defined as follows.
For any call , we say that a live vertex is internal if it has a directed path to inside the live set, and external otherwise, and we write for the set of the internal vertices of . By the fact noted in the proof of Lemma 2.1, the internal vertices are the live vertices that are ancestors of in , and condition (A) says that no live vertex is external. At the root, by the definition of , since the live set of the root is .
Neither line of the clean-up changes . Line 2 deletes only vertices that are not ancestors of , whereas an internal vertex, like every vertex of the path that makes it internal, is an ancestor of ; the internal vertices and their paths thus survive, and no new one appears, since the child has a smaller live set and a smaller graph. Line 3 keeps the graph and moves to the intervention set exactly the external vertices, so that the live set of its child is ; the vertices of a path that makes a vertex internal are themselves internal, so that these paths survive as well, and the child has the same internal vertices.
Finally, the call has no external vertex, as we check on the four clean-ups of Theorem 2.4. If the clean-up ends with a line 3, this line has just moved every external vertex to the intervention set. If the clean-up is empty, is the root, which does not execute line 1, because its intervention set is not empty, nor line 2 or line 3: the test of line 3 is therefore reached and fails, so that no live vertex is external (Lemma 2.1). If the clean-up is a line 2 alone, is the child of this line 2, and the same argument applies (the test of line 3 fails) unless its intervention set is empty; in that case executes line 1, and all its vertices are live and are ancestors of , hence internal. In every case the live set of is , which equals because has not changed along the clean-up.
Proof of Proposition 3.4. (i) If the round is not entangled, every vertex of lies above . For the sum (5) then contains no vertex of and reads , so that the ratio (2) is . For , the heads up to are and the vertices of , so that
The factors involve only variables up to , hence no vertex of , and can be taken out of the summation. Their product is , and dividing by it leaves (6).
(ii) Suppose first that is not empty. Since the round is not entangled at , no vertex of precedes , so that the sum (5) for the prefix is the plain product , and this is the denominator of (3). In the numerator of (3), is given by (5) as a sum over the vertices of below , and (3) sums it further over ; together these are all the vertices of with , since no vertex of lies below . The factors with involve only variables up to , hence none of the summed ones, so that their product can be taken out of the summations of the numerator, where it cancels against the denominator, and what remains is the expression of the statement.
If is empty, (3) has no denominator. Its numerator sums over , and by (5) is itself the sum, over the vertices of below , of the product of all the factors with . The two summations together run over all the vertices of , which gives the expression of the statement without its lower bounds.
Proof of Theorem 3.6. We write for the set of the vertices from which a directed path of , possibly of length zero, leads to a vertex of . The proof uses two facts. First, contains every parent of each of its vertices, that is, if and is an edge of , then . Second, as shown after Definition 3.3, a round is not entangled in an order if and only if every vertex of other than the last one precedes every vertex of in ; moreover the last vertex of is an outcome, and hence the last of the outcomes, since contains .
(i) Suppose that the round is not entangled in a topological order in which is the last outcome. By the second fact is the last vertex of , so that every vertex of precedes , and it precedes every vertex of . On the other hand, a directed path of from a vertex to forces , because every edge of goes from an earlier to a later vertex of . No such path can therefore start at or at a vertex of , which is the condition of the statement.
Conversely, suppose that satisfies the condition, and let . The condition says precisely that contains neither nor any vertex of . We build in two blocks, listing first the vertices of (which are thus the earliest vertices of ), in a topological order of the subgraph that they induce, and then all the other vertices, among which are and the vertices of , in a topological order of theirs. The result is a topological order of , because an edge between two vertices of the same block is respected by construction, and an edge between the blocks cannot lead from the second block to the first, since would imply . In this order every vertex of , which lies in the first block, precedes and all the vertices of , which lie in the second. Hence is the last vertex of , and therefore the last outcome, the other vertices of precede those of , and the round is not entangled.
With a single outcome , the vertex can only be . Every other vertex of is an ancestor of in the graph of the round, hence in , and a directed path from to one of them would close a directed cycle, so that the part of the condition that concerns holds automatically.
(ii) Let and be the sets of the rounds , for $2\le s\le t$. The vertices of a round are among those of the previous round, when there is one, so that , and every $\mathbf{V}_s contains . If a single order leaves all the rounds unentangled with as the last outcome, then is the last vertex of every , and the first part of the proof of (i) gives the condition at every round.
Conversely, suppose that the condition holds at every round, and let , so that . We now build in blocks, listing first the vertices of (the earliest of ), then those of , and so on up to , and finally the vertices outside , each block in a topological order of the subgraph that it induces. As before, an edge cannot lead from a later block to an earlier one, because then belongs to a set that does not contain , whereas contains every parent of . The result is therefore a topological order of . For every , the vertices of lie in , whereas and the vertices of lie outside by the condition, and are listed after all the vertices of . More precisely, lies outside every , hence in the last block. The vertices of lie in the block if (they are vertices of other than , hence belong to , and they lie outside ), and in the last block if . Every round is therefore not entangled in this order, and is its last outcome. On graph (a) of Example 3.5, for instance, where and , the blocks are , and , and listing them in turn gives the order used there.
Proof of Theorem 4.1. We prove the general statement, of which the first is the case , where does not involve and cancels entirely. We follow the steps of the simplification of , writing for its product after steps, and we maintain an identity , valid for all values of the variables, in which is a product of one term for each variable summed out so far, none of which occurs in . Initially and . A rearrangement replaces by an expression equal to it for all values, and is kept. A summation replaces a joint distribution of , where is the set of the heads joined in it, by . By the chain rule, which requires no condition, , so that , and the last term is appended to . After this step no longer occurs in , and later steps do not reintroduce it. At the end for all values of the variables, where is the product of the terms set aside, one for each variable of , whence . A factor of that does not involve involves no variable of either, because the variables of outside have been summed out of and do not occur in ; such a factor can therefore be taken out of both summations and cancelled.
Proof of Theorem 5.1. Fix a trajectory, and let be its calls that execute line 6 or line 7, as in Definition 3.2, so that are its rounds. We call sum over a summation, possibly over the empty set, of a product of factors formed by , and we write for the largest depth of such an expression. The factors of are terms, of depth zero, and a summation of a product of terms has depth one, so that .
For , by (2) and (5) every factor of the round is a sum over or the ratio of two of them, both of which have depth at most , and a sum over places one more summation on a product of such factors. A round thus adds at most one level, that is, . If the round is not entangled, it adds none, and the bound improves to . Indeed, by Proposition 3.4(i) the factors of are those of , except for the factor (6) of the last vertex , which carries a summation over . The vertices of lie above every vertex of the round other than , and the factor of a vertex involves only variables up to that vertex, so that they do not occur in the other factors of . In a sum over , the summation over can therefore be extended to the whole product and merged with the outer summation, as on graph (a) of Example 3.5, and the result is a sum over . Since , it follows that is at most one plus the number of entangled rounds among , so that , and that for every .
Suppose first that line 4 is not executed. The output is then a sum over , since the exit sums the product of the factors of over at line 6, and over at line 1, where is the set summed out by the line 2 that precedes it (if , the exit must be line 1, which returns a marginal of , of depth zero). Its depth is therefore at most . This is also at most , because a tail of repetitions contains at most rounds, so that .
Suppose now that line 4 is executed. Each branch returns an expression of depth at most , as we have just seen, and line 4 sums the product of these expressions, which adds at most one level and gives . For the bound we use that the branches are saturated (Lemma 2.2), so that their exits sum over an empty leftover set. Consider a branch whose tail has repetitions. If it exits at line 6, it returns the product of the factors of , without any summation, and each of these factors has depth at most . If it exits at line 1, it returns a sum over , of depth at most . In both cases the depth is at most (and zero if , where the branch returns terms or a marginal of ), and the summation of line 4 brings it to at most .
References
- [1]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. arXiv:1206.6831.
- [2]I. Lodato, S. Hiranandani, and A. V. Iyer. A fast and sound algorithm to simplify summations in interventional queries expressions. arXiv:2611.18416, 2026.
- [3]J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–688, 1995. doi:10.1093/biomet/82.4.669.DOI
- [4]M. Pedemonte, J. Vitrià, and Á. Parafita. Algorithmic causal effect identification with causaleffect. arXiv:2107.04632, 2021.arxiv.org/abs/2107.04632
- [5]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, 2006a. mlanthology.org/aaai/2006/shpitser2006aaai-identification.
- [6]I. Shpitser and J. Pearl. Identification of conditional interventional distributions. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, pages 437–444, 2006b. arXiv:1206.6876.
- [7]I. Shpitser and J. Pearl. Complete identification methods for the causal hierarchy. Journal of Machine Learning Research, 9:1941–1979, 2008. jmlr.org/papers/v9/shpitser08a.
- [8]J. Tian. Identifying conditional causal effects. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pages 561–568, 2004. arXiv:1207.4161.
- [9]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. escholarship.org/uc/item/17r754xz.
- [10]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. ftp.cs.ucla.edu/pub/stat_ser/R290-L.pdf.
- [11]S. Tikka and J. Karvanen. Simplifying probabilistic expressions in causal inference. Journal of Machine Learning Research, 18(36):1–30, 2017a. jmlr.org/papers/v18/16-166.
- [12]S. Tikka and J. Karvanen. Identifying causal effects with the R package causaleffect. Journal of Statistical Software, 76(12):1–30, 2017b. doi:10.18637/jss.v076.i12.

