Apêndice 6.J Seção 11 (Identificabilidade na Descoberta Causal)

$(1\rightarrow 2)$ Sem perda de generalidade, suponha que $V_{1}\rightarrow V_{2}$. Inicialmente, construíremos uma $f$ compatível com ${\mathcal{G}}$. Para todo $V\notin\{V_{1},V_{2}\}$, tomamos $f(V|Pa(V))={\mathbb{I}}(V=0)$. Isto é, $V$ é degenerado em $0$. Além disso, tomamos $V_{1}|Pa(V_{1})\sim\text{Bernoulli}(0.5)$ e $V_{2}|Pa(V_{2})\equiv V_{1}$. Para todo ${\mathbb{V}}\subseteq{\mathcal{V}}-\{V_{1},V_{2}\}$, ${\mathbb{P}}({\mathbb{V}}=0)=1$. Portanto, $Cov(V_{1},V_{2}|{\mathbb{V}})=Cov(V_{1},V_{2})=0.25\neq 0$. Portanto, $V_{1}$ e $V_{2}$ não são independentes dado ${\mathbb{V}}$ segundo $f$. Como $f$ é compatível com ${\mathcal{G}}$, decorre do Teorema 2.49 que $V_{1}$ e $V_{2}$ não são d-separados dado ${\mathbb{V}}$.

$(2\rightarrow 3)$ Decorre do fato de que $Anc(\{V_{1},V_{2}\})-\{V_{1},V_{2}\}$ é um caso particular de ${\mathbb{V}}$ em (2).

$(3\rightarrow 4)$ Provaremos que se existe um caminho de $V_{1}$ em $V_{2}$, $C$, que não está bloqueado dado $A$, ele também não está bloqueado dado $Pa$. Faremos esta prova em duas etapas: primeiramente considerando vértices em $C$ que não sejam colisores e, a seguir, que sejam colisores. Tome um vértice em $C$, $C_{i}$, que não é um colisor. Como $C$ não está bloqueado dado $A$, $C_{i}\notin A$. Como $Pa\subseteq A$, $C_{i}\notin Pa$. A seguir, tome um vértice em $C$, $C_{i}$, que é um colisor. Como $C$ não está bloqueado dado $A$, existe $V_{1}\in A$ tal que $V_{1}$ é descendente de $C$. Como $V_{1}\in A$, existe $V_{2}\in Pa$ tal que $V_{2}=V_{1}$ ou $V_{2}$ é descendente de $V_{1}$. Portanto, $V_{2}\in Pa$ é descendente de $C_{i}$. Decorre das conclusões anteriores que $C$ não está bloqueado dado $Pa$.

$(4\rightarrow 1)$ Considere que $V_{1}$ e $V_{2}$ não são adjacentes e suponha por abusrdo que há um caminho de $V_{1}$ a $V_{2}$, $C$, não bloqueado dado $Pa$. Como $V_{1}$ e $V_{2}$ não são adjacentes, $|C|>2$. Caso, $V_{1}\leftarrow C_{2}$, então $C_{2}\in Pa$ e $C_{2}$ não é um colisor, isto é, $C$ está bloqueado dado $Pa$. Conclua que $V_{1}\rightarrow C_{2}$. Por simetria, conclua que $C_{n-1}\rightarrow V_{2}$. Como $V_{1}\rightarrow C_{2}$ e $C_{n-1}\rightarrow V_{2}$, há pelo menos um colisor em $C$. Defina $C_{i}$ como o colisor de menor índice (o mais próximo de $V_{1}$) e $C_{j}$ o de maior índice (o mais próximo de $V_{2}$). Por definição construção, $C_{i}$ é descendente de $V_{1}$ e $C_{j}$ é descendente de $V_{2}$. Note que, se $C_{i}$ é ascendente de $V_{2}$ e $C_{j}$ é ascendente de $V_{1}$, então

é um ciclo em ${\mathcal{G}}$. Como ${\mathcal{G}}$ é um DAG, ou $C_{i}$ não é ascendente de $V_{2}$ ou $C_{j}$ não é ascendente de $V_{1}$. Sem perda de generalidade, considere que $C_{i}$ não é ascendente de $V_{2}$. Como $C_{i}$ é descendente de $V_{1}$, $C_{i}$ também não é ascendente de $V_{1}$. Como $C_{i}$ não é ascendente de $V_{1}$ ou de $V_{2}$, Não há vértice em $Pa$ que é descendente de $C_{i}$. Portanto, $C_{i}$ é um colisor e não há descendente de $C_{i}$ em $Pa$. Conclua que $C$ está bloqueado dado $Pa$, um absurdo. Portanto, $V_{1}\perp V_{2}|Pa$. ∎

($\rightarrow$) Considere que $V_{1}\rightarrow V_{2}$ e $V_{2}\leftarrow V_{3}$. Tome o caminho $C=V_{1}\rightarrow V_{2}\leftarrow V_{3}$. Como $V_{2}$ é um colisor em $C$, $C$ não está bloqueado dado qualquer ${\mathbb{V}}$ tal que $V_{2}\in{\mathbb{V}}$. Conclua que $V_{1}$ não é d-separado de $V_{3}$ dado qualquer ${\mathbb{V}}$ tal que $V_{2}\in{\mathbb{V}}$.

($\leftarrow$) Considere que $V_{1}\leftarrow V_{2}$ ou $V_{2}\rightarrow V_{3}$. Portanto, $V_{2}\in Pa:=Pa(\{V_{1},V_{3}\})-\{V_{1},V_{3}\}$. Como $V_{1}$ não é adjacente a $V_{3}$, conclua do Lema 6.24 que $V_{1}\perp V_{3}|Pa$. ∎

Decorre diretamente dos Lemas 6.24 e 6.25. ∎

Para provar este resultado basta mostrar que, se $V_{1}$ e $V_{3}$ não são adjacentes nas condições do lema, então existe $V_{*}$ com as condições especificadas. Como $Z$ é descendente de $V_{2}$ em ${\mathcal{G}}$, existe um caminho direcionado em ${\mathcal{G}}$, $C=(C_{1},\ldots,C_{n})$, tal que $C_{1}=V_{2}$ e $C_{n}=Z$. Como ${\mathcal{G}}^{*}$ tem o mesmo padrão de ${\mathcal{G}}$, $C$ é um caminho de $V_{2}$ em $Z$. Faremos a demonstração por indução.

Suponha que $C_{1}=V_{2}$ e $C_{1}=Z$, isto é, $V_{2}=Z$. Neste caso, $V_{*}=V_{2}$ satisfaz as condições do lema. A seguir, suponha que, se $n\leq n^{*}$, então existe $V_{*}$ nas condições do lema e que $n=n^{*}+1$. Se $Z$ é descendente de $V_{2}$ em ${\mathcal{G}}^{*}$, então basta tomar $V_{*}=Z$. Caso contrário, existe um menor $i$ tal que $C_{i}\leftarrow C_{i+1}$. Existem $2$ casos a considerar: $i=1$ e $i>1$.

Se $i>1$, então $C_{i-1}\rightarrow C_{i}\leftarrow C_{i+1}$ é um colisor em ${\mathcal{G}}^{*}$. Como eles formam uma cadeia em ${\mathcal{G}}$, e ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $C_{i-1}$ e $C_{i+1}$ são adjacentes em ambos os DAGs. Como $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$ e ${\mathcal{G}}$ é acíclico, $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$. Portanto, $C^{*}=(C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n})$ é um caminho de tamanho $n-1$ de $V_{2}$ a $Z$ em ${\mathcal{G}}^{*}$ que é um caminho direcionado em ${\mathcal{G}}$. Decorre da hipótese de indução que existe $V_{*}$ tal qual desejado.

Se $i=1$, $V_{2}\stackrel{{\scriptstyle{\mathcal{G}}^{*}}}{{\leftarrow}}C_{2}$. Portanto, $V_{1}\rightarrow V_{2}\leftarrow C_{2}$ e $V_{3}\rightarrow V_{2}\leftarrow C_{2}$ são colisores em ${\mathcal{G}}^{*}$, mas não em ${\mathcal{G}}$. Como ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, conclua que $V_{1}$ e $C_{2}$, e $V_{3}$ e $C_{2}$ são adjacentes em ambos os DAGs. Como $V_{1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}V_{2}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{2}$ e ${\mathcal{G}}$ é acíclico, $V_{1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{2}$. Por simetria $V_{3}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{2}$. Portanto, $V_{1}\rightarrow C_{2}\leftarrow V_{3}$ é um colisor em ${\mathcal{G}}$. Como $V_{1}$ e $V_{3}$ não são adjacentes por suposição e ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $V_{1}\rightarrow C_{2}\leftarrow V_{3}$ é um colisor em ${\mathcal{G}}^{*}$, $(C_{2},C_{3},\ldots,C_{n})$ é um caminho de tamanho $n-1$ em ${\mathcal{G}}^{*}$ e que também é um caminho direcionado em ${\mathcal{G}}$. Portanto, pela hipótese de indução, existe $V_{*}$ tal qual desejado. ∎

Desejamos provar que para quaisquer $V_{1},V_{2}\in{\mathcal{V}}$ e ${\mathbb{V}}\subseteq{\mathcal{V}}$ tais que $V_{1}\neq V_{2}$ e $\{V_{1},V_{2}\}\cap{\mathbb{V}}=\emptyset$, se existe um caminho em ${\mathcal{G}}$ de $V_{1}$ a $V_{2}$ não bloqueado dado ${\mathbb{V}}$, então existe um caminho em ${\mathcal{G}}^{*}$ de $V_{1}$ a $V_{2}$ não bloqueado dado ${\mathbb{V}}$. Tome $V_{1}$, $V_{2}$ e ${\mathbb{V}}$ arbitrários. Realizaremos a demonstração por indução.

Suponha que há um caminho de tamanho $2$ de $V_{1}$ a $V_{2}$ em ${\mathcal{G}}$ que não é bloqueado dado ${\mathbb{V}}$. Portanto, $V_{1}$ e $V_{2}$ são adjacentes em ${\mathcal{G}}$. Como ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $V_{1}$ e $V_{2}$ são adjacentes em ${\mathcal{G}}^{*}$. Conclua do Lema 6.25 que $(V_{1},V_{2})$ é um caminho não bloqueado dado ${\mathbb{V}}$ em ${\mathcal{G}}^{*}$.

A seguir, suponha que, para todo caminho de tamanho menor ou igual a $n$ em ${\mathcal{G}}$ de $V_{1}$ a $V_{2}$ que não é bloqueado dado ${\mathbb{V}}$, existe um caminho em ${\mathcal{G}}^{*}$ de $V_{1}$ a $V_{2}$ que não é bloqueado dado ${\mathbb{V}}$. Tome um caminho caminho arbitrário de tamanho $n+1$, $(C_{1},C_{2},\ldots,C_{n},C_{n+1})$ em ${\mathcal{G}}$ de $V_{1}$ a $V_{2}$ que não é bloqueado dado ${\mathbb{V}}$. Desejamos provar que existe um caminho em ${\mathcal{G}}^{*}$ de $V_{1}$ a $V_{2}$ que não é bloqueado dado ${\mathbb{V}}$.

Para tal, observamos inicialmente que, como ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $C$ é um caminho de $V_{1}$ a $V_{2}$ em ${\mathcal{G}}^{*}$. A seguir, dividiremos a análise em alguns casos:

1. a)
   ​

   Considere que existe $i$ tal que $C_{i}$ é um colisor em ${\mathcal{G}}$ e não é um colisor em ${\mathcal{G}}^{*}$. Como ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $C_{i-1}$ e $C_{i+1}$ são adjacentes em ${\mathcal{G}}$. Sem perda de generalidade, suponha que $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$. Tome $C^{*}=(C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n+1})$. Com exceção de $C_{i+1}$, todos os vértices em $C^{*}$ tem o mesmo tipo entre colisor e não-colisor que eles tem em $C$. Assim, todos os demais vértices estão abertos dado ${\mathbb{V}}$. Caso $C_{i+1}$ não seja um colisor em $C^{*}$, então ele tem o mesmo tipo que em $C$ e, assim, está aberto em $C^{*}$ dado ${\mathbb{V}}$. A seguir, resta o caso em que $C_{i+1}$ é um colisor em $C^{*}$. Como $C_{i}$ é um colisor em $C$, $C_{i}$ é descendente de $C_{i+1}$. Também, como $C_{i}$ não estava bloqueado em $C$ dado ${\mathbb{V}}$, existe $V\in{\mathbb{V}}$ tal que $V$ é descendente de $C_{i}$. Conclua que $V$ é descendente de $C_{i+1}$ e, assim, $C_{i+1}$ não está bloqueado em $C^{*}$ dado ${\mathbb{V}}$. Portanto, $C^{*}$ é um caminho de tamanho $n$ de $V_{1}$ a $V_{2}$ em ${\mathcal{G}}$ que não está bloqueado dado ${\mathbb{V}}$. Assim, esse caso está resolvido pela hipótese de indução.

2. b)
   ​

   Considere que existe $i$ tal que $C_{i}$ não é um colisor em ${\mathcal{G}}$ e é um colisor em ${\mathcal{G}}^{*}$. Como ${\mathcal{G}}$ e ${\mathcal{G}}^{*}$ tem o mesmo padrão, $C_{i-1}$ e $C_{i+1}$ são adjacentes em ${\mathcal{G}}$. Há 3 casos a analisar:

   1. I)
      ​

      Caso $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$, como ${\mathcal{G}}$ é um DAG, obtemos que $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$. Neste caso, todos os vértices no caminho $C^{*}=(C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n+1})$ tem o mesmo tipo entre colisor e não-colisor que eles tem em $C$. Assim, $C^{*}$ é um caminho de tamanho $n$ de $V_{1}$ a $V_{2}$ que não está bloqueado em ${\mathcal{G}}$ dado ${\mathbb{V}}$. Assim, esse caso está resolvido pela hipótese de indução.

   2. II)
      ​

      Caso $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\leftarrow}}C_{i}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\leftarrow}}C_{i+1}$, a análise é análoga ao caso anterior.

   3. III)
      ​

      Caso $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\leftarrow}}C_{i}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$, tome sem perda de generalidade que $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$. A seguir, há dois casos a considerar. Primeiramente, considere que $C_{i-1}$ é um colisor em $C$ em ${\mathcal{G}}$. Como $C_{i}$ é um colisor em $C$ em ${\mathcal{G}}^{*}$, $C_{i-1}$ não é um colisor em $C$ em ${\mathcal{G}}^{*}$. Portanto, $C_{i-1}$ satisfaz as condições do caso tratado em a). A seguir, se $C_{i-1}$ não é um colisor em $C$ em ${\mathcal{G}}$, então todos os vértices em $C^{*}=(C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n+1})$ tem o mesmo tipo entre colisor e não-colisor dado ${\mathbb{V}}$ que em $C$. Portanto, $C^{*}$ é um caminho de tamanho $n$ de $V_{1}$ a $V_{2}$ que não está bloqueado dado ${\mathbb{V}}$ em ${\mathcal{G}}$. Assim, esse caso está resolvido pela hipótese de indução.

3. c)
   ​

   Resta o caso tal que, para todo $i$, tanto em ${\mathcal{G}}$ quanto em ${\mathcal{G}}^{*}$, $C_{i}$ tem o mesmo tipo em $C$ entre colisor e não-colisor. Existem dois casos a analisar:

   1. I)
      ​

      Caso exista algum $i$ tal que $C_{i}$ é um colisor em $C$ tanto em ${\mathcal{G}}$ quanto em ${\mathcal{G}}^{*}$ e $C_{i-1}$ e $C_{i+1}$ são adjacentes em ${\mathcal{G}}$. Sem perda de generalidade, suponha que $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i+1}$ e tome $C^{*}=(C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n+1})$. Todos os vértices em $C^{*}$ com exceção de $C_{i+1}$ tem o mesmo tipo entre colisor e não-colisor que em $C$. Caso $C_{i+1}$ também tenha o mesmo tipo, então $C^{*}$ não está bloqueado dado ${\mathbb{V}}$. Caso contrário, $C_{i+1}$ é um colisor em $C^{*}$. Como $C_{i}$ é um colisor em $C$, obtemos que $C_{i+1}\stackrel{{\scriptstyle{\mathcal{G}}}}{{\rightarrow}}C_{i}$. Além disso, como $C_{i}$ não está bloqueado em $C$ dado ${\mathbb{V}}$, conclua que existe $V\in{\mathbb{V}}$ tal que $V$ é descendente de $C_{i}$. Conclua das duas últimas sentenças que $V$ é descendente de $C_{i+1}$. Assim, $C_{i+1}$ não está bloqueado em $C^{*}$ dado ${\mathbb{V}}$. Decorre que $C^{*}$ é um caminho de tamanho $n$ de $V_{1}$ a $V_{2}$ que não está bloqueado em ${\mathcal{G}}$ dado ${\mathbb{V}}$. Assim, esse caso está resolvido pela hipótese de indução.

   2. II)
      ​

      Caso contrário, para todo $i$ em que $C_{i}$ é um colisor em $C$, $C_{i-1}$ e $C_{i+1}$ não são adjacentes. Portanto, decorre do Lema 6.27 que existe $C^{*}_{i}$ tal que $C_{i-1}\stackrel{{\scriptstyle{\mathcal{G}}^{*}}}{{\rightarrow}}C^{*}_{i}\stackrel{{\scriptstyle{\mathcal{G}}^{*}}}{{\leftarrow}}C_{i+1}$ e existe $V\in{\mathbb{V}}$ que é descendente de $C_{i}$ em ${\mathcal{G}}^{*}$. Para todo $i$ em que $C_{i}$ não é colisor em $C$, tome $C^{*}_{i}=C_{i}$. Por construção, $C^{*}$ não está bloqueado em ${\mathcal{G}}^{*}$ dado ${\mathbb{V}}$.

∎

Decorre dos Lemas 6.26 e 6.28 ∎