6
$\begingroup$

Background: $\newcommand{\doop}{\operatorname{do}}\newcommand{\op}[1]{\operatorname{#1}}$

Definition 1.2.2 (Markov Compatibility) If a probability function $P$ admits the factorization of $$P(x_1,\dots,x_n)=\prod_i P(x_i|\operatorname{pa}_i)$$ relative to the Directed Acyclic Graph (DAG) $G,$ we say that $G$ represents $P,$ that $G$ and $P$ are compatible, or that $P$ is Markov relative to $G.$

Here the $\operatorname{pa}_i$ are the parents of $x_i.$

Definition 1.3.1 (Causal Bayesian Network) Let $P(v)$ be a probability distribution on a set $V$ of variables, and let $P(v|\doop(x))$ denote the distribution resulting from the intervention $\doop(X=x)$ that sets a subset $X$ of variables to constants $x.$ Denote by $P_*$ the set of all interventional distributions $P(v|\doop(x)), X\subseteq V,$ including $P(v),$ which represents no intervention (i.e., $X=\varnothing$). A DAG $G$ is said to be a causal Bayesian network compatible with $P_*$ if and only if the following three conditions hold for every interventional $P\in P_*:$

  1. $P(v|\doop(x))$ is Markov relative to $G;$
  2. $P(v_i|\doop(x))=1$ for all $V_i\in X$ whenever $v_i$ is consistent with $X=x;$
  3. $P(v_i|\operatorname{pa}_i,\doop(x))=P(v_i|\operatorname{pa}_i)$ for all $V_i\not\in X$ whenever $\operatorname{pa}_i$ is consistent with $X=x,$ i.e., each $P(v_i|\operatorname{pa}_i)$ remains invariant to interventions not involving $V_i.$

Truncated Factorization: $$P(v|\doop(x))=\prod_{i|V_i\not\in X}P(v_i|\operatorname{pa}_i)\qquad\text{for all } v \text{ consistent with }x.$$

Problem Statement: Prove that the three conditions of Definition 1.3.1 (Causal Bayesian Network) are necessary and sufficient for the truncated factorization.

My Answer So Far:

$(\to)$ Assume the three conditions of Definition 1.3.1 hold. We know by (i) that we can write $$P(v|\doop(x))=\prod_iP(v_i|\op{pa}_i,\doop(x)).$$ Then we factor into two products, depending on where the $v_i$ are: \begin{align*} P(v|\doop(x)) &=\prod_iP(v_i|\op{pa}_i,\doop(x))\\ &=\left[\prod_{i, v_i\in X}P(v_i|\op{pa}_i,\doop(x))\right]\left[\prod_{i, v_i\not\in X}P(v_i|\op{pa}_i,\doop(x))\right]. \end{align*} According to (ii), the first product is $1,$ yielding $$P(v|\doop(x))=\prod_{i, v_i\not\in X}P(v_i|\op{pa}_i,\doop(x)).$$ Finally, we argue that \begin{align*} P(v|\doop(x)) &=\prod_{i, v_i\not\in X}P(v_i|\op{pa}_i,\doop(x))\\ &=\prod_{i, v_i\not\in X}P(v_i|\op{pa}_i) \end{align*} by invoking (iii), since we assumed that $P(v_i|\op{pa}_i)$ are invariant to interventions involving $X.$ Am I correct so far?

$(\leftarrow)$ Other than the obvious first step of assuming we can write the truncated factorization, I don't have any ideas on this one. How can I proceed? Would the steps in the $(\to)$ direction all be reversible?

Many thanks for your time!

$\endgroup$
1
+50
$\begingroup$

$\newcommand{\doop}{\operatorname{do}}\newcommand{\op}[1]{\operatorname{#1}}$ I think your proof of the forward implication is correct. For the backward implication I may have something.

Suppose the Truncated Factorization: for all $v$ consistent with $x$, $$P(v\mid \mathrm{do}(x))=\prod_{i\mid Vi\notin X}P(v_i \mid \mathrm{pa}_i)$$ for a non cyclic oriented graph $G$.

Proof that condition 3 is verified

Let be $i$, $v_i$, and an intervention $X = x$ be such that $V_i \notin X$ and a realization of $\mathrm{pa}_i$ is compatible with $X = x$. We need to prove that: $$P(v_i|\mathrm{pa}_i, \mathrm{do}(x)) = P(v_i |\mathrm{pa}_i).$$ To do so, let's take an intervention $X' = x'$ such that:

  • $X \subset X'.$
  • $X = x$ and $X' = x'$ are compatible.
  • $V_i \notin X'$ and $\forall j\neq i, V_j\in X'.$
  • The realization of $\mathrm{pa_i}$ considered is compatible with $X'.$

Intuitively, we are fixing everything but $V_i$ by an intervention, without contradicting the intervention $X = x$ nor the considered realization of $\mathrm{pa}_i$.

Then, using the factorization, $$P(v|\mathrm{do}(x')) = P(v_i| \mathrm{pa}_i)$$ since only index $i$ is left in the product, and thus $$P(v|\mathrm{do}(x'), \mathrm{do}(x)) = P(v_i|\mathrm{pa}_i, \mathrm{do}(x)).$$ But as $X = x$ is included in $X' = x'$, $P(v|\mathrm{do}(x'), \mathrm{do}(x)) = P(v|\mathrm{do}(x'))$. So we have that: $$P(v_i|\mathrm{pa}_i, \mathrm{do}(x)) = P(v_i|\mathrm{pa}_i),$$ which is what we wanted.

Proof that condition 1 is verified

If we use the truncated factorization on a null intervention, we obtain that $G$ and $P$ are Markov compatible: $$P(v) = \prod_i P(v_i|\mathrm{pa}_i).$$ Conditioning the last equation on an intervention $X = x$, we get that $$P(v|\mathrm{do}(x)) = \prod_i P(v_i|\mathrm{pa}_i, \mathrm{do}(x)),$$ which is that $P(v|\mathrm{do}(x))$ and $G$ are Markov compatible.

Proof that condition 2 is verified

Let's consider an intervention $X =x$. Using condition 1, we have: \begin{align*} P(v|\doop(x)) &=\prod_i P(v_i|\op{pa}_i, \doop(x))\\ &=\prod_{i|V_i\in X}P(v_i|\op{pa}_i,\doop(x))\cdot\prod_{i|V_i\not\in X}P(v_i|\op{pa}_i,\doop(x))\\ &=\prod_{i|V_i\in X}P(v_i|\op{pa}_i,\doop(x))\cdot\prod_{i|V_i\not\in X}P(v_i|\op{pa}_i), \end{align*} using condition 3. As $P(v|\mathrm{do}(x))$ can also be expressed with the truncated factorization, we get that: $$\prod_{i|V_i \notin X}P(v_i|\mathrm{pa}_i) = \prod_{i|V_i \in X}P(v_i|\mathrm{pa}_i, \mathrm{do}(x))\prod_{i|V_i \notin X}P(v_i| \mathrm{pa}_i)$$ and so, simplifying by dividing out $P(v_i|\mathrm{pa}_i)$: $$ \prod_{i|V_i \in X}P(v_i|\mathrm{pa}_i) = 1 .$$ (To be allowed to make this simplification, we need to suppose that $P(v_i|\mathrm{pa}_i) \neq 0$, which is necessarily the case if we suppose $P(v|\mathrm{do}(x)) \neq 0$ for instance.)

In the end we have that $P(v_i|\mathrm{pa}_i, \mathrm{do}(x)) = 1$ for all $i$ such that $i \in X$ (since their product is $1$). To get to condition 2, write $$P(v_i|\mathrm{do}(x)) = \mathbb{E}_{\mathrm{pa}_i}\left[P(v_i| \mathrm{pa}_i, \mathrm{do}(x))\right] = \mathbb{E}_{\mathrm{pa}_i}\left[1\right] = 1.$$

I hope this is understandable, correct and helping..

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks very much! I'll go ahead and award you the bounty, but I need to digest it a bit more before I accept it as the answer. $\endgroup$ – Adrian Keister Jun 8 at 18:12
  • $\begingroup$ In (ii), why does $$P(v_i|\operatorname{do}(x))=E_{\operatorname{pa}_i}\!\!\left[P(v_i|\operatorname{pa}_i,\operatorname{do}(x))\right]?$$ $\endgroup$ – Adrian Keister Jun 10 at 20:23
  • $\begingroup$ We start from the equality $P(v_i) = E_{pa_i}[P(v_i\mid pa_i)]$ and then condition on the intervention $do(x)$. Is this correct ? $\endgroup$ – Pohoua Jun 10 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.