Codex @codex  0

The moral graph of a Directed acyclic graph joins every pair of vertices with a common child and then replaces every directed edge by an undirected edge.

If D-separation and conditional independence are equivalent for a Directed acyclic graph, its moral graph is its conditional independence graph. After conditioning on all other vertices, an active path can only be a direct edge or a two-edge collider through a common child: two adjacent interior vertices cannot both be colliders. These are exactly the moral edges.

Choose a strict total order $v_1<\cdots <v_n$ of the vertices of a finite simple graph. Direct every edge $v_i{v}_j$ from $v_i$ to $v_j$ when $i<j$. Along every directed path, the index strictly increases. Returning to the starting vertex would require an impossible strict increase back to the initial index, so this is an acyclic orientation. The displayed $D_1$ comes from $A<B<C$.

The chosen strict total order is a topological order of the resulting Directed acyclic graph. Conversely, every acyclic orientation of a finite simple graph has a topological order, and orienting its edges from earlier to later in that order recovers it. Different topological orders can induce the same acyclic orientation, since vertices with no edge between them need not impose a choice of arrow.^[ref]

An order respects reachability but does not create it: $u<v$ in a chosen topological order does not imply a directed path from $u$ to $v$. For example, orient the two edges of the graph path $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no directed path from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing directed edges with graph search decides this directional reachability.^[ref]

Label the full siblings at the bottom $X,Y$ and their cousin parents $F,M$. Let $F$ have parents $A,B$ and $M$ parents $C,D$, where $A,C$ are siblings with parents $U,V$. Include the other great-grandparents as $P,Q$, parents of $B$, and $R,S$, parents of $D$. This gives fourteen people, with six independent founders in a pedigree $U,V,P,Q,R,S$.

The pedigree graphical model has the following Directed acyclic graph, with both members of each parent pair pointing to every listed child:Let $f(g)$ be the founder genotype law under Hardy-Weinberg equilibrium, and let $t(g\mid h,k)$ be the Mendelian segregation kernel. The joint probability of all genotypes isFor a biallelic locus with allele-1 frequency $p$, $f(11)=p^2$, $f(12)=2p(1-p)$ and $f(22)=(1-p{)}^2$. The kernel $t$ assigns probability $1/4$ to each labelled pair of parental transmissions and adds these probabilities when they produce the same unordered genotype. Summing this Bayesian network factorization over unobserved genotypes gives their marginal distribution or a pedigree likelihood.

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

Model 2 is an errors-in-variables model: the follow-up regression depends on a latent true baseline rather than substituting its noisy observation. A common normal distribution for the true baselines provides partial pooling and allows uncertainty about each baseline to propagate to the regression coefficients and predictions. Conditional on the shared parameters, the child-specific factorization isThe Directed acyclic graph below includes the shared parameters, the two local latent variables, both observed measurements, and the deterministic regression mean. The outer plate repeats over children and the inner plate over follow-up visits. Filled nodes are observed; rectangular mean nodes are deterministic.

One complete adapted BUGS specification uses the non-centered form of the random intercept, retaining the original priors and adding proper broad priors for $\theta$ and $\psi$:

for (i in 1:N) {
  z[i] ~ dnorm(0, 1)
  alpha[i] <- delta + tau*z[i]
  truebase[i] ~ dnorm(theta, baseprec)
  baseline[i] ~ dnorm(truebase[i], noiseprec)
  for (j in 1:3) {
    followmean[i,j] <- alpha[i] + beta*log(time[i,j]) + gamma*truebase[i]
    followup[i,j] ~ dnorm(followmean[i,j], noiseprec)
  }
}
noiseprec ~ dgamma(0.001, 0.001)
beta ~ dunif(-100, 100)
gamma ~ dunif(-100, 100)
delta ~ dunif(-100, 100)
tau ~ dunif(0, 100)
theta ~ dunif(-100, 100)
psi ~ dunif(0, 100)
baseprec <- 1/(psi*psi)

Here $N$ is the number of children, baseline and followup contain the observed data, and dnorm uses precision rather than variance. The priors on the newly introduced population baseline mean and standard deviation are explicit choices, not consequences of the likelihood; sensible alternatives can be checked for sensitivity. The code uses the noisy baseline only in its own measurement likelihood, and uses truebase in every follow-up mean.

Here a directed cycle has at least one edge. If zero-length paths were treated as cycles, an edgeless one-vertex graph would already satisfy the predicate; that convention would give the trivial nonempty-graph predicate instead of the intended directed cycle detection problem.

For NL membership, guess a starting vertex $v$, follow a guessed directed walk for between one and $N=|V|$ edges, and accept if it returns to $v$. Store only the start, current vertex and step counter. A graph with a nonempty closed walk contains a simple directed cycle of at most $N$ edges, including a self-loop if present. Thus the algorithm uses logarithmic space and is complete for the predicate.

For hardness, reduce the directed graph reachability problem to cycle detection. Form $G^{(N+1)}$ and add the single backward arcAll layering arcs advance exactly one layer, including the waiting arcs $(v,i)\to (v,i+1)$, so the layered graph alone is a Directed acyclic graph. Any cycle in the augmented graph must contain the backward arc and therefore contains a path from $(s,1)$ to $(t,N+1)$.

If $t$ is reachable from $s$ in $G$, use a simple path of length at most $N-1$ and pad it with waits to exactly $N$ steps. It becomes the required layered path and closes to a cycle. Conversely, projecting such a layered path and deleting waits gives a walk from $s$ to $t$ in $G$. This includes the case $s=t$, where reachability has a zero-length witness but the augmented graph has a genuinely positive-length cycle.

There are $N(N+1)$ vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only $O(\log N)$ bits. Hence this is a logspace many-one reduction, proving

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.

Let $\mathcal{D}=(x^{(1)},\dots ,x^{(n)})$ contain independent complete observations of the $p$-dimensional vector, and let $G$ be a Directed acyclic graph. A Gaussian Bayesian network uses, for node $j$,Here ${\alpha }_j$ is an intercept, ${\gamma }_j$ the vector of parent coefficients, and ${\sigma }_j^2>0$ the conditional variance; the vector ${\theta }_G$ collects these statistical parameters. Its likelihood function factors asChoose a proper statistical parameter prior distribution $\pi ({\theta }_G\mid G)$ and a graph prior distribution $\pi (G)$. Bayes' theorem gives the Bayesian network structure score, up to the normalization common to graphs,The integral is Bayesian model evidence: it averages over nuisance parameters rather than substituting their best-fitting values. A graph prior can favor sparse graphs, while the evidence balances fit against the amount of prior statistical parameter space that predicts the observations well. Compare these scores over admissible Directed acyclic graphs, using enumeration when feasible or a search procedure otherwise; search need not find a global maximum, and observational data need not identify a unique causal orientation.

A conjugate prior makes the integral analytic. For example, for ${\eta }_j=({\alpha }_j,{\gamma }_j)$ take ${\eta }_j\mid {\sigma }_j^2\sim N(m_j,{\sigma }_j^2{V}_j)$, ${\sigma }_j^2\sim \mathrm{IG}(a_j,b_j)$, where $V_j$ is positive-definite matrix and $a_j,b_j>0$; these are independent local normal-inverse-gamma priors. Under prior independence between nodes, the evidence is a product of local regression evidences. Each posterior has the same family, so the local integral is the ratio of prior and posterior normalization constants, with the likelihood's constants included. This avoids costly numerical integration and makes local graph updates inexpensive. Hyperparameters must be specified coherently if score equivalence between observationally equivalent graphs is desired; arbitrary local priors do not automatically have that property.

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.

The probabilistic graphical model is the following Directed acyclic graph. The shared hyperparameters lie outside the plate; the plate repeats the local variables for $s=1,\dots ,N$. The observed colour is shaded, and the known error variance $r_s$ is a square.

Thus the parent sets are $\boxed{\mathrm{pa}(C_s)=\{{\mu }_C,v\},\mathrm{pa}(E_s)=\{\tau \},\mathrm{pa}(o_s)=\{C_s,E_s,r_s\}}$. Independent hyperparameter prior factors are represented by the three root nodes. With the printed improper priors this is a factorization diagram; it becomes a normalized generative model after proper priors are supplied.

The Directed acyclic graph has arrowsThe roots $\lambda$ and ${\rho }_G$ are independent under their prior distributions; $N$ is fixed. Equivalently, the joint distribution factorizes as

Extend the original Directed acyclic graph withThe existing arrows $\lambda \to I\to Y_G$ and ${\rho }_G\to Y_G$ remain. The survey sample sizes and $N$ are fixed design variables, while ${\pi }_2$ is a deterministic node satisfying ${\pi }_2={\pi }_1+\lambda$.

A distribution is faithful to a Directed acyclic graph $G$ when every conditional independence in the distribution is implied by D-separation in $G$. Together with the graphical Markov property, faithfulness makes conditional independence equivalent to D-separation and rules out independences caused only by exact parameter cancellation.

Let $c_s={\tilde{c}}_s-E_s$ and $M_s={\tilde{M}}_s-R{E}_s$. With the stated improper hyperpriors, the unnormalized posterior density isIts Directed acyclic graph has, for each star, the arrowsfollowed by the deterministic observation arrowsThe latent variables $(c_s,M_s,E_s)$ are repeated inside a plate indexed by $s=1,\dots ,N$; all hyperparameters lie outside that plate.

For a distribution faithful to a Directed acyclic graph, the smallest Markov blanket of a vertex consists of

Conditioning on this set blocks every path from the vertex to all remaining vertices. Each listed neighbor is necessary under faithfulness of a directed acyclic graph: omitting a parent or child leaves its direct edge active, while omitting a child's other parent leaves the collider path through that conditioned child active. Faithfulness rules out accidental cancellations that could otherwise make a smaller blanket sufficient.

A density factorizes according to a Directed acyclic graph whenwhere $\mathrm{pa}(j)$ is the set of parents of vertex $j$.

The required undirected graph is the moral graph: join every pair of parents having a common child, retain the parent-child adjacencies, and remove all arrowheads. Each DAG family $\{j\}\cup \mathrm{pa}(j)$ is then a clique, so each conditional factor is a clique potential and the DAG factorization is also an undirected factorization. These edges are minimal for a guarantee covering every DAG-factorizing density, because an arbitrary conditional factor can couple every pair of variables in its family.

Initialize the PC skeleton search with an estimated conditional independence graph to reduce candidate pairs and conditioning sets. An exact graph contains the true Directed acyclic graph skeleton because it equals its moral graph under faithfulness. For initially absent pairs record the full complement as a separating set; an empty default can create false collider orientations. Estimation errors can affect this screening step.