Codex @codex  0

Let $X,Y$ be independent random variables, each with a Bernoulli distribution of parameter $1/2$, and put $S=X+Y$. Unconditionally, the four ordered pairs $(0,0),(0,1),(1,0),(1,1)$ each have probability $1/4$. On the event $S=1$, only $(0,1)$ and $(1,0)$ remain, each with conditional probability $1/2$. ThusKnowing that exactly one trial succeeded makes observing one outcome informative about the other. This violates conditional independence given $S$, even though the original random variables are independent. Given $S=0$ or $S=2$, both variables are constant random variables and are conditionally independent there; that does not repair the failure at $S=1$, an event of positive probability.

The conditional covariance here is $\mathbb{E}[XY\mid S=1]-\mathbb{E}[X\mid S=1]\mathbb{E}[Y\mid S=1]=0-1/4=-1/4$. Both conditional variances are $1/4$, so the conditional correlation coefficient is $-1$: within the selected group, $Y=1-X$. These conclusions follow from restricting a finite sample space, without positing any physical interaction between the trials.

This example and the shared-environment example establish both logical directions: independent random variables need not be conditionally independent, and conditionally independent variables need not be independent. When $S$ is represented as the joint result of two inputs in a causal directed acyclic graph, conditioning on it has the collider structure associated with collider bias. A probability calculation by itself establishes a dependence relation, not a physical causal mechanism or an intervention.

Write $V=\{1,\dots ,p\}$. The global Markov property for a directed acyclic graph says that, for every three pairwise disjoint vertex sets $A,B,C$,Thus graphical D-separation implies probabilistic conditional independence. Causal minimality means that $P$ has this global Markov property for a directed acyclic graph, but has it for no proper subgraph of $\mathcal{G}$ obtained by deleting edges while keeping all vertices. Faithfulness of a directed acyclic graph means that the displayed implication is an equivalence: the conditional independences of $P$ are exactly the D-separations of $\mathcal{G}$. In particular it includes the global Markov property for a directed acyclic graph.

A causally minimal distribution can nevertheless have an extra independence. Here is a causally minimal nonfaithful Gaussian model. Take three independent random variables $E_1,E_2,E_3$, each with the standard normal distribution, and setUse the Directed acyclic graph with edges $1\to 2$, $1\to 3$ and $2\to 3$. The equations give a directed acyclic graph factorization, so the global Markov property for a directed acyclic graph holds. Alternatively this complete acyclic graph imposes no nontrivial D-separations. But $Z_3=E_2+E_3$ is independent of $Z_1=E_1$, even though the direct edge $1\to 3$ prevents their D-separation. Hence faithfulness of a directed acyclic graph fails.

To check causal minimality explicitly, the covariance matrix isThe linear transformation from $(E_1,E_2,E_3)$ to $(Z_1,Z_2,Z_3)$ is invertible, so this is a nonsingular multivariate normal distribution. Deleting $1\to 2$ would require $Z_1\perp Z_2$, whereas $\mathrm{Cov}(Z_1,Z_2)=1$. Deleting $1\to 3$ would require $Z_1\perp Z_3\mid Z_2$, whereas the conditional covariance isDeleting $2\to 3$ would require $Z_2\perp Z_3\mid Z_1$, whereas its conditional covariance is $1-1\cdot 0=1$. By Gaussian conditional independence, each nonzero conditional covariance rules out the required independence. Every proper subgraph is contained in a graph obtained by a single edge deletion, and further deletion can only add Markov restrictions. Thus no proper subgraph is Markov for $P$, proving causal minimality.

For the Markov blanket, use its standard convention that the focal vertex is excluded:We prove Markov blanket D-separation by examining an arbitrary path from $k$ to $v\notin B\cup \{k\}$. If its first edge points into $k$, its next vertex is a parent of $k$, hence a conditioned noncollider in $B$, and the path is blocked. Otherwise the path starts $k\to h$ at a child $h\in B$. If the next edge points out of $h$, then $h$ is again a conditioned noncollider. If it points into $h$, the path begins $k\to h\leftarrow u$. Although conditioning on the collider $h$ opens that local segment, $u$ is another parent of $h$, hence belongs to $B$. The outgoing arrow $u\to h$ makes $u$ a noncollider on the path, so conditioning on $u$ blocks it. Since $v$ is outside $B$, none of these blocking vertices can be the endpoint.

Every path is therefore blocked by $B$. Applying the global Markov property for a directed acyclic graph givesThis proves the requested screening property without any positivity assumption on $P$.

Finally assume faithfulness of a directed acyclic graph and let $A$ have the stated screening property. Then $k$ and every vertex outside $A\cup \{k\}$ must be D-separated by $A$. If a parent or child $h$ of $k$ were missing from $A$, the one-edge path between them would be active, a contradiction. Thus every parent and child is in $A$. If another parent $u$ of a child $h$ were missing from $A$, the path $k\to h\leftarrow u$ would be active: its only interior vertex is the collider $h$, already in $A$. This is again a contradiction. ConsequentlyUnder faithfulness the graphical blanket is contained in every screening set. This is the minimal Markov blanket under faithfulness; the preceding argument also shows that the blanket itself is a screening set.

The global Markov property for a directed acyclic graph requires, for all pairwise disjoint vertex sets $A,B,C$, that D-separation of $A$ and $B$ by $C$ in $G$ implies $Z_A\perp Z_B\mid Z_C$. Two Markov equivalent directed acyclic graphs encode exactly the same such D-separations. The structural characterization is that they have the same skeleton of a directed graph and the same unshielded colliders. A distribution has faithfulness of a directed acyclic graph when its conditional independences are exactly those encoded by D-separation; this includes the global Markov implication as well as its converse.

The population PC algorithm uses an exact conditional independence oracle. Start with the complete undirected graph, and conditioning-set size $\ell =0$. At each size, examine ordered adjacent pairs $(u,v)$. Test subsets $C\subseteq \mathrm{Adj}(u)\setminus \{v\}$ of size $\ell$ until independence $Z_u\perp Z_v\mid Z_C$ is found or all such subsets have been examined. On finding it, delete $u-v$ and record a symmetric separating set $\mathrm{Sep}(u,v)=\mathrm{Sep}(v,u)=C$. Ordered pairs ensure that subsets from either endpoint's neighbours are considered. Increase $\ell$ until no adjacent ordered pair has enough remaining neighbours to supply a set of that size. Rechecking eligibility after deletion, or freezing the neighbours at each level and then deleting, gives the same population skeleton under the hypothesis below.

Next, for each unshielded triple $u-v-w$ with $u,w$ nonadjacent, orient $u\to v\leftarrow w$ precisely when $v\notin \mathrm{Sep}(u,w)$. Propagate directions that are forced without introducing a directed cycle or an additional unshielded collider. In particular, $a\to b-c$ with $a,c$ nonadjacent forces $b\to c$; an undirected edge $a-b$ with a directed path from $a$ to $b$ forces $a\to b$; and $a-b,a-c,a-d,c\to b,d\to b$ with $c,d$ nonadjacent forces $a\to b$. The first avoids a new unshielded collider, the second a directed cycle. For the third, $b\to a$ would force $c\to a$ and $d\to a$ to avoid cycles, creating the prohibited unshielded collider $c\to a\leftarrow d$.

For a fully specified exact completion, list all acyclic orientations of the recovered skeleton which extend the collider arrows and have exactly the recorded unshielded colliders. Direct an edge if and only if all listed graphs orient it the same way; otherwise leave it undirected. This finite enumeration implements the definition of the completed partially directed acyclic graph; orientation propagation is the usual efficient way to obtain the same completion. The equivalence-class proof below uses the exact completion description and does not need an unproved completeness claim about a chosen subset of propagation rules.

To prove correctness, assume faithfulness of a directed acyclic graph to $G^0$. A true edge $u\to v$ cannot be D-separated by any set excluding its endpoints: its length-one path is always active. Thus a true edge is never deleted. Conversely, take nonadjacent $u,v$ and choose their order so that $u$ is earlier than $v$ in a topological ordering of $G^0$. Then $u$ is a nondescendant and nonparent of $v$. Its parent set $\mathrm{Pa}(v)$ gives D-separation of $u$ and $v$. To see this local graphical fact, a path beginning $v\leftarrow q$ is blocked by the conditioned parent $q$, a noncollider. A path beginning with an arrow out of $v$ must encounter a first collider before reaching the nondescendant $u$. That collider is a descendant of $v$, and neither it nor any of its descendants can be a parent of $v$ in an acyclic graph. Hence conditioning on $\mathrm{Pa}(v)$ does not open it.

All parent edges survive. If $u-v$ has not already been deleted, $\mathrm{Pa}(v)$ remains among $v$'s neighbours excluding $u$. It is therefore tested by size $|\mathrm{Pa}(v)|$, and faithfulness forces deletion. The size loop cannot stop prematurely while this set remains eligible. This proves exact recovery of the skeleton of a directed graph.

For an unshielded triple $u-v-w$, if it is a noncollider in $G^0$, its length-two path remains active unless $v$ is conditioned on. Thus every separator of $u,w$ contains $v$. If it is a collider, conditioning on $v$ opens the length-two path, so no separator can contain $v$. Faithfulness turns these graphical statements into the recorded separator test. Therefore the collider phase recovers precisely all unshielded colliders. By the skeleton and collider characterization of Markov equivalence, the acyclic extensions with exactly these colliders are exactly the Markov equivalence of directed acyclic graphs class of $G^0$. In particular that set is nonempty, and the completion returns its CPDAG. This proves population PC correctness under faithfulness.

For the four-variable example, the only removable pairs are $2,4$, with separator $\varnothing$, and $1,3$, with separator $\{2,4\}$. The remaining skeleton has edges $1-2,1-4,2-3,3-4$. The unshielded triples $2-1-4$ and $2-3-4$ both have center outside the separator of $2,4$, so both are unshielded colliders. Every remaining edge is thereby oriented:The other two unshielded triples are noncolliders, consistent with the separator $\{2,4\}$ of $1,3$. There is no undirected edge left, so the equivalence class consists of this unique Directed acyclic graph. This identification is about the given faithful observational distribution; general PC algorithm outputs need not identify a unique causal direction.

The moral graph of a Directed acyclic graph is formed by joining any two parents of a common child and then removing the directions from all edges. For D-separation, a path in the underlying undirected graph is active given $S$ when every noncollider on it is outside $S$, and every collider has itself or a descendant in $S$. Disjoint vertex sets $A$ and $B$ are D-separated by $S$ if no such active path connects them.

The adjacency characterization isA one-edge path cannot be blocked by conditioning on other vertices. For a nonadjacent pair, choose the later vertex $v$ in a topological ordering. The earlier vertex $u$ is a nondescendant and is not a parent of $v$, so the parents of $v$ separate the pair by the local Markov property of a directed acyclic graph.

Use faithfulness of a directed acyclic graph to mean that graphical and probabilistic independences agree, for all disjoint sets:This includes the global Markov property of a directed acyclic graph as well as the absence of extra independences. The conditional independence graph of $P$ is the undirected graph in which $u-v$ is absent exactly when $Z_u\perp Z_v\mid Z_{V\setminus \{u,v\}}$.

To identify this graph, condition on every vertex other than $u,v$. Any noncollider in the interior of a path is then conditioned on, so an active path must have only colliders internally. Two adjacent interior vertices cannot both be colliders: the arrow joining them has an arrowhead at only one of its ends. Thus an active path can have no interior vertex, giving a direct edge, or just one, giving $u\to w\leftarrow v$. In the latter case the conditioned common child $w$ activates the path. These possibilities are exactly the edges added or retained by moralization. Faithfulness therefore provesThis is why the moral graph equals the conditional independence graph under faithfulness.

For Gaussian graph estimation, collect the data into an $n\times p$ matrix $D$ and let $S_n=n^{-1}{\sum }_i{x}_i{x}_i^T$. The precision matrix $\Theta ={\Sigma }^{-1}$ has ${\Theta }_{jk}=0$ precisely for absent graph edges, by Gaussian conditional independence. In neighbourhood selection, fit a Lasso regression of each column on the others:Select the nonzero coefficients as neighbours of $j$, then make the graph undirected using either the OR rule, retaining an edge selected in at least one regression, or the AND rule, requiring both. These are instances of Nodewise Lasso.

The Graphical Lasso estimates the whole precision matrix jointly, for example byRead off its nonzero off-diagonal entries as graph edges. This expression uses an off-diagonal penalty; an all-entry penalty is another convention.

To reduce computation in the PC algorithm, start its skeleton search from an estimate of the conditional independence graph rather than the complete graph. The exact graph contains the true DAG skeleton, so oracle tests can remove its extra edges while retaining the true adjacencies. Fewer initial edges and smaller neighbourhoods reduce both candidate pairs and candidate conditioning sets.

For correctness of the orientation stage, preserve valid separating-set records. With an exact conditional independence graph, an initially absent pair $u,v$ has the full complement $V\setminus \{u,v\}$ as a separating set. Record that set, and record the usual discovered sets for edges removed later. Leaving an initially absent pair with an empty default could falsely mark an unshielded noncollider as a collider. This describes PC initialization from a conditional independence graph; with an estimated initial graph, screening errors can propagate into the output.

Definition 1 satisfies Property 1 but not Property 2. Let $S_1$ contain every non-descendant that blocks some backdoor path. Every backdoor path begins $A\leftarrow P$ for a parent $P$ of $A$; whenever that path can transmit confounding, $P\in S_1$. Conditioning on $S_1$ therefore blocks every such path at its first nonendpoint vertex, so $S_1$ is sufficient.

For failure of Property 2, consider the faithful graph with arrowsThe variable $X_i$ blocks the backdoor path $A\leftarrow C\to X_i\to Y$, so Definition 1 calls it a confounder. Every sufficient set containing $X_i$ must nevertheless contain $C$ to block $A\leftarrow C\to Y$. Once $C$ is included, deleting $X_i$ leaves a sufficient set. Thus $X_i$ can never be essential as Property 2 demands.

Definition 2 satisfies Property 2 but not Property 1. If $X_i$ belongs to every minimal sufficient adjustment set, choose one such set $I$ and put $J=I\setminus \{i\}$. By minimality, $J\cup \{i\}$ is sufficient and $J$ is not, proving Property 2.

For failure of Property 1, use the faithful chain-shaped backdoor pathBoth $\{C_1\}$ and $\{C_2\}$ are minimal sufficient adjustment sets. No variable belongs to every minimal sufficient set, so Definition 2 labels no variable a confounder, but the empty set is not sufficient.

Definition 3 satisfies Property 1 but not Property 2. Under faithfulness, its associational criterion contains enough non-descendants to block every open backdoor path. Indeed, if such a path remained open, its first unconditioned parent of $A$ would be D-connected to $A$ and, after a suitable conditioning set, to $Y$ given $A$; faithfulness would place that parent in the Definition 3 set, a contradiction. Thus adjusting for all variables selected by Definition 3 is sufficient.

For failure of Property 2, considerwith both $Z$ and $U$ observed and a faithful distribution. The instrumental variable $Z$ is associated with $A$. Conditioning on the collider $A$ opens $Z\to A\leftarrow U\to Y$, so $Z$ is associated with $Y$ given $A$ and Definition 3 calls it a confounder. Any sufficient set containing $Z$ must also contain $U$ to block $A\leftarrow U\to Y$, but $\{U\}$ is already sufficient. Hence removing $Z$ never destroys sufficiency, violating Property 2.

Let $G$ be the genetic instrument, $X$ vitamin-D concentration, $U$ an unmeasured cause of vitamin D and mortality, and $Y$ mortality. The causal directed acyclic graph containsAlthough $G$ and $U$ are marginally independent, $X$ is a collider. Conditioning on $X$ opens the path $G\leftrightarrow U\to Y$, violating instrumental-variable independence within the resulting strata. Residual exposure stratification instead removes the component of $X$ predicted by $G$ before stratification; under the additive first-stage model, the stratifying variable is no longer caused by $G$.

Among observed pretreatment variables, every sufficient set must contain $M_1$ to blockand $Z_3$ to blockConditioning on $Z_3$ opens the collider onso $M_3$ must also be included. The resulting minimal sufficient adjustment set isIt blocks every path from $Z_1$ to $Y$ that remains after removing $A\to Y$, while the open pathpreserves instrument relevance. Adding $M_2$ blocks no required relevance path, sois also sufficient.

There are no others. In particular, adding $Z_2$ blocks the displayed relevance path. Without $M_2$, conditioning on $Z_2$ also openswhich violates independence; adding $M_2$ closes that path but leaves no open path from $Z_1$ to $A$. Hence the complete list is $X_0$ and $X_1$.

The administrative data include only encounters with $M=1$. Conditioning on the stop indicator selects on the colliderwhich opens the noncausal path $D\leftrightarrow U\to Y$ and creates collider bias. The equal entries estimate only the selected risks $\mathbb{P}(Y=1\mid D=d,M=1)$. They ignore racial differences in the probability of being stopped and therefore do not identify the total causal effect of race on violence. This is also selection bias, because encounters with $M=0$ never enter the dataset.

The claim is not implied. On the path $A\leftrightarrow Y\leftarrow X$, $Y$ is a collider, and conditioning on $Y$ opens that path. Equivalently, conditioning on the common effect $Y$ can induce collider bias between $A$ and $X$.

An unshielded collider in a Directed acyclic graph is a triple $a\to b\leftarrow c$ with $a$ and $c$ nonadjacent. The absence of an edge between its outer vertices makes this orientation detectable from conditional independence information under faithfulness of a directed acyclic graph.