PC algorithm and Markov-equivalence structure learning — Examples

Let $W_1,\dots ,W_m$ be a finite independent family of scalar normal variables with means ${\mu }_r$ and variances ${\sigma }_r^2$. For any real coefficients $a_1,\dots ,a_m,b$, [F1]–[F2] give the characteristic function of $b+{\sum }_r{a}_r{W}_r$ as $\exp \text{\hspace{0.17em}⁣}(it(b+{\sum }_r{a}_r{\mu }_r)-\frac{t^2}{2}{\sum }_r{a}_r^2{\sigma }_r^2)$; scalar uniqueness identifies this as the normal law with that mean and variance. Every scalar projection of a finite affine image of $W=(W_1,\dots ,W_m)$ is such a sum, so [F3] proves that every such image is multivariate normal, including when a projection has variance zero.

The chain model's density is $\varphi (x)\varphi (y-x)\varphi (z-y)$, where $\varphi$ is the standard-normal density. Its factors are exactly the parent probability kernels $K_X(dx)=N(0,1)(dx)$, $K_Y(x,dy)=N(x,1)(dy)$, and $K_Z(y,dz)=N(y,1)(dz)$, so the full-joint law factorizes in the topological order $X,Y,Z$. All three vertices are observed and [F8] gives the Markovian SCM condition. Its moments are $\mathrm{Var}(X)=1$, $\mathrm{Var}(Y)=2$, $\mathrm{Var}(Z)=3$, and distinct covariances $\mathrm{Cov}(X,Y)=1$, $\mathrm{Cov}(Y,Z)=2$, $\mathrm{Cov}(X,Z)=1$. The vector is multivariate normal by step 1.1, and its covariance matrix is positive definite because $(X,Y,Z)$ is an invertible triangular linear transform of $(U_X,U_Y,U_Z)$. The conditional covariance formula gives $\mathrm{Cov}(X,Z\mid Y)=1-\frac{1\cdot 2}{2}=0,\mathrm{Cov}(X,Y\mid Z)=1-\frac{1\cdot 2}{3}=\frac{1}{3},\mathrm{Cov}(Y,Z\mid X)=2-\frac{1\cdot 1}{1}=1.$ Together with the nonzero marginal covariances, [F4] shows that the only conditional independence between distinct variables is $X\perp Z\mid Y$. By [F10], the only d-separated vertex pair is also $X,Z$ given $Y$: the adjacent pairs have an active one-edge path, and the $X$–$Z$ path is blocked only by conditioning on $Y$. Any conditional independence between vertex sets would imply the corresponding coordinate independences, so the set-level independence and d-separation models also agree. This verifies faithfulness in [F7].

The collider model's density is $\varphi (x)\varphi (z)\varphi (y-x-z)$. Its factors are exactly the parent probability kernels $K_X(dx)=N(0,1)(dx)$, $K_Z(dz)=N(0,1)(dz)$, and $K_Y(x,z,dy)=N(x+z,1)(dy)$, so the full-joint law factorizes in the topological order $X,Z,Y$. All vertices are observed and [F8] gives the Markovian SCM condition. Its variances are $\mathrm{Var}(X)=\mathrm{Var}(Z)=1$, $\mathrm{Var}(Y)=3$, its covariances are $\mathrm{Cov}(X,Y)=\mathrm{Cov}(Z,Y)=1$, and $\mathrm{Cov}(X,Z)=0$. The vector is multivariate normal by step 1.1, and this covariance matrix is positive definite by the invertible triangular map from the exogenous variables. The conditional covariances are $\mathrm{Cov}(X,Z\mid Y)=0-\frac{1\cdot 1}{3}=-\frac{1}{3},\mathrm{Cov}(X,Y\mid Z)=1,\mathrm{Cov}(Y,Z\mid X)=1.$ Therefore [F4] shows that $X\perp Z$ marginally, but there is no conditional independence after conditioning on the third variable and no independence for an adjacent pair. By [F10], this is exactly the collider DAG's d-separation list: the collider path is blocked unconditioned and opened by conditioning on $Y$, while each adjacent pair has an active one-edge path. Any set conditional independence would imply coordinate independences, so [F7] holds at the set level as well.

Thus PC does not delete any pair at level $0$. At level $1$, $X-Z$ is deleted and its separator is recorded as $\{Y\}$; $X-Y$ and $Y-Z$ remain because step 2.1 shows that each is dependent both marginally and conditional on the third variable. The sole unshielded triple has its middle vertex in the separator, so [F5] or [F6] leaves both edges undirected. No Meek rule applies without a directed edge, and the output is the undirected chain CPDAG. The run terminates under [F9], since step 2.1 verifies the chain model's discovery-regime hypotheses.

PC deletes $X-Z$ at level $0$ and records the empty separator. It retains $X-Y$ and $Y-Z$ by their nonzero marginal covariances. Since $Y$ is absent from the separator, [F5] orients $X\to Y\leftarrow Z$; the output is the collider CPDAG. The run terminates under [F9], since step 2.2 verifies the collider model's discovery-regime hypotheses. These calculations verify both claimed outputs without relying on the diagrams.

Let $W_1,\dots ,W_m$ be a finite independent family of scalar normal variables with means ${\mu }_r$ and variances ${\sigma }_r^2$. For real coefficients $a_1,\dots ,a_m,b$, [F3] gives the characteristic function of $b+{\sum }_r{a}_r{W}_r$ as $\exp \text{\hspace{0.17em}⁣}(it(b+{\sum }_r{a}_r{\mu }_r)-\frac{t^2}{2}{\sum }_r{a}_r^2{\sigma }_r^2)$; scalar uniqueness identifies this as the normal law with that mean and variance. Every scalar projection of a finite affine image of $W=(W_1,\dots ,W_m)$ is such a sum, so [F4] proves that every such image is multivariate normal, including when a projection has variance zero.

In the latent model, $\mathbb{E}(X,Y)=(0,0)$, $\mathrm{Var}(X)=\mathrm{Var}(Y)=2$, and $\mathrm{Cov}(X,Y)=1$, by independence of $L,U_X,U_Y$. In the direct-edge model, $\mathbb{E}(X,Y)=(0,0)$, $\mathrm{Var}(X)=2$, $\mathrm{Cov}(X,Y)=\frac{1}{2}\mathrm{Var}(X)=1$, and $\mathrm{Var}(Y)=\frac{1}{4}(2)+\frac{3}{2}=2$. Both vectors are Gaussian by step 1.1 and have the same positive-definite covariance matrix $\mathrm{\Sigma }=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$, whose leading principal minors are $2$ and $3$. By [F5], both vector characteristic functions equal $\exp (-t^T\mathrm{\Sigma }t\mathrm{/}2)$ for every $t\in {\mathbb{R}}^2$; the uniqueness clause of [F5] gives equality of the full observed laws.

The latent model is a finite recursive Markovian SCM with observed set $\{X,Y\}$ and omitted latent vertex $L$, so it does not satisfy [F2]. The direct-edge model has observed set $\{X,Y\}$ and independent exogenous variables; its full-joint law factors as $N(0,2)(dx)N(x\mathrm{/}2,3\mathrm{/}2)(dy)$, the root probability kernel for $X$ followed by the probability kernel for $Y$ given its parent $X$. In its two-vertex graph $X\to Y$, the only pair of nonempty disjoint endpoint sets is $\{X\},\{Y\}$, which is not d-separated because of the direct path; step 2.1 gives $\mathrm{Cov}(X,Y)=1$, so they are not independent. Thus this law is faithful to the direct-edge DAG, and the direct-edge model satisfies the observed-only Markovian factorization and faithfulness conditions in the discovery regime. Since the observed laws agree by step 2.1, no procedure using only that law can distinguish the two causal explanations.

The common observed law has $\mathrm{Cov}(X,Y)=1\mathrm{\ne }0$, so $X,Y$ are dependent and the perfect oracle does not delete their only edge. With only two vertices there is no unshielded triple and none of R1–R3 applies; by [F9] the regime-compliant run terminates, and its computed output is $X-Y$. Reversing the single edge in the direct-edge DAG keeps the same skeleton and no unshielded collider, so [F6] proves the reverse DAG is equivalent; [F7] therefore gives the same undirected CPDAG. The PC output reports adjacency but cannot recover the latent-versus-direct causal distinction.

Each graph has all three possible edges, so there is no triple with nonadjacent endpoints and in particular no unshielded collider. Their skeletons and unshielded colliders agree; [F2] proves Markov equivalence. Every distinct pair has a direct active path under every allowed conditioning set by [F1], so neither DAG has a d-separation between distinct vertices. Faithfulness in [F6] makes the oracle dependent on every pair and set.

In the two DAGs, the orientations of $A-B$, $A-C$, and $B-C$ are respectively $A\to B$ versus $B\to A$, $A\to C$ versus $C\to A$, and $B\to C$ versus $C\to B$. Thus each edge is oriented both ways in the equivalence class, and [F3] makes every edge undirected in the CPDAG.

The perfect oracle never reports independence for any pair by step 1.1, so the algorithm deletes no edge. With three vertices, after the level-$0$ tests the complete triangle permits level $1$; at level $1$ each pair has only one possible conditioning vertex at each endpoint, and the oracle again returns dependence by step 1.1. The stopping condition then fails because an endpoint has at most one neighbor other than the other endpoint, fewer than the required two. Thus the skeleton search terminates. There is no unshielded triple to orient, and none of R1–R3 can fire because each requires at least one directed edge; the finite orientation scan therefore terminates as well. PC returns the undirected triangle, which [F5] identifies with the CPDAG found in step 1.2. The diagram is only a rendering of these verified adjacencies and orientations.