M-separation
Encyclopedia
In statistics
, m-separation is a measure of disconnectedness in ancestral graph
s and a generalization of d-separation for directed acyclic graph
s. It is the opposite of m-connectedness.
Suppose G is an ancestral graph. For given source and target nodes s and t and a set Z of nodes in G\{s, t}, m-connectedness can be defined as follows. Consider a path
from s to t. An intermediate node on the path is called a collider if both edges on the path touching it are directed toward the node. The path is said to m-connect the nodes s and t, given Z, if and only if:
If s and t cannot be m-connected by any path satisfying the above conditions, then the nodes are said to be m-separated.
The definition can be extended to node sets S and T. Specifically, S and T are m-connected if each node in S can be m-connected to any node in T, and are m-separated otherwise.
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, m-separation is a measure of disconnectedness in ancestral graph
Ancestral graph
An ancestral graph is a graph with three types of edges: directed edge, bidirected edge, and undirected edge such that it can be decomposed into three parts: an undirected subgraph, a directed subgraph, and directed edges pointing from the undirected subgraph to the directed subgraph.An ancestral...
s and a generalization of d-separation for directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
s. It is the opposite of m-connectedness.
Suppose G is an ancestral graph. For given source and target nodes s and t and a set Z of nodes in G\{s, t}, m-connectedness can be defined as follows. Consider a path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
from s to t. An intermediate node on the path is called a collider if both edges on the path touching it are directed toward the node. The path is said to m-connect the nodes s and t, given Z, if and only if:
- every non-collider on the path is outside Z, and
- for each collider c on the path, either c is in Z or there is a directed path from c to an element of Z.
If s and t cannot be m-connected by any path satisfying the above conditions, then the nodes are said to be m-separated.
The definition can be extended to node sets S and T. Specifically, S and T are m-connected if each node in S can be m-connected to any node in T, and are m-separated otherwise.