A Discovery Algorithm for Directed Cyclic Graphs
  Directed acyclic graphs have been used fruitfully to represent causal
strucures (Pearl 1988). However, in the social sciences and elsewhere models
are often used which correspond both causally and statistically to directed
graphs with directed cycles (Spirtes 1995). Pearl (1993) discussed predicting
the effects of intervention in models of this kind, so-called linear
non-recursive structural equation models. This raises the question of whether
it is possible to make inferences about causal structure with cycles, form
sample data. In particular do there exist general, informative, feasible and
reliable precedures for inferring causal structure from conditional
independence relations among variables in a sample generated by an unknown
causal structure? In this paper I present a discovery algorithm that is correct
in the large sample limit, given commonly (but often implicitly) made plausible
assumptions, and which provides information about the existence or
non-existence of causal pathways from one variable to another. The algorithm is
polynomial on sparse graphs.
