betaFeedback

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 GG, 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 P(Y∣X^)P(\mathbf{Y} \mid\hat{\mathbf{X}}) that a set of outcomes Y\mathbf{Y} would have if the variables X\mathbf{X} were set by an external action rather than observed, and this effect is identifiable if it can be computed from the observational distribution P(V)P(\mathbf{V}) and GG 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 P(V)P(\mathbf{V}) factorises over the cc-components of GG, 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 P(V∣C)P(\mathbf{V} \mid C), which we call terms. A familiar instance is the front-door graph for which ID returns

P(Y∣X^)=∑Z(P(Z∣X)∑XP(X)P(Y∣X,Z)),(1)P(Y \mid\hat{X}) = \sum_{Z} \left(P(Z \mid X) \sum_{X} P(X) P(Y \mid X,Z)\right), \tag*{(1)}

a formula whose two summations have different origins. The outer one, over ZZ, is written by line 4 of the algorithm and marginalises the variables that are neither intervened on nor queried. The inner one, over XX, arises at a later stage of the execution, where line 7, having isolated the c-component {X,Y}\{X,Y\} of YY, rebuilds a distribution on it, and the line 2 that follows marginalises XX, which is not an ancestor of YY 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 XX thus occurs in (1) in two roles, as the intervened variable in P(Z∣X)P(Z \mid X), 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 P(V∣C)P(V \mid C) with a single variable VV, its head, and a set C≠VC \ne V, its conditioning set. A call is an execution of ID⁡(Y,X,Q,G)\operatorname{ID}(Y,X,Q,G), with G=(V,E)G=(V,E), in which YY is the outcome set, XX the intervention set and QQ 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 k≥2k \ge2 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 X≠∅\mathbf{X} \ne\varnothing at the root.

The recursion tree of ID for the front-door query

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 F1F_1 and F2F_2 returned by its two branches, summed over its leftover set SL={Z}\mathbf{S}_{\mathrm{L}} = \{Z\}.

We write PP 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 PP and for which no explicit summation is written, as in the upper branch of Figure 1. These two lines are the first to break PP 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 PP, so that the distribution argument differs from PP only in the tail.

The terms are formed with respect to a topological order π\pi of the vertex set V0\mathbf{V}_0 of the query, which is fixed once and for all, and u<vu < v means that uu precedes vv in π\pi. If V1<⋯<Vn\mathbf{V}_1 < \cdots< \mathbf{V}_n are the vertices of the vertex set V\mathbf{V} of a call, we write V(i)={V1,…,Vi}\mathbf{V}^{(i)} = \{\mathbf{V}_1, \ldots, \mathbf{V}_i\}, with V(0)=∅\mathbf{V}^{(0)} = \varnothing, TiT_i for the c-component of ViV_i in the subgraph of GG induced on V(i)\mathbf{V}^{(i)}, and

Ci=Pa(Ti)∖{Vi},C_i = Pa(T_i) \setminus\{V_i\},

where Pa(Ti)Pa(T_i) consists of TiT_i and of the parents in GG of its members. Lines 6 and 7 form the Tian factors Q(Vi∣Ci)Q(V_i \mid C_i) of the distribution argument (Tian and Pearl, [10], Lemmas 1 and 4). Every member of CiC_i precedes ViV_i, so that a Tian factor involves only variables up to its head. When Q=PQ = P, the Tian factor is the term P(Vi∣Ci)P(V_i \mid C_i) (whose conditioning set is minimal under faithfulness; [10, 2]). In the front-door graph with the order X<Z<YX < Z < Y, for instance, the c-component of YY is T3={X,Y}T_3 = \{X,Y\}, the only parent that it adds is ZZ, and C3={X,Z}C_3 = \{X,Z\}, which gives the term P(Y∣X,Z)P(Y \mid X,Z) of (1). In the tail, where QQ is no longer equivalent to PP, the Tian factors have to be computed from QQ, and § 3 is devoted to this computation.

Two sets derived from the arguments of a call govern the analysis, the live set S\mathbf{S} and the leftover set SL\mathbf{S}_{\mathrm{L}},

S=V∖X,SL=S∖Y,\mathbf{S} = \mathbf{V} \setminus\mathbf{X}, \qquad\mathbf{S}_{\mathrm{L}} = \mathbf{S} \setminus\mathbf{Y},

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, S={Z,Y}\mathbf{S} = \{Z,Y\} and SL={Z}\mathbf{S}_{\mathrm{L}} = \{Z\}. We write G[S]G[\mathbf{S}] for the subgraph of GG induced on S\mathbf{S} and C(G)\mathcal{C}(G) for the set of the c-components of a graph GG. When the test of line 4 fails, G[S]G[\mathbf{S}] has a single c-component, which is the set denoted S\mathbf{S} in lines 5–7 of the pseudocode, and at line 7 S+\mathbf{S}^{+} denotes the c-component of GG that strictly contains it. The table below lists, for each line, its test and the formula returned or the arguments V′\mathbf{V}', Y′\mathbf{Y}', X′\mathbf{X}', Q′Q' of its child. Two features of the table deserve a remark. First, a set CiC_i formed at line 7 may contain vertices outside S+S^+, which in the product passed on by line 7 are no longer variables but fixed values, as ZZ 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 V∖YV \setminus Y, because XX is empty), and line 2 places one inside the distribution argument.

linetestV′V'Y′Y'X′X'Q′Q'
1X=∅X = \varnothingreturn ∑SLQ\sum_{S_L} Q
2V≠An⁡(Y)GV \ne\operatorname{An}(Y)_GAn⁡(Y)G\operatorname{An}(Y)_GYYX∩V′X \cap V'∑V∖V′Q\sum_{V \setminus V'} Q
3W:=S∖An⁡(Y)GX≠∅W := S \setminus\operatorname{An}(Y)_{G_X} \ne\varnothingVVYYX∪WX \cup WQQ
4C(G[S])={S1,…,Sk}, k>1C(G[S]) = \{S_1,\ldots,S_k\},\ k > 1return ∑SL∏i=1kID⁡(Si,V∖Si,Q,G)\sum_{S_L} \prod_{i=1}^{k} \operatorname{ID}(S_i,V \setminus S_i,Q,G)
5C(G)={V}C(G) = \{V\}FAIL\mathrm{FAIL}
6S∈C(G)S \in C(G)return ∑SL∏Vi∈SQ(Vi∣Ci)\sum_{S_L} \prod_{V_i \in S} Q(V_i \mid C_i)
7S⊂S+∈C(G)S \subset S^+ \in C(G)S+S^+YYX∩S+X \cap S^+∏Vi∈S+Q(Vi∣Ci)\prod_{V_i \in S^+} Q(V_i \mid C_i)

Table 1.

The course of a trajectory is controlled by two properties of the live set SS of a call:

(A) every v∈Sv \in S has a directed path to YY in GG with all its vertices in SS, where a path may have length zero, so that the vertices of YY always meet the requirement;

(B) G[S]G[S] has exactly one c-component, that is, C(G[S])C(G[S]) has a single element.

We also say that a call is saturated when its leftover set is empty, that is, when S=YS = Y, in which case (A) holds through paths of length zero. At the root of Figure 1, (A) holds because of the edge Z→YZ \to Y, whereas (B) fails, since ZZ and YY 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.

The four phases of a trajectory for an identifiable interventional query

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 ∅\varnothing, 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 m≥0m \ge0 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 X0\mathbf{X}_0 is the intervention set of the call at which the tail begins, then m≤⌊∣X0∣/2⌋m \le\lfloor|\mathbf{X}_0|/2 \rfloor.

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 m=1m = 1 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 kk branches (k=1k = 1 if line 4 is not executed), each of which consists of at most one line 2, of the 2m2m calls of its tail and of one exit. Since 2m≤∣X0∣<∣V0∣2m \le|\mathbf{X}_0| < |\mathbf{V}_0| (at least one vertex is an outcome), the recursion tree has at most 3+k(∣V0∣+1)3 + k(|\mathbf{V}_0| + 1) calls, with k<∣V0∣k < |\mathbf{V}_0|. 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 SL\mathbf{S}_L 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 ∑SLΦ\sum_{\mathbf{S}_L} \Phi, with SL=An⁡(Y)G0[V0∖X]∖Y\mathbf{S}_L = \operatorname{An}(\mathbf{Y})_{G_0[\mathbf{V}_0 \setminus\mathbf{X}]} \setminus\mathbf{Y}, where Y\mathbf{Y}, X\mathbf{X} and G0G_0 are the outcome set, the intervention set and the graph of the query. The summation over SL\mathbf{S}_L is written by line 4, if line 4 is executed, in which case Φ\Phi is the product of the formulas returned by its branches, and by the exit of the only trajectory otherwise. Every summation inside Φ\Phi 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 SL={Z}\mathbf{S}_L = \{Z\}, and the summation over X\mathbf{X} 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 ZZ and YY instead of XX and YY, for instance, the query P(Y∣X^)P(Y \mid\widehat{X}) is answered by line 6 alone, which returns ∑ZP(Z∣X)P(Y∣X,Z)\sum_Z P(Z \mid X)P(Y \mid X,Z), again with SL={Z}\mathbf{S}_L = \{Z\}. 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 π\pi plays no role in the trajectories. Every test, and every set passed to a child, is computed from V\mathbf{V}, Y\mathbf{Y}, X\mathbf{X} and GG 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 Q=PQ=P, and its Tian factors are the terms P(Vi∣Ci)P(V_i \mid C_i). 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 PP. Its Tian factors are given by the generalised QQ-decomposition of Tian and Pearl [10]. Let V1<⋯<VnV_1 < \cdots< V_n be the vertices of the call under consideration, that is, the elements of its own vertex set V\mathbf{V}, which along the tail is a proper subset of the vertex set V0\mathbf{V}_0 of the query. The lemma states that

Q(Vi∣Ci)=Q[V(i)]Q[V(i−1)],Q[V(i)]=∑Vi+1,…,VnQ,(2)Q(V_i \mid C_i) = \frac{Q[\mathbf{V}^{(i)}]}{Q[\mathbf{V}^{(i-1)}]}, \qquad Q[\mathbf{V}^{(i)}] = \sum_{V_{i+1},\ldots,V_n} Q, \tag*{(2)}

where Q[V(0)]=1Q[\mathbf{V}^{(0)}] = 1 and the sets V(i)\mathbf{V}^{(i)} are called the prefixes of V\mathbf{V}; in its item (iii), the lemma adds that this ratio is a function of ViV_i and CiC_i only. As written, (2) divides by the marginal on the whole prefix V(i−1)\mathbf{V}^{(i-1)}, although by item (iii) the factor depends only on CiC_i. What matters is therefore the prefix that ends at the last vertex of CiC_i in the order π\pi, which we denote by VℓV_\ell, and (2) can be rewritten accordingly. Since the factor does not depend on the vertices Vℓ+1,…,Vi−1V_{\ell+1}, \ldots, V_{i-1}, the identity Q[V(i)]=Q(Vi∣Ci)Q[V(i−1)]Q[\mathbf{V}^{(i)}] = Q(V_i \mid C_i) Q[\mathbf{V}^{(i-1)}] can be summed over them, which gives

Q(Vi∣Ci)=∑Vℓ+1,…,Vi−1Q[V(i)]Q[V(ℓ)].(3)Q(V_i \mid C_i) = \frac{\sum_{V_{\ell+1},\ldots,V_{i-1}} Q[\mathbf{V}^{(i)}]}{Q[\mathbf{V}^{(\ell)}]}. \tag*{(3)}

Two special cases are worth noting. When CiC_i is empty there is no denominator, and the summation runs over all of V(i−1)\mathbf{V}^{(i-1)}; when Vi−1V_{i-1} belongs to CiC_i (as it does for every nonempty CiC_i in the examples of this paper), ℓ=i−1\ell= i - 1 and (3) coincides with (2). The following example shows what these formulas give when QQ is a summed product.

Example 3.1. Consider the query P(Y∣A^,X^,C^)P(Y \mid\hat{A}, \hat{X}, \hat{C}) on the graph of Figure 3. The root executes line 4, since the graph without AA, XX and CC has the c-components {B}\{B\} and {Y}\{Y\}. The branch for BB has the trajectory 4, 2, 6 and returns P(B∣X)P(B \mid X). The branch for YY has the trajectory 4, 7, 2, 7, 2, 1. Its first line 7 finds the c-component S+={A,X,C,Y}S^+ = \{A, X, C, Y\} of YY, and BB becomes a fixed value. Inside this component the only directed edges are A→XA \to X, A→CA \to C and C→YC \to Y, so that XX is not an ancestor of YY, and the line 2 that follows sums it out. The next call has the vertex set V={A,C,Y}\mathbf{V} = \{A, C, Y\}, with the edges A→CA \to C, C→YC \to Y and A↔YA \leftrightarrow Y. It executes line 7 with S+={A,Y}S^+ = \{A, Y\}, so that it has to form the Tian factors of AA and of YY, whose conditioning sets are C1=∅C_1 = \varnothing and C3={A,C}C_3 = \{A, C\}.

Take first the topological order A<X<C<B<YA < X < C < B < Y. The first line 7 forms the terms P(A)P(A), P(X∣A)P(X \mid A), P(C∣A,X)P(C \mid A, X) and P(Y∣A,X,C,B)P(Y \mid A, X, C, B), so that the distribution argument of the second line 7 is

Q=∑XP(A)P(X∣A)P(C∣A,X)P(Y∣A,X,C,B).Q = \sum_X P(A) P(X \mid A) P(C \mid A, X) P(Y \mid A, X, C, B).

Figure 3. The graph of Example 3.1; dashed edges are bidirected.

The vertices of V\mathbf{V} are V1=AV_1=A, V2=CV_2=C and V3=YV_3=Y, and its prefixes are {A}\{A\}, {A,C}\{A,C\} and {A,C,Y}\{A,C,Y\}.

By (2),

Q[A,C,Y]=Q,Q[A,C,Y]=Q,
Q[A,C]=∑YQ=∑XP(A)P(X∣A)P(C∣A,X),Q[A,C]=\sum_Y Q=\sum_X P(A)P(X\mid A)P(C\mid A,X),
Q[A]=∑C,YQ=P(A).Q[A]=\sum_{C,Y}Q=P(A).

In Q[A,C]Q[A,C] the term of YY, which no other term mentions, has summed to one, whereas the summation over XX remains, because XX lies below CC and occurs in the term of CC. In Q[A]Q[A] the terms of YY, CC and XX have summed to one in turn. The Tian factors are therefore Q(A)=P(A)Q(A)=P(A) and

Q(Y∣A,C)=Q[A,C,Y]Q[A,C]=∑XP(A)P(X∣A)P(C∣A,X)P(Y∣A,X,C,B)∑XP(A)P(X∣A)P(C∣A,X),Q(Y\mid A,C)=\frac{Q[A,C,Y]}{Q[A,C]}=\frac{\sum_X P(A)P(X\mid A)P(C\mid A,X)P(Y\mid A,X,C,B)}{\sum_X P(A)P(X\mid A)P(C\mid A,X)},

and after the last line 2 has summed out AA, the branch returns ∑AP(A)Q(Y∣A,C)\sum_A P(A)Q(Y\mid A,C), a summation placed over a ratio. The same result is obtained in the topological order A<X<B<C<YA<X<B<C<Y.

Take now the order A<C<X<B<YA<C<X<B<Y. The first line 7 forms P(A)P(A), P(C∣A)P(C\mid A), P(X∣A,C)P(X\mid A,C) and P(Y∣A,C,X,B)P(Y\mid A,C,X,B), and QQ is the sum over XX of their product. The set V\mathbf{V} and its prefixes are the same, but XX now lies above CC, so that in Q[A,C]=∑YQQ[A,C]=\sum_Y Q the terms of YY and of XX sum to one in turn, and Q[A,C]=P(A)P(C∣A)Q[A,C]=P(A)P(C\mid A). This product, which carries no summation, divides Q[A,C,Y]=P(A)P(C∣A)∑XP(X∣A,C)P(Y∣A,C,X,B)Q[A,C,Y]=P(A)P(C\mid A)\sum_X P(X\mid A,C)P(Y\mid A,C,X,B), so that Q(Y∣A,C)=∑XP(X∣A,C)P(Y∣A,C,X,B)Q(Y\mid A,C)=\sum_X P(X\mid A,C)P(Y\mid A,C,X,B), and ID returns

P(Y∣A^,X^,C^)=∑BP(B∣X)∑A,XP(A)P(X∣A,C)P(Y∣A,X,B,C),(4)P(Y\mid\hat{A},\hat{X},\hat{C})=\sum_B P(B\mid X)\sum_{A,X}P(A)P(X\mid A,C)P(Y\mid A,X,B,C), \tag*{(4)}

which contains no quotient. The two formulas are equal, and they differ in form only because the summed vertex XX lies below CC, the last vertex of C3C_3, 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 c1,…,ctc_1,\ldots,c_t be the calls of a trajectory that execute line 6 or line 7, in their order. For s≥2s\ge2 the call csc_s is a round. By Theorem 2.4, cs−1c_{s-1} executes line 7 and is separated from csc_s by a single call, which executes line 2. The line 7 of cs−1c_{s-1} retains a c-component S+\mathbf{S}^{+} and forms a factor qhq_h for each of its vertices hh. The line 2 that follows splits S+\mathbf{S}^{+} into the set U\mathbf{U} that it sums out and the set V\mathbf{V} that it keeps, so that the round csc_s has the vertex set V=S+∖U\mathbf{V}=\mathbf{S}^{+}\setminus\mathbf{U} and the distribution argument Q=∑U∏hqhQ=\sum_{\mathbf{U}}\prod_h q_h. We write V1<⋯<VnV_1<\cdots<V_n for the vertices of V\mathbf{V}, and K⊆V\mathbf{K}\subseteq\mathbf{V} for the set of vertices whose Tian factors the round forms, which is its own set S+\mathbf{S}^{+} if it executes line 7 and S\mathbf{S} if it executes line 6.

The following scheme summarises where the sets of a round come from.

line 7 (call cs−1c_{s-1}) ⟶\longrightarrow line 2 ⟶\longrightarrow line 6 or 7 (the round csc_s)

retains S+\mathbf{S}^{+}, forms the qhq_h             sums out U\mathbf{U}, keeps V=S+∖U\mathbf{V}=\mathbf{S}^{+}\setminus\mathbf{U}             forms the factors of K⊆V\mathbf{K}\subseteq\mathbf{V}

In Example 3.1 the second line 7 is a round. The first line 7 retains S+={A,X,C,Y}\mathbf{S}^{+}=\{A,X,C,Y\}, whose four terms are the factors qhq_h, line 2 sums out U={X}\mathbf{U}=\{X\} and keeps V={A,C,Y}\mathbf{V}=\{A,C,Y\}, and the round forms the factors of K={A,Y}\mathbf{K}=\{A,Y\}.

In a round, the sums (2) are computed as in the example, thanks to two properties of the factors qhq_h. 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 π\pi, so that each factor qhq_h 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 Q[V(i)]Q[\mathbf{V}^{(i)}] involves only the variables of V(i)\mathbf{V}^{(i)} and sums to Q[V(i−1)]Q[\mathbf{V}^{(i-1)}] over ViV_i. Summing QQ over the vertices of V\mathbf{V} above ViV_i therefore removes, from the highest head down, every factor whose head lies above ViV_i, and leaves2

Q[V(i)]=∑u∈U,u<Vi∏h≤Viqh.(5)Q[\mathbf{V}^{(i)}] = \sum_{\substack{u \in\mathbf{U},\,u < V_i}} \prod_{h \le V_i} q_h. \tag*{(5)}

The sum on a prefix is thus a truncation of the product at ViV_i, which keeps the summations over the vertices of U\mathbf{U} below ViV_i. In the first order of Example 3.1, the truncation at CC keeps the summation over XX, and in the second it keeps no summation.

Entangled rounds

By (3) and (5), the factor that a round forms for ViV_i is the ratio of two truncations of the same product, at ViV_i and at the last vertex VℓV_\ell of CiC_i. Its denominator is the shorter truncation, and it is a sum, rather than a plain product, exactly when a vertex of U\mathbf{U} lies below VℓV_\ell.

Definition 3.3. A round is entangled at Vi∈KV_i \in\mathbf{K} when CiC_i is not empty and some vertex of U\mathbf{U} precedes the last vertex of CiC_i in the order π\pi. 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 VnV_n is an outcome, because every vertex of a round is an ancestor of Y\mathbf{Y} in the graph of the round and no vertex lies above VnV_n, and the c-component of an outcome in this graph is K\mathbf{K}. The vertex Vn−1V_{n-1} then belongs to CnC_n, because it is a member of K\mathbf{K}, or a parent of VnV_n, or both; indeed, if it is not a member of K\mathbf{K} it is not an outcome, and its only way to reach Y\mathbf{Y} passes through VnV_n, the only vertex above it. The last vertex of CnC_n is therefore Vn−1V_{n-1} (so that, for VnV_n, (3) always has ℓ=n−1\ell= n - 1 and coincides with (2)), and the last vertex of every other set CiC_i precedes it, so that

a round is entangled if and only if some vertex of U\mathbf{U} precedes Vn−1V_{n-1},

that is, if and only if a summed vertex has at least two vertices of V\mathbf{V} above it. In Example 3.1, where Vn−1=CV_{n-1} = C, the round is entangled in the two orders in which XX precedes CC, and it is not entangled in the order A<C<X<B<YA < C < X < B < Y. 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 K\mathbf{K} other than VnV_n is the factor qhq_h that the previous call formed for that vertex, unchanged, and the factor of VnV_n absorbs the summation,

Q(Vn∣Cn)=∑U′qVn∏u∈U′qu,(6)Q(V_n \mid C_n) = \sum_{\mathbf{U}'} q_{V_n} \prod_{u \in\mathbf{U}'} q_u, \tag*{(6)}

where U′\mathbf{U}' is the set of the vertices of U\mathbf{U} that precede VnV_n.

(ii) In any round, the factor of a vertex ViV_i at which the round is not entangled is formed without any division, and reads

Q(Vi∣Ci)=∑Vℓ<h<Vi∏Vℓ<h≤Viqh,Q(V_i \mid C_i) = \sum_{V_\ell< h < V_i} \prod_{V_\ell< h \le V_i} q_h,

where hh runs over the vertices of U∪V\mathbf{U} \cup\mathbf{V} and VℓV_\ell is the last vertex of CiC_i, the lower bounds being dropped when CiC_i is empty.

The proof, a direct computation with (2), (3) and (5), is given in Appendix § 8. The factors qhq_h 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 Vi−1V_{i-1} and ViV_i of V\mathbf{V} that both belong to K\mathbf{K} 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 K\mathbf{K} 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 c1c_1, 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 P(Vi∣Ci)P(V_i \mid C_i) formed by c1c_1, 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 P(Y∣H^1,Z^1,H^2,Z^2,H^3,Z^3)P(Y \mid\hat{H}_1,\hat{Z}_1,\hat{H}_2,\hat{Z}_2,\hat{H}_3,\hat{Z}_3) on each of the two graphs of Figure 4, which give rise to the same trajectory. The root call has S=Y={Y}\mathbf{S}=\mathbf{Y}=\{Y\} 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 ⌊6/2⌋\lfloor6/2\rfloor allowed by Theorem 2.4. The first line 7 retains the c-component {H1,H2,Z2,H3,Z3,Y}\{H_1,H_2,Z_2,H_3,Z_3,Y\} of YY, so that Z1Z_1 becomes a fixed value, and the line 2 that follows sums out H1H_1, which reaches YY only through Z1Z_1. The second line 7 is a round with U={H1}\mathbf{U}=\{H_1\} and V={H2,Z2,H3,Z3,Y}\mathbf{V}=\{H_2,Z_2,H_3,Z_3,Y\}. It retains K={H2,H3,Z3,Y}\mathbf{K}=\{H_2,H_3,Z_3,Y\}, so that Z2Z_2 becomes a fixed value, and line 2 sums out H2H_2, which reaches YY only through Z2Z_2. The third line 7 is a round with U={H2}\mathbf{U}=\{H_2\}, V={H3,Z3,Y}\mathbf{V}=\{H_3,Z_3,Y\} and K={H3,Y}\mathbf{K}=\{H_3,Y\}, after which line 2 sums out H3H_3 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 H3<Z3<H2<Z2<H1<Z1<YH_3 < Z_3 < H_2 < Z_2 < H_1 < Z_1 < Y, in which the first line 7 forms the six terms

P(H3),P(Z3∣H3),P(H2∣H3,Z3),P(Z2∣H2),P(H1∣H3,Z3,H2,Z2),P(Y∣H3,Z3,H2,Z2,H1,Z1).P(H_3),\quad P(Z_3 \mid H_3),\quad P(H_2 \mid H_3,Z_3),\quad P(Z_2 \mid H_2),\quad P(H_1 \mid H_3,Z_3,H_2,Z_2),\quad P(Y \mid H_3,Z_3,H_2,Z_2,H_1,Z_1).

In the first round H1H_1 lies above Z2Z_2, the last but one vertex of V\mathbf{V}, so that the round is not entangled. By Proposition 3.4(i) the factors of H3H_3, Z3Z_3 and H2H_2 are their terms, and the factor of YY is, by (6), ∑H1P(H1∣H3,Z3,H2,Z2)P(Y∣H3,Z3,H2,Z2,H1,Z1)\sum_{H_1} P(H_1 \mid H_3,Z_3,H_2,Z_2)P(Y \mid H_3,Z_3,H_2,Z_2,H_1,Z_1). 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 Z1→H2Z_1 \to H_2 and Z2→H3Z_2 \to H_3.

lies above Z3Z_3, so that this round is not entangled either, the factor of H3H_3 is again P(H3)P(H_3), and the factor of YY is

∑H2P(H2∣H3,Z3)∑H1P(H1∣H3,Z3,H2,Z2)P(Y∣H3,Z3,H2,Z2,H1,Z1)=∑H1,H2P(H2∣H3,Z3)P(H1∣H3,Z3,H2,Z2)P(Y∣H3,Z3,H2,Z2,H1,Z1).\sum_{H_2} P(H_2 \mid H_3,Z_3) \sum_{H_1} P(H_1 \mid H_3,Z_3,H_2,Z_2) P(Y \mid H_3,Z_3,H_2,Z_2,H_1,Z_1) = \sum_{H_1,H_2} P(H_2 \mid H_3,Z_3) P(H_1 \mid H_3,Z_3,H_2,Z_2) P(Y \mid H_3,Z_3,H_2,Z_2,H_1,Z_1).

where the two summations merge because H1H_1, which lies above H2H_2, does not occur in the term of H2H_2. The summation over H3H_3 merges with them for the same reason, and line 1 returns

P(Y∣H^1,Z^1,H^2,Z^2,H^3,Z^3)=∑H1,H2,H3P(H3)P(H2∣H3,Z3)P(H1∣H3,Z3,H2,Z2)P(Y∣H1,Z1,H2,Z2,H3,Z3)(7)P(Y \mid\hat{H}_1,\hat{Z}_1,\hat{H}_2,\hat{Z}_2,\hat{H}_3,\hat{Z}_3) = \sum_{H_1,H_2,H_3} P(H_3) P(H_2 \mid H_3,Z_3) P(H_1 \mid H_3,Z_3,H_2,Z_2) P(Y \mid H_1,Z_1,H_2,Z_2,H_3,Z_3) \tag*{(7)}

a single summation over a product of four of the six terms, the terms of Z2Z_2 and Z3Z_3 having left the product together with their heads.

Graph (b). The two additional edges leave a single topological order, H1<Z1<H2<Z2<H3<Z3<YH_1 < Z_1 < H_2 < Z_2 < H_3 < Z_3 < Y. In it H1H_1 precedes every vertex of the first round and H2H_2 every vertex of the second, so that both rounds are entangled. The first line 7 forms the six terms

f1=P(H1),f2=P(H2∣H1,Z1),f3=P(Z2∣H1,Z1,H2),f4=P(H3∣H1,Z1,H2,Z2),f_1 = P(H_1), \qquad f_2 = P(H_2 \mid H_1,Z_1), \qquad f_3 = P(Z_2 \mid H_1,Z_1,H_2), \qquad f_4 = P(H_3 \mid H_1,Z_1,H_2,Z_2),
f5=P(Z3∣H1,Z1,H2,Z2,H3),f6=P(Y∣H1,Z1,H2,Z2,H3,Z3).f_5 = P(Z_3 \mid H_1,Z_1,H_2,Z_2,H_3), \qquad f_6 = P(Y \mid H_1,Z_1,H_2,Z_2,H_3,Z_3).

By (5), the sums of the first round on the prefixes ending at H2H_2, Z2Z_2, H3H_3, Z3Z_3 and YY are A2,…,A6A_2,\ldots,A_6, where Ak=∑H1f1⋯fkA_k = \sum_{H_1} f_1 \cdots f_k, and its factors are A2A_2 for H2H_2, A4/A3A_4/A_3 for H3H_3, A5/A4A_5/A_4 for Z3Z_3 and A6/A5A_6/A_5 for YY. The last three telescope, as observed above (each numerator cancels the denominator of the next factor), and their product is A6/A3A_6/A_3. The sums of the second round on the prefixes ending at H3H_3, Z3Z_3 and YY are then B1B_1, B2B_2 and B3B_3, where Bj=∑H2A2Aj+3/A3B_j = \sum_{H_2} A_2 A_{j+3}/A_3, its factors are B1B_1 for H3H_3 and B3/B2B_3/B_2 for YY, and the output is

P(Y∣H^1,Z^1,H^2,Z^2,H^3,Z^3)=∑H3B1B3B2,Bj=∑H2A2Aj+3A3,Ak=∑H1f1⋯fk.(8)P(Y \mid\hat{H}_1,\hat{Z}_1,\hat{H}_2,\hat{Z}_2,\hat{H}_3,\hat{Z}_3) = \sum_{H_3} \frac{B_1 B_3}{B_2}, \qquad B_j = \sum_{H_2} \frac{A_2 A_{j+3}}{A_3}, \qquad A_k = \sum_{H_1} f_1 \cdots f_k. \tag*{(8)}

Three summations are nested, and the ratios contain ratios, where (7) has a single summation and no ratio. None of the sums AkA_k is a marginal of PP, because the product lacks the term P(Z1∣H1)P(Z_1 \mid H_1) of the fixed value Z1Z_1, which depends on H1H_1. Adding further pairs HkH_k, ZkZ_k, connected to their neighbours and to YY as in graph (b), gives for every mm the trajectory (7,2)m,1(7,2)^m,1, whose m−1m-1 rounds are all entangled, and an output with mm nested summations and m−1m-1 nested ratios.

Entanglement from the graph

Whether a round is entangled depends on the topological order π\pi, while the sets UU and VV of Definition 3.2, like the outcome set YY of the round and the graph G0G_0 of the query, are the same in every order. As we have seen, a round is not entangled in π\pi exactly when every vertex of VV other than the last one precedes every vertex of UU. An order with this property may or may not exist, and the following theorem decides the matter from UU, VV, YY and ancestry in G0G_0.

Theorem 3.6 (Entanglement from the graph). Consider a round with sets UU and VV and with outcome set YY, and let z∈Yz \in Y be one of its outcomes.

(i) Some topological order of G0G_0 leaves the round unentangled, with zz as the last outcome in this order, if and only if neither zz nor any vertex of UU is an ancestor in G0G_0 of a vertex of VV other than $z.

(ii) A single topological order of G0G_0 leaves all the rounds of the trajectory unentangled, with zz as the last outcome in this order, if and only if the condition of (i) holds at every round.

Since the last vertex of VV 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 YY there is no choice, and the condition is that no vertex of UU be an ancestor in G0G_0 of a vertex of VV other than YY. 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 VV other than zz together with all their ancestors in G0G_0, and then the remaining vertices, among which are zz and the vertices of UU (for several rounds, whose sets VV 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 U={X}U = \{X\} and V={A,C,Y}V = \{A, C, Y\}. There the vertex XX is an ancestor of BB and of YY only, the condition holds, and the order that lists AA and CC first is A<C<X<B<YA < C < X < B < Y. In graph (a) of Example 3.5, H1H_1 is an ancestor of Z1Z_1 and YY only and H2H_2 of Z2Z_2 and YY only, so that the condition holds at both rounds with z=Yz = Y; the construction lists H3H_3 and Z3Z_3, then H2H_2 and Z2Z_2, then the remaining vertices, and gives the order used in the example. In graph (b), H1H_1 is an ancestor of H2H_2, through Z1Z_1, and H2H_2 is an ancestor of H3H_3, through Z2Z_2, 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 uu 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 G0G_0 from uu 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 Z1Z_1 and Z2Z_2 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 Z1→H2Z_1 \to H_2 is added to graph (a), the first round is entangled in every order, because H1H_1 becomes an ancestor of H2H_2, while the second is not entangled in the order H3<Z3<H1<Z1<H2<Z2<YH_3 < Z_3 < H_1 < Z_1 < H_2 < Z_2 < Y. If only Z2→H3Z_2 \to H_3 is added, it is the second round that is entangled in every order, while the first is not entangled in the order H2<Z2<H3<Z3<H1<Z1<YH_2 < Z_2 < H_3 < Z_3 < H_1 < Z_1 < Y. The reason is that the tests of two successive rounds concern different paths. At a round with sets UU and VV, the test asks whether a directed path of G0G_0 leads from UU into V∖{z}V \setminus\{z\}. The vertices summed out before the next round belong to V∖{z}V \setminus\{z\} themselves, as do the vertices that the next round retains, so that the next test asks about paths between two parts of V∖{z}V \setminus\{z\}, 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 qhq_h 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 AA and retains a vertex BB, while another sums out BB and retains AA, since the first then needs BB to precede AA 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 A<X<C<B<YA < X < C < B < Y, they can, since the terms of the denominator join into P(A,X,C)P(A, X, C), and the denominator becomes ∑XP(A,X,C)=P(A,C)\sum_{X} P(A, X, C) = P(A, C). 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 K\mathbf{K}, has the form

ND,N=∑AF,D=∑A∪BF,(9)\frac{N}{D}, \qquad N = \sum_{\mathbf{A}} F, \qquad D = \sum_{\mathbf{A}\cup\mathbf{B}} F, \tag*{(9)}

where FF is a product of factors, A\mathbf{A} is a set of summed vertices and B\mathbf{B} is the set of the heads that are free in NN and summed in DD. We consider simplifications of DD 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 ss from a joint distribution P(H∣C)P(\mathbf{H} \mid\mathbf{C}) of which it is one of the heads, replacing it by P(H∖{s}∣C)P(\mathbf{H}\setminus\{s\} \mid\mathbf{C}), when ss 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 ss 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 NN and DD be as in (9), where FF is a product of terms, some of which may be divisors. If rearrangements and summations remove all the summations of DD, the ratio N/DN/D equals a formula without quotient,

ND=∑A∏e∈A∪BP(e∣Ce),\frac{N}{D} = \sum_{\mathbf{A}} \prod_{e\in\mathbf{A}\cup\mathbf{B}} P(e \mid C_e),

with one term, for a suitable set CeC_e, for each variable summed out of DD. More generally, if these steps bring DD to the form ∑RF′\sum_{\mathbf{R}} F', where F′F' is a product of terms, then N=∑AF′∏e∈EP(e∣Ce)N = \sum_{\mathbf{A}} F' \prod_{e\in\mathbf{E}} P(e \mid C_e) with E=(A∪B)∖R\mathbf{E} = (\mathbf{A}\cup\mathbf{B})\setminus\mathbf{R}, and every factor of F′F' that does not involve R\mathbf{R} cancels from N/DN/D.

In the proof, given in Appendix § 8, the chain rule sets aside one term for each variable that is summed out of DD. To see the theorem at work, take the ratio Q(Y∣A,C)Q(Y \mid A,C) of Example 3.1 in the order A<X<C<B<YA < X < C < B < Y, for which F=P(A)P(X∣A)P(C∣A,X)P(Y∣A,X,C,B)F = P(A)P(X \mid A)P(C \mid A,X)P(Y \mid A,X,C,B), A={X}\mathbf{A} = \{X\} and B={Y}\mathbf{B} = \{Y\}. The denominator D=∑X,YFD = \sum_{X,Y} F is simplified in three steps: a summation over YY removes the term of YY, a rearrangement joins the three remaining terms into P(A,X,C)P(A,X,C) by the chain rule, and a summation over XX leaves D=P(A,C)D = P(A,C), without summation. The replay sets aside one term at each summation, P(Y∣A,X,C,B)P(Y \mid A,X,C,B) at the first and P(X∣A,C)P(X \mid A,C) at the second, and the theorem gives

ND=∑XP(X∣A,C)P(Y∣A,X,C,B),\frac{N}{D} = \sum_{X} P(X \mid A,C)P(Y \mid A,X,C,B),

which is the factor that ID forms directly in the order A<C<X<B<YA < C < X < B < Y. In the term P(X∣A,C)P(X \mid A,C) the condition CC follows the head XX in the order of the computation; in general the terms P(e∣Ce)P(e \mid C_e) 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 P(Vi∣Ci)P(V_i \mid C_i) 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 P(Vi∣Ci)P(V_i \mid C_i) 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 +1+1 for every term of which it is the head and −1-1 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 ViV_i has weight 1 in ViV_i 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 Z1Z_1 is never a head and has weight 0. In every AkA_k, the variable H1H_1 is the head of f1f_1 and is summed once, which gives 1−1=01-1=0, while each of the other heads of f2,…,fkf_2,\ldots,f_k counts +1+1. The two tables below count the remaining variables, first in B3=∑H2A2A6/A3B_3 = \sum_{H_2} A_2 A_6/A_3 and then in the output ∑H3B1B3/B2\sum_{H_3} B_1 B_3/B_2.

in B3B_3H2H_2Z2Z_2H3H_3Z3Z_3YY
A2A_2+1+10000
A6A_6+1+1+1+1+1+1+1+1+1+1
1/A31/A_3−1-1−1-1000
∑H2\sum_{H_2}−1-10000
weight00111

Table 2.

in the outputH3H_3Z3Z_3YY
B1B_1+1+100
B3B_3+1+1+1+1+1+1
1/B21/B_2−1-1−1-10
∑H3\sum_{H_3}−1-100
weight001

Table 3.

The rows of B1B_1 and B2B_2 in the second table are obtained as in the first, with A4A_4 and A5A_5 in the place of A6A_6. The variable H2H_2 is the head of three factors of B3B_3, two in the numerator and one in the denominator, and is summed once, which gives 1+1−1−1=01+1-1-1=0. The outcome YY 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

d(P(V∣C))=0,d(E1E2)=d(E1/E2)=max⁡{d(E1),d(E2)},d(∑ME)=d(E)+1,d(P(V \mid C)) = 0,\quad d(E_1E_2) = d(E_1/E_2) = \max\{d(E_1),d(E_2)\},\quad d\left(\sum_{\mathrm{M}} E\right) = d(E) + 1,

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 GG and are not renamed, so that a factor E′E' standing beside ∑ME\sum_{\mathrm{M}} E can be moved inside the summation only if no variable of M\mathrm{M} occurs in E′E', not even as a fixed value. In (1), P(Z∣X)P(Z \mid X) contains the intervened variable XX, 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 ee be the largest number of entangled rounds on a trajectory of the query, and mm the largest length of a tail. The output has depth at most 1+e1 + e if line 4 is not executed and at most 2+e2 + e if it is, and in both cases at most 1+m1 + m.

The proof is given in Appendix A, and it follows at once from the theorem that an output of depth three or more requires e≥1e \ge1 and m≥2m \ge2, that is, an entangled round and a tail of at least two repetitions, which in turn requires an intervention set X0X_0 of at least four vertices at the beginning of the tail (Theorem 2.4). The bounds 2+e2 + e and 1+m1 + m are attained by the front-door formula (1), in which line 4 is executed, e=0e = 0 and m=1m = 1, and the bound 1+e1 + e by graph (b) of Example 3.5 and its extensions, in which line 4 is not executed and the depth is mm with e=m−1e = m - 1. Graph (a) of the same example, with the same trajectory and no entangled round, gives depth one. In Example 3.1 the branch for YY has depth one in the order A<C<X<B<YA < C < X < B < Y and depth two in the order A<X<C<B<YA < X < C < B < Y, where the summation over AA is placed over a ratio.

The number ee 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 ∑SL∏kFk\sum_{S_L}\prod_k F_k, with one factor FkF_k for each branch of line 4, or a single factor if line 4 is not executed. Without entangled rounds, each FkF_k 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 S′=V′∖X′S' = V' \setminus X' is the live set of the child and G′=G[V′]G' = G[V'] its graph.

Proof of Lemma 2.1. A directed path of GXˉG_{\bar{X}} that starts outside XX contains no vertex of XX, because each of its later vertices is entered by an edge of the path, and GXˉG_{\bar{X}} has no edge entering XX. The test of line 3 fails when every vertex of SS is an ancestor of YY in GXˉG_{\bar{X}}. If (A) holds, the path that it provides for a vertex v∈Sv \in S lies in SS, hence outside XX, so that it is also a path of GXˉG_{\bar{X}} and makes vv an ancestor of YY there; the test then fails. If, on the other hand, the test fails, every v∈Sv \in S has a directed path to YY in GXˉG_{\bar{X}}. This path avoids XX by the remark above, so that it lies in SS, and it is a path of GG, since GXˉG_{\bar{X}} is GG 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 GX‾G_{\overline{X}} if and only if it has a directed path to Y inside SS. 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 SS contains Y and is not empty, so that G[S]G[S] 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, V′=An(Y)GV' = An(Y)_G and X′=X∩V′X' = X \cap V', so that S′=V′∖X′=S∩V′=SS' = V' \setminus X' = S \cap V' = S, because S⊆V′S \subseteq V'). 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 S+S^+, which are all intervened, because S⊆S+S \subseteq S^+. 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 ii-th child has the graph GG, the outcome set Y′=Si' = S_i and the intervention set V∖SiV \setminus S_i, so that S′=Si=S' = S_i =Y′' and the child is saturated. Condition (A) then holds through paths of length zero, and (B) holds because the vertices of SiS_i, a c-component of G[S]G[S], are connected by bidirected paths inside SiS_i.

Line 3. The child has the graph GG, the outcome set Y and the intervention set X∪WX \cup W, so that S′=S∖WS' = S \setminus W consists of the vertices of SS that are ancestors of Y in GX‾G_{\overline{X}}. A directed path from v∈S′v \in S' to Y in GX‾G_{\overline{X}} avoids XX, 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 S′S'. Each vertex of S′S' thus reaches Y along a path that lies in S′S', 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 G[S]G[S] has a single c-component, G[S′]G[S'] may have several, because the bidirected paths that connected the vertices of S′S' may have passed through the removed set WW. 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 An(Y)GAn(Y)_G, 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 X′⊇W≠∅X' \supseteq W \ne\varnothing, and of a line 4, where X′=V∖Si⊇X≠∅X' = V \setminus S_i \supseteq X \ne\varnothing. The same holds for the child of a line 7, whose intervention set X′=X∩S+X' = X \cap S^+ consists of the vertices of S+S^+ outside SS and is never empty, because line 7 is executed only when SS is a proper subset of S+S^+. 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 S+S^+ 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 ∅\varnothing, 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 mm, the line 7 of a repetition deletes the set V∖S+V \setminus S^{+}, which is not empty, since otherwise the test of line 5 would have succeeded, and is contained in XX, since S⊆S+S \subseteq S^{+}. Its line 2 deletes the vertices of S+S^{+} that are not ancestors of YY in G[S+]G[S^{+}], 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 YY. The 2m2m sets deleted along the tail are disjoint subsets of X0X_{0}, so that 2m≤∣X0∣2m \leq|X_{0}|, with equality when they are single vertices that exhaust X0X_{0}, as in Example 3.5 (∣X0∣=6|X_{0}| = 6, m=3m = 3). □

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 SL\mathbf{S}_{L} remains to be proved. Let c∗c^{*} be the call at which the clean-up ends, that is, the first call after it, and S∗S^{*} 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 SL=S∗∖Y\mathbf{S}_{L} = S^{*} \setminus Y. Let D=An(Y)G0[V0∖X]\mathbf{D} = A_{n}(Y)_{G_{0}}[V_{0} \setminus X] be the set of the vertices from which YY can be reached by a directed path of G0G_{0}, the original graph, that avoids the intervention set XX of the query, the vertices of YY included. It suffices to prove that S∗=DS^{*} = \mathbf{D}, and we do so by following along the clean-up the set D(c)\mathbf{D}(c) defined as follows.

For any call cc, we say that a live vertex is internal if it has a directed path to YY inside the live set, and external otherwise, and we write D(c)\mathbf{D}(c) for the set of the internal vertices of cc. By the fact noted in the proof of Lemma 2.1, the internal vertices are the live vertices that are ancestors of YY in GXG_{X}, and condition (A) says that no live vertex is external. At the root, D(c)=D\mathbf{D}(c) = \mathbf{D} by the definition of D\mathbf{D}, since the live set of the root is V0∖XV_{0} \setminus X.

Neither line of the clean-up changes D(c)\mathbf{D}(c). Line 2 deletes only vertices that are not ancestors of YY, whereas an internal vertex, like every vertex of the path that makes it internal, is an ancestor of YY; 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 D(c)\mathbf{D}(c); 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 c∗c^{*} 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, c∗c^{*} 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, c∗c^{*} 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 c∗c^* executes line 1, and all its vertices are live and are ancestors of YY, hence internal. In every case the live set S∗S^* of c∗c^* is D(c∗)\mathrm{D}(c^*), which equals D\mathrm{D} because D(c)\mathrm{D}(c) has not changed along the clean-up.

Proof of Proposition 3.4. (i) If the round is not entangled, every vertex of U\mathbf{U} lies above Vn−1V_{n-1}. For i<ni<n the sum (5) then contains no vertex of U\mathbf{U} and reads Q[V(i)]=qV1⋯qViQ[\mathbf{V}^{(i)}]=q_{V_1}\cdots q_{V_i}, so that the ratio (2) is qViq_{V_i}. For i=ni=n, the heads up to VnV_n are V1,…,VnV_1,\ldots,V_n and the vertices of U′U', so that

Q[V(n)]=∑U′qV1⋯qVn−1qVn∏u∈U′qu.Q[\mathbf{V}^{(n)}]=\sum_{U'}q_{V_1}\cdots q_{V_{n-1}}q_{V_n}\prod_{u\in U'}q_u.

The factors qV1,…,qVn−1q_{V_1},\ldots,q_{V_{n-1}} involve only variables up to Vn−1V_{n-1}, hence no vertex of U′U', and can be taken out of the summation. Their product is Q[V(n−1)]>0Q[\mathbf{V}^{(n-1)}]>0, and dividing by it leaves (6).

(ii) Suppose first that CiC_i is not empty. Since the round is not entangled at ViV_i, no vertex of U\mathbf{U} precedes VℓV_\ell, so that the sum (5) for the prefix V(ℓ)\mathbf{V}^{(\ell)} is the plain product ∏h≤Vℓqh\prod_{h\le V_\ell}q_h, and this is the denominator of (3). In the numerator of (3), Q[V(i)]Q[\mathbf{V}^{(i)}] is given by (5) as a sum over the vertices of U\mathbf{U} below ViV_i, and (3) sums it further over Vℓ+1,…,Vi−1V_{\ell+1},\ldots,V_{i-1}; together these are all the vertices hh of U∪V\mathbf{U}\cup\mathbf{V} with Vℓ<h<ViV_\ell<h<V_i, since no vertex of U\mathbf{U} lies below VℓV_\ell. The factors qhq_h with h≤Vℓh\le V_\ell involve only variables up to VℓV_\ell, 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 CiC_i is empty, (3) has no denominator. Its numerator sums Q[V(i)]Q[\mathbf{V}^{(i)}] over V1,…,Vi−1V_1,\ldots,V_{i-1}, and by (5) Q[V(i)]Q[\mathbf{V}^{(i)}] is itself the sum, over the vertices of U\mathbf{U} below ViV_i, of the product of all the factors qhq_h with h≤Vih\le V_i. The two summations together run over all the vertices h<Vih<V_i of U∪V\mathbf{U}\cup\mathbf{V}, which gives the expression of the statement without its lower bounds.

Proof of Theorem 3.6. We write An⁡(W)\operatorname{An}(\mathbf{W}) for the set of the vertices from which a directed path of G0G_0, possibly of length zero, leads to a vertex of W\mathbf{W}. The proof uses two facts. First, An⁡(W)\operatorname{An}(\mathbf{W}) contains every parent of each of its vertices, that is, if b∈An⁡(W)b\in\operatorname{An}(\mathbf{W}) and a→ba\to b is an edge of G0G_0, then a∈An⁡(W)a\in\operatorname{An}(\mathbf{W}). Second, as shown after Definition 3.3, a round is not entangled in an order π\pi if and only if every vertex of V\mathbf{V} other than the last one precedes every vertex of U\mathbf{U} in π\pi; moreover the last vertex of V\mathbf{V} is an outcome, and hence the last of the outcomes, since V\mathbf{V} contains Y\mathbf{Y}.

(i) Suppose that the round is not entangled in a topological order π\pi in which zz is the last outcome. By the second fact zz is the last vertex of V\mathbf{V}, so that every vertex vv of V∖{z}\mathbf{V}\setminus\{z\} precedes zz, and it precedes every vertex of U\mathbf{U}. On the other hand, a directed path of G0G_0 from a vertex xx to vv forces x<vx<v, because every edge of G0G_0 goes from an earlier to a later vertex of π\pi. No such path can therefore start at zz or at a vertex of U\mathbf{U}, which is the condition of the statement.

Conversely, suppose that zz satisfies the condition, and let A=An⁡(V∖{z})\mathbf{A}=\operatorname{An}(\mathbf{V}\setminus\{z\}). The condition says precisely that A\mathbf{A} contains neither zz nor any vertex of U\mathbf{U}. We build π\pi in two blocks, listing first the vertices of A\mathbf{A} (which are thus the earliest vertices of π\pi), in a topological order of the subgraph that they induce, and then all the other vertices, among which are zz and the vertices of U\mathbf{U}, in a topological order of theirs. The result is a topological order of G0G_0, because an edge between two vertices of the same block is respected by construction, and an edge a→ba\to b between the blocks cannot lead from the second block to the first, since b∈Ab\in\mathbf{A} would imply a∈Aa\in\mathbf{A}. In this order every vertex of V∖{z}\mathbf{V}\setminus\{z\}, which lies in the first block, precedes zz and all the vertices of U\mathbf{U}, which lie in the second. Hence zz is the last vertex of V\mathbf{V}, and therefore the last outcome, the other vertices of V\mathbf{V} precede those of U\mathbf{U}, and the round is not entangled.

With a single outcome YY, the vertex zz can only be YY. Every other vertex of V\mathbf{V} is an ancestor of YY in the graph of the round, hence in G0G_0, and a directed path from YY to one of them would close a directed cycle, so that the part of the condition that concerns zz holds automatically.

(ii) Let Us\mathbf{U}_s and Vs\mathbf{V}_s be the sets of the rounds csc_s, for $2\le s\le t$. The vertices of a round are among those of the previous round, when there is one, so that Vt⊆⋯⊆V2\mathbf{V}_t\subseteq\cdots\subseteq\mathbf{V}_2, and every $\mathbf{V}_s contains YY. If a single order leaves all the rounds unentangled with zz as the last outcome, then zz is the last vertex of every Vs\mathbf{V}_s, 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 As=An⁡(Vs∖{z})\mathbf{A}_s = \operatorname{An}(\mathbf{V}_s \setminus\{z\}), so that At⊆⋯⊆A2\mathbf{A}_t \subseteq\cdots\subseteq\mathbf{A}_2. We now build π\pi in tt blocks, listing first the vertices of At\mathbf{A}_t (the earliest of π\pi), then those of At−1∖At\mathbf{A}_{t-1} \setminus\mathbf{A}_t, and so on up to A2∖A3\mathbf{A}_2 \setminus\mathbf{A}_3, and finally the vertices outside A2\mathbf{A}_2, each block in a topological order of the subgraph that it induces. As before, an edge a→ba \to b cannot lead from a later block to an earlier one, because bb then belongs to a set As\mathbf{A}_s that does not contain aa, whereas As\mathbf{A}_s contains every parent of bb. The result is therefore a topological order of G0G_0. For every ss, the vertices of Vs∖{z}\mathbf{V}_s \setminus\{z\} lie in As\mathbf{A}_s, whereas zz and the vertices of Us\mathbf{U}_s lie outside As\mathbf{A}_s by the condition, and are listed after all the vertices of As\mathbf{A}_s. More precisely, zz lies outside every As\mathbf{A}_s, hence in the last block. The vertices of Us\mathbf{U}_s lie in the block As−1∖As\mathbf{A}_{s-1} \setminus\mathbf{A}_s if s≥3s \ge3 (they are vertices of Vs−1\mathbf{V}_{s-1} other than zz, hence belong to As−1\mathbf{A}_{s-1}, and they lie outside As\mathbf{A}_s), and in the last block if s=2s = 2. Every round is therefore not entangled in this order, and zz is its last outcome. On graph (a) of Example 3.5, for instance, where z=Yz = Y and t=3t = 3, the blocks are A3={H3,Z3}\mathbf{A}_3 = \{H_3, Z_3\}, A2∖A3={H2,Z2}\mathbf{A}_2 \setminus\mathbf{A}_3 = \{H_2, Z_2\} and {H1,Z1,Y}\{H_1, Z_1, Y\}, and listing them in turn gives the order used there. □\square

Proof of Theorem 4.1. We prove the general statement, of which the first is the case R=∅\mathbf{R} = \varnothing, where F′F' does not involve R\mathbf{R} and cancels entirely. We follow the steps of the simplification of DD, writing FkF_k for its product after kk steps, and we maintain an identity F=FkLkF = F_k L_k, valid for all values of the variables, in which LkL_k is a product of one term P(e∣⋅)P(e \mid\cdot) for each variable ee summed out so far, none of which occurs in FkF_k. Initially F0=FF_0 = F and L0=1L_0 = 1. A rearrangement replaces FkF_k by an expression Fk+1F_{k+1} equal to it for all values, and LkL_k is kept. A summation replaces a joint distribution P(H∣C)P(\mathbf{H} \mid\mathbf{C}) of FkF_k, where H\mathbf{H} is the set of the heads joined in it, by P(H∖{s}∣C)P(\mathbf{H} \setminus\{s\} \mid\mathbf{C}). By the chain rule, which requires no condition, P(H∣C)=P(H∖{s}∣C)P(s∣H∖{s},C)P(\mathbf{H} \mid\mathbf{C}) = P(\mathbf{H} \setminus\{s\} \mid\mathbf{C}) P(s \mid\mathbf{H} \setminus\{s\}, \mathbf{C}), so that Fk=Fk+1P(s∣H∖{s},C)F_k = F_{k+1} P(s \mid\mathbf{H} \setminus\{s\}, \mathbf{C}), and the last term is appended to LkL_k. After this step ss no longer occurs in Fk+1F_{k+1}, and later steps do not reintroduce it. At the end F=F′LF = F'L for all values of the variables, where LL is the product of the terms set aside, one for each variable of EE, whence N=∑AF′LN = \sum_{\mathbf{A}} F'L. A factor of F′F' that does not involve R\mathbf{R} involves no variable of A\mathbf{A} either, because the variables of A\mathbf{A} outside R\mathbf{R} have been summed out of DD and do not occur in F′F'; such a factor can therefore be taken out of both summations and cancelled. □\square

Proof of Theorem 5.1. Fix a trajectory, and let c1,…,ctc_1, \ldots, c_t be its calls that execute line 6 or line 7, as in Definition 3.2, so that c2,…,ctc_2, \ldots, c_t are its rounds. We call sum over csc_s a summation, possibly over the empty set, of a product of factors formed by csc_s, and we write DsD_s for the largest depth of such an expression. The factors of c1c_1 are terms, of depth zero, and a summation of a product of terms has depth one, so that D1=1D_1 = 1.

For s≥2s \ge2, by (2) and (5) every factor of the round csc_s is a sum over cs−1c_{s-1} or the ratio of two of them, both of which have depth at most Ds−1D_{s-1}, and a sum over csc_s places one more summation on a product of such factors. A round thus adds at most one level, that is, Ds≤Ds−1+1D_s \le D_{s-1} + 1. If the round csc_s is not entangled, it adds none, and the bound improves to Ds≤Ds−1D_s \le D_{s-1}. Indeed, by Proposition 3.4(i) the factors of csc_s are those of cs−1c_{s-1}, except for the factor (6) of the last vertex VnV_n, which carries a summation over U′\mathbf{U}'. The vertices of U′\mathbf{U}' lie above every vertex of the round other than VnV_n, and the factor of a vertex involves only variables up to that vertex, so that they do not occur in the other factors of csc_s. In a sum over csc_s, the summation over U′\mathbf{U}' 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 cs−1c_{s-1}. Since D1=1D_1 = 1, it follows that DsD_s is at most one plus the number of entangled rounds among c2,…,csc_2, \ldots, c_s, so that Dt≤1+eD_t \le1 + e, and that Ds≤sD_s \le s for every ss.

Suppose first that line 4 is not executed. The output is then a sum over ctc_t, since the exit sums the product of the factors of ctc_t over SLS_L at line 6, and over SL∪US_L \cup\mathbf{U} at line 1, where U\mathbf{U} is the set summed out by the line 2 that precedes it (if t=0t = 0, the exit must be line 1, which returns a marginal of PP, of depth zero). Its depth is therefore at most Dt≤1+eD_t \le1 + e. This is also at most 1+m1 + m, because a tail of mm repetitions contains at most mm rounds, so that e≤me \le m.

Suppose now that line 4 is executed. Each branch returns an expression of depth at most 1+e1 + e, as we have just seen, and line 4 sums the product of these expressions, which adds at most one level and gives 2+e2 + e. For the bound 1+m1 + m 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 r≤mr \le m repetitions. If it exits at line 6, it returns the product of the factors of cr+1c_{r+1}, without any summation, and each of these factors has depth at most DrD_r. If it exits at line 1, it returns a sum over crc_r, of depth at most DrD_r. In both cases the depth is at most Dr≤r≤mD_r \le r \le m (and zero if r=0r = 0, where the branch returns terms or a marginal of PP), and the summation of line 4 brings it to at most 1+m1 + m.

References

  1. [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. [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. [3]J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–688, 1995. doi:10.1093/biomet/82.4.669.DOI
  4. [4]M. Pedemonte, J. Vitrià, and Á. Parafita. Algorithmic causal effect identification with causaleffect. arXiv:2107.04632, 2021.arxiv.org/abs/2107.04632
  5. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

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

views · 1

downloads · 0

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

  • Mathematics

Claude

View statement
Looking for related papers…
Contents