We show that if any number of variables are allowed to be simultaneously and
independently randomized in any one experiment, log2(N) + 1 experiments are
sufficient and in the worst case necessary to determine the causal relations
among N >= 2 variables when no latent variables, no sample selection bias and
no feedback cycles are present. For all K, 0 < K < 1/(2N) we provide an upper
bound on the number experiments required to determine causal structure when
each experiment simultaneously randomizes K variables. For large N, these
bounds are significantly lower than the N - 1 bound required when each
experiment randomizes at most one variable. For kmax < N/2, we show that
(N/kmax-1)+N/(2kmax)log2(kmax) experiments aresufficient and in the worst case
necessary. We over a conjecture as to the minimal number of experiments that
are in the worst case sufficient to identify all causal relations among N
observed variables that are a subset of the vertices of a DAG.

利用随机化实验，可在没有潜在变量、样本选择偏差和反馈循环的情况下，确定 N 个变量之间的因果关系，最多需要 log2 (N) + 1 次实验，而当每个实验同时随机化 K 个变量时，我们提供了实验数量的上界，并且发现这个上界比每次随机化最多一个变量时的上界要低得多。并且，我们提供了在满足 kmax < N/2 的情况下，确定 N 个观察变量的因果关系所需的最小实验次数。

识别 N 个变量间所有因果关系的实验数在最坏情况下的充分必要性

On the Number of Experiments Sufficient and in the Worst Case Necessary  to Identify All Causal Relations Among N Variables

Pearl and Dechter (1996) claimed that the d-separation criterion for
conditional independence in acyclic causal networks also applies to networks of
discrete variables that have feedback cycles, provided that the variables of
the system are uniquely determined by the random disturbances. I show by
example that this is not true in general. Some condition stronger than
uniqueness is needed, such as the existence of a causal dynamics guaranteed to
lead to the unique solution.

本文旨在反驳 Pearl 和 Dechter（1996）提出的基于 d - 分离准则的有向无环因果网络的条件独立性也适用于存在反馈循环的离散变量网络（前提是系统的变量由随机干扰确定），我通过示例说明通常情况下这并不成立，需要更强的条件，如存在可以保证唯一解的因果动态。