N-1 Experiments Suffice to Determine the Causal Relations Among N Variables

By combining experimental interventions with search procedures for graphical causal models we show that under familiar assumptions, with perfect data, <em>N</em> - 1 experiments suffice to determine the causal relations among <em>N</em> > 2 variables when each experiment randomizes at most one variable. We show the same bound holds for adaptive learners, but does not hold for <em>N</em> > 4 when each experiment can simultaneously randomize more than one variable. This bound provides a type of ideal for the measure of success of heuristic approached in active learning methods of casual discovery, which currently use less informative measures.