Additive-noise causal discovery and identifiability

Suppose $a\mathrm{\ne }0$ and put $\mathrm{\ell }=\mathrm{\mid }a\mathrm{\mid }>0$. Invariance under translation by $a$ implies invariance under translation by $\mathrm{\ell }$: when $a=-\mathrm{\ell }$, apply the given identity to $A+\mathrm{\ell }$. The half-open intervals $I_k=[k\mathrm{\ell },(k+1)\mathrm{\ell })$, $k\in \mathbb{Z}$, partition $\mathbb{R}$ and are translates of $I_0$, so they all have the same measure $c=\mu (I_0)$.

If $c>0$, choose a natural $n>1\mathrm{/}c$ by [F3]. The first $n$ intervals are disjoint, so finite additivity gives $1\ge \mu ({\bigcup }_{k=0}^{n-1}{I}_k)=nc>1$, a contradiction. Hence $c=0$.

Countable additivity over the partition $(I_k{)}_{k\in \mathbb{Z}}$ now gives $1=\mu (\mathbb{R})={\sum }_{k\in \mathbb{Z}}\mu (I_k)=0$, again a contradiction. Therefore $a=0$.

The coordinate change $(y,c)\mapsto (r,c)=(y-m(c),c)$ is a translation in each fixed $c$-section. By [F1] and iterated integration [F3], the law of $(R,C)$ has density $h(r,c)=p(r+m(c),c)$. Since $p$ and $m$ are $C^3$ and $p>0$, $h$ is a strictly positive $C^3$ function.

Independence and [F2] make the law with density $h(r,c)$ from step 1.1 the product of the marginal laws of $R$ and $C$. Tonelli [F3] gives marginal density versions, and therefore $h(r,c)=q_R(r)p_C(c)$ almost everywhere. Choose $c_0$ for which $0<p_C(c_0)<\mathrm{\infty }$ and this equality holds for almost every $r$. Then $q_R(r)=h(r,c_0)\mathrm{/}{p}_C(c_0)$ almost everywhere, so this formula supplies a strictly positive $C^3$ version of $q_R$.

By Fubini choose $r_0$ with $q_R(r_0)>0$ such that $h(r_0,c)=q_R(r_0)p_C(c)$ for almost every $c$. Set $p_C^{\ast }(c)=h(r_0,c)\mathrm{/}{q}_R(r_0)$. This is a strictly positive $C^3$ function and equals $p_C$ almost everywhere. Thus $h(r,c)=q_R(r)p_C^{\ast }(c)$ almost everywhere; both sides are continuous, so the equality holds everywhere.

Substituting $r=y-m(c)$ into step 3.1 yields $p(y,c)=q_R(y-m(c))p_C^{\ast }(c)$ for every $(y,c)$. Renaming $p_C^{\ast }$ as $p_C$ proves the Statement.

First suppose every $q_j$ is Borel measurable. For each $j$, let $Q_j=q_{j}d\lambda$ on Borel sets; [F1, F3] makes $Q_j$ a probability measure. The function $g(n)={\prod }_{r=1}^p{q}_{v_r}(n_{v_r})$ is Borel, hence product-measurable, by [F7, F8]. Repeated Tonelli gives $\int gd\rho =1$ and, on every Borel rectangle, ${\int }_{\prod B_j}gd\rho ={\prod }_j{Q}_j(B_j)$. Uniqueness of product measures identifies this Borel density measure with the joint law of the independent noises.

Recursion in topological order defines a Borel map $T:{\mathbb{R}}^p\to {\mathbb{R}}^p$ from the noise vector to $X$. Its inverse has coordinates $n_j=x_j-f_j(x_{\mathrm{pa}(j)})$, so the observational law is the Borel pushforward under $T$.

Start from step 1.1 and change one coordinate at a time in topological order. With earlier endogenous coordinates fixed, $x_{v_r}=n_{v_r}+f_{v_r}(x_{\mathrm{pa}(v_r)})$ is a fixed translation. Translation invariance changes its density factor to $q_{v_r}(x_{v_r}-f_{v_r}(x_{\mathrm{pa}(v_r)}))$. Every intermediate integrand for a nonnegative Borel test function is product-measurable by [F7, F8], so Tonelli justifies the successive one-dimensional substitutions. The resulting identity $\mathbb{E}[h(X)]=\int h(x)p_X(x)d\rho (x)$ for every nonnegative Borel $h$ proves the density assertion on Borel sets. The product is Borel and strictly positive. No choice principle was used in this case.

Now assume Countable Choice and allow arbitrary Lebesgue-measurable $q_j$. By [F9] choose Borel representatives, replace their values outside $(0,\mathrm{\infty })$ by $1$, and call the resulting functions ${\bar{q}}_j$. Since each original density is positive and finite almost everywhere, this changes it only on a null set and preserves its integral and noise law. Choose a Borel null hull $Z_j$ of $\{q_j\mathrm{\ne }{\bar{q}}_j\}$. These are only finitely many applications of [F9]. Step 2.1 applied to ${\bar{q}}_j$ gives the positive Borel density ${\bar{p}}_X$ relative to $\rho$.

For each $j$, let $E_j=\{x:x_j-f_j(x_{\mathrm{pa}(j)})\in Z_j\}$. It is Borel by [F8]. With all coordinates except $x_j$ fixed, its $x_j$-section is a translate of $Z_j$ and has measure zero by [F6]; for $p>1$, Tonelli gives $\rho (E_j)=0$, and for $p=1$ this follows directly from translation invariance. Off the finite union $E={\bigcup }_j{E}_j$, the products $p_X$ and ${\bar{p}}_X$ agree. Completeness [F10] therefore makes $p_X$ measurable for $\bar{\rho }$, with the same integral on every completed measurable set as ${\bar{p}}_X$. Every original factor is positive, proving strict positivity as well.

In the Countable Choice case, the density measures in steps 2.1 and 4.1 extend the Borel observational law. To see uniqueness among absolutely continuous extensions, first note that every product-measurable set differs from a Borel set by a subset of a Borel $\rho$-null set: the sets with this property form a sigma-algebra under Countable Choice and contain every Lebesgue rectangle by [F9]; Borel null coordinate slabs have product measure zero by Tonelli. A product-null set has a Borel null hull by the same representation, so every $\bar{\rho }$-measurable set has such a representation too. Any absolutely continuous extension assigns zero to the exceptional set and is determined by the Borel core. Thus the stated extensions and both density conclusions hold.

For each $k\in S$, define $A_k$ to be $k$ together with all vertices having a directed path to $k$, and put $A={\bigcup }_{k\in S}{A}_k$. In topological order, a root variable is a measurable function of its own noise; if this representation has been obtained for each parent of $k$, substituting those representations into $X_k=f_k(X_{\mathrm{pa}(k)})+N_k$ shows that $X_k$ is a measurable function of $(N_i{)}_{i\in A_k}$. Finite induction therefore makes $X_S$ a measurable function of $(N_i{)}_{i\in A}$. Since $S$ contains only nondescendants of $j$, no directed path goes from $j$ to a vertex of $S$, so $j\mathrm{\notin }A$.

The finite noise product law [F2] implies that $N_j$ is independent of the vector $(N_i{)}_{i\in A}$ because the two coordinate blocks are disjoint. Applying [F3] to the measurable map from that vector to $X_S$ from step 1.1 shows $N_j\perp X_S$. If $S=\mathrm{\varnothing }$, $X_S$ is the constant empty tuple and the same independence statement holds.

For Borel noise densities use the displayed product. Otherwise [F1] supplies positive finite Borel versions under the assumed Countable Choice; use their Borel product throughout the integrations below. It has the same observational law, and its marginal densities agree almost everywhere with the stipulated marginal versions, so the final almost-everywhere identity transfers to those versions. Put $H={\mathrm{An}}_G(A\cup B\cup C)$. No vertex outside $H$ is a parent of a vertex in $H$, since that would make it an ancestor of $A\cup B\cup C$. Integrate the product density [F1] over $V\setminus H$ in reverse topological order. At each elimination, all child factors have already been integrated and no child lies in $H$, so the only remaining factor involving the current coordinate $x_v$ is $q_v(x_v-f_v(x_{\mathrm{pa}(v)}))$. Its section integral is one by [F2]. Tonelli [F3] justifies each section integral; consequently the marginal density on $H$ is ${\prod }_{v\in H}{q}_v(x_v-f_v(x_{\mathrm{pa}(v)}))$.

By [F4], deleting $C$ from the moral graph on $H$ leaves no path from $A$ to $B$. Partition its connected components into $L$, the union of components meeting $A$, and $R$, the union of the remaining components. Then $A\subseteq L$, $B\subseteq R$, and there is no moral edge between $L$ and $R$. For each $v\in H$, the factor indexed by $v$ in step 1.1 depends only on $\{v\}\cup \mathrm{pa}(v)\subseteq H$; this set is a clique in that moral graph by [F5]. Hence no such factor involves both an $L$-coordinate and an $R$-coordinate. Assign factors involving an $L$-coordinate to $U$, and assign all other factors to $W$. Their finite products give a factorization of the density on $H$ as $U(x_L,x_C)W(x_R,x_C)$.

Integrate the factorization in step 2.1 over the hidden coordinates $L\setminus A$ and $R\setminus B$. Since the factors separate and are nonnegative, Tonelli [F3] yields measurable functions $u(x_A,x_C)$ and $w(x_B,x_C)$ such that $p_{A\cup B\cup C}(x_A,x_B,x_C)=u(x_A,x_C)w(x_B,x_C)$ almost everywhere. Each function is strictly positive because it integrates a strictly positive factor over its hidden coordinates; if that coordinate set is empty, it is the original strictly positive factor.

Define $\alpha (x_C)=\int u(x_A,x_C)d{x}_A$ and $\beta (x_C)=\int w(x_B,x_C)d{x}_B$. Tonelli makes these measurable and gives $p_{A\cup C}=u\beta$ and $p_{B\cup C}=w\alpha$ almost everywhere. Also $p_C(x_C)=\int u(x_A,x_C)w(x_B,x_C)d{x}_{A}d{x}_B$ for almost every $x_C$. The marginal $p_C$ is positive, since it integrates the everywhere-positive density over any unit box in the remaining coordinates, and it is finite almost everywhere since $\int p_C=1$. For almost every such $x_C$, strict positivity of $u,w$ gives $\alpha ,\beta >0$. If, for example, $\alpha =\mathrm{\infty }$, then $\beta >0$ supplies a set of $b$-values of positive measure where $w(b,x_C)>1\mathrm{/}n$ for some $n$, so Tonelli makes $\int u(a,x_C)w(b,x_C)dadb=\mathrm{\infty }$; the same argument applies if $\beta =\mathrm{\infty }$. Hence both integrals are finite almost everywhere, Tonelli factors the last integral as $p_C=\alpha \beta$, and multiplying the finite marginal identities gives the claimed conditional-density factorization.

Use the supplied Borel noise densities, or their positive finite Borel versions from [F2] under Countable Choice. Work with their Borel shifted-noise product and its integrated marginals; changing density versions does not change an almost-everywhere conditional-independence factorization. Every variable in $\{i\}\cup P\cup Q$ is a nondescendant of $j$. By [F3], $N_j$ is independent of the vector $(X_i,X_P,X_Q)$. Conditional on $(X_i=x,X_P=p,X_Q=q)$, the structural equation therefore gives the density $p_{X_j\mid X_i,X_P,X_Q}(y\mid x,p,q)=q_j(y-f_j(p,x))$ for almost every $(x,p,q,y)$. This density does not depend on $q$, so the joint conditional density of $(X_j,X_Q)$ given $(X_i,X_P)$ factors; hence $X_j{\perp }_d{X}_Q\mid (X_i,X_P)$.

Suppose, for contradiction, that $X_j{\perp }_d{X}_i\mid X_P$. Since $N_j$ is independent of the parent vector $(X_i,X_P)$, its conditional density is $q_j(y-f_j(p,x))$. The assumed factorization says this density is independent of $x$ for almost every $p$ and almost every $x$. The conditional density of $X_i$ given $X_P=p$ is positive for almost every $x$ at almost every $p$ with $0<p_P(p)<\mathrm{\infty }$, because the full joint density is strictly positive. Therefore, for almost every such $p$, for almost every pair $x,x^{\mathrm{\prime }}$, the two translates $q_j(y-f_j(p,x))$ and $q_j(y-f_j(p,x^{\mathrm{\prime }}))$ agree for almost every $y$.

A positive integrable density cannot have a nonzero period: if $q_j(y-a)=q_j(y-b)$ almost everywhere with $a\mathrm{\ne }b$, then $q_j$ repeats on every translate of an interval of length $\mathrm{\mid }a-b\mathrm{\mid }$; that interval has positive integral, so the integral over the disjoint translates is infinite, contradicting $\int q_j=1$. Thus step 1.2 forces $f_j(p,x)=f_j(p,x^{\mathrm{\prime }})$ for almost every pair $x,x^{\mathrm{\prime }}$ and almost every $p$. Continuity of $f_j$ extends this constancy to every setting of the other parent coordinates: any two unequal values would persist on open neighborhoods of positive Lebesgue measure. This contradicts [F1], so $X_j\mathrm{̸}{\perp }_d{X}_i\mid X_P$.

If $Q$ is empty, $S=P$ and step 2.1 is the required conclusion. Otherwise, suppose $X_j{\perp }_d{X}_i\mid X_{P,Q}$. By the conditional-density equality in step 1.1 and this supposition, for almost every $(p,y)$ one has $p_{X_j\mid X_i=x,X_P=p}(y)=p_{X_j\mid X_P=p,X_Q=q}(y)$ for almost every pair $(x,q)$. The left side depends only on $x$ and the right side only on $q$; by Fubini, each is therefore almost everywhere constant in its varying coordinate. Hence $X_j{\perp }_d{X}_i\mid X_P$, contradicting step 2.1. Thus the factorization given $X_S$ fails.

The Borel noise densities specified in the Statement give the Borel product [F2]; when necessary their versions are supplied under Countable Choice by that same result. Every shifted factor and every finite regrouping is Borel measurable. If $y$ were a parent of any $d\in D$, then $d$ would be another child of $y$ and also a descendant of $z$, contrary to the hypothesis. Thus no vertex in $D$ has $y$ as a parent. Every parent of a vertex in $D$ therefore lies in $D\cup \{z\}\cup S$.

No vertex in $D$ can be a parent of a vertex outside $D$: that would make the latter a descendant of $z$. Hence each density factor in [F2] for a vertex outside $D$ depends only on $(y,s,z)$, while each factor for a vertex in $D$ depends only on $(d,s,z)$. Regrouping the finite product gives $p(d,y,s,z)=A(y,s,z)B(d,s,z)$ for nonnegative measurable functions $A,B$.

By [F3], the marginal densities obtained from the full product are $p_{X_S,X_z}(s,z)=(\int A(y,s,z)dy)(\int B(d,s,z)dd),$ $p_{X_y,X_S,X_z}(y,s,z)=A(y,s,z)\int B(d,s,z)dd,p_{X_D,X_S,X_z}(d,s,z)=B(d,s,z)\int A(y,s,z)dy\mathrm{.}$ These identities hold almost everywhere where the marginal densities are finite; Tonelli also permits infinite values on exceptional null sets. Multiplying the last two identities and comparing with the first proves the factorization in the Statement almost everywhere. For any fixed $s$ with $0<p_{X_S}(s)<\mathrm{\infty }$, put $a_s(z)=\int A(y,s,z)dy$ and $b_s(z)=\int B(d,s,z)dd$. Tonelli gives $p_{X_S}(s)=\int a_s(z)b_s(z)dz<\mathrm{\infty }$, so for almost every $z$ under that conditional law both $a_s(z)$ and $b_s(z)$ are finite and positive. The conditional densities of $X_y$ and $X_D$ given $(X_S=s,X_z=z)$ are respectively $A(y,s,z)\mathrm{/}{a}_s(z)$ and $B(d,s,z)\mathrm{/}{b}_s(z)$; their product is the joint conditional density. This proves the stated conditional-independence factorization at each such $s$.

Use the Borel noise densities supplied in the hypotheses, or choose their positive finite Borel versions under Countable Choice by [F1]. Repeatedly delete a vertex that is a sink in both graphs and has the same parent set in both. At each deletion, its equation contributes a single shifted noise-density factor, which integrates to one by [F7]; no remaining equation uses the deleted vertex, so the remaining law still has the positive ANM product density and all remaining edges remain causally minimal. The process cannot delete every vertex, since then the graphs would be equal. It stops only when no common sink with equal parent sets remains; therefore choose a remaining sink $l$ of $G$, which either has a different parent set in $G^{\mathrm{\prime }}$ or has a child in $G^{\mathrm{\prime }}$.

Partition the incident vertices by $Z={\mathrm{pa}}_G(l)\cap {\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)$, $Y={\mathrm{pa}}_G(l)\cap {\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)$, $W={\mathrm{pa}}_G(l)\setminus (Z\cup Y)$, $D={\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)\setminus {\mathrm{pa}}_G(l)$, and $E={\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)\setminus {\mathrm{pa}}_G(l)$. These sets are pairwise disjoint, ${\mathrm{pa}}_G(l)=Z\cup Y\cup W$, ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(l)=Z\cup D$, and ${\mathrm{ch}}_{G^{\mathrm{\prime }}}(l)=Y\cup E$. Put $T=Y\cup W$.

Suppose $T=\mathrm{\varnothing }$ and $D\mathrm{\ne }\mathrm{\varnothing }$, and choose $d\in D$. Since $l$ is a sink in $G$, all vertices in $D\cup Z$ are nondescendants of $l$. By [F2], $N_l$ is independent of $(X_D,X_Z)$; the equation $X_l=f_l(X_Z)+N_l$ therefore makes the conditional density of $X_l$ given $(X_D,X_Z)$ independent of $X_D$. Its density factorization gives $X_l{\perp }_d{X}_D\mid X_Z$. Weak union follows directly by writing this factorization for the split $D=\{d\}\cup (D\setminus \{d\})$ and dividing by the positive marginal density: $X_l{\perp }_d{X}_d\mid X_{Z\cup (D\setminus \{d\})}$. This conditioning set contains all other parents of $l$ in $G^{\mathrm{\prime }}$ and contains no descendant of $l$ there, contradicting [F3] for $d\to l$ in $G^{\mathrm{\prime }}$.

Suppose $T=D=\mathrm{\varnothing }$ and $E\mathrm{\ne }\mathrm{\varnothing }$. Choose $e\in E$ and put $R={\mathrm{pa}}_{G^{\mathrm{\prime }}}(e)\setminus \{l\}$. Since $l$ is a sink in $G$, every vertex of $\{e\}\cup Z\cup R$ is a nondescendant of $l$. By [F2], $N_l$ is independent of $(X_e,X_R,X_Z)$; hence the conditional density of $X_l$ given these variables depends only on $X_Z$. Splitting off $X_e$ and dividing by the positive marginal density gives $X_l{\perp }_d{X}_e\mid X_{Z\cup R}$. In $G^{\mathrm{\prime }}$, $l\to e$, the set $Z\cup R$ contains all other parents of $e$, and each $z\in Z$ is an ancestor of $e$ along $z\to l\to e$, so this set contains no descendant of $e$. This contradicts [F3] for $l\to e$. If also $E=\mathrm{\varnothing }$, then $l$ is a common sink with the same parent set and would have been deleted in step 1.1.

It remains that $T\mathrm{\ne }\mathrm{\varnothing }$. Choose $t\in T$ with no directed path in $G^{\mathrm{\prime }}$ from $t$ to any other member of $T$; such a vertex exists by taking a maximal element of the directed-reachability partial order on the finite nonempty set $T$. We show that $t\mathrm{\notin }W$. For contradiction suppose $t=w\in W$, and form ${\tilde{G}}^{\mathrm{\prime }}$ by adding arrows $y^{\mathrm{\prime }}\to w$ for all $y^{\mathrm{\prime }}\in Y$ and $w^{\mathrm{\prime }}\to w$ for all $w^{\mathrm{\prime }}\in W\setminus \{w\}$. The graph is still acyclic: a new arrow could create a cycle only if $w$ already reached its tail, contrary to the choice of $w$. Also $l$ and $w$ are nonadjacent in ${\tilde{G}}^{\mathrm{\prime }}$.