Reichenbach's Common Cause Principle states that if two variables X and Y are correlated, then either X causes Y , or Y causes X, or there is a common hidden variable U that causes both. We focus on the three situations depicted in Figure 1, with the goal being to discover which of the three alternatives is true. If the causal structure is X -→ Y , then (X, Y ) is generated by the assignments: X := N X and Y := f Y (X, N Y ) where N X , N Y are independent random variables and f Y is some (deterministic) function. The roles of X and Y are interchanged if the structure is X ←-Y . If the causal structure is X ←-U -→ Y , then (X, Y ) is generated as: U := N U , X := f X (U , N X ), and Y := f Y (U , N Y ), where f X , f Y are functions and N X , N Y , N U are independent random variables. In this formalism, an intervention corresponds to setting one of the variables to a fixed value and examining the distribution of the other. For example, if the structure is X -→ Y and the intervention of fixing X to x is performed, then Y is generated as f Y (x, N Y ). We denote this intervention by do(X = x).
How would one distinguish between the three possibilities shown in Figure 1? Observationally, they are impossible to distinguish as the joint distribution of (X, Y ) may be exactly the same in all three cases. But a fundamental insight of Fisher (1925) was that they can be distinguished if interventions are allowed. For example, if the true causal structure was X -→ Y , then intervening on X should have an effect on Y , while intervening on Y should have no effect on X. The situation is vice versa for X ←-Y . On the other hand, if the causal structure was X ←-U -→ Y , intervention on neither X nor Y would affect the other.
In this work, we revisit the problem of recovering the correct causal structure from a quantitative point of view. While it is clear that a nonzero number of samples from inter-ventional distributions are necessary, what is the minimum number of such samples needed? More precisely, given m 1 , what is the minimum m 2 such that m 1 observations and m 2 samples from interventions suffice to distinguish between the possibilities in Figure 1? While there is a long line of work on causal structure learning while minimizing the number of experiments (e.g., Eberhardt (2007Eberhardt ( , 2008)); Hauser and Bühlmann (2012); Shanmugam et al. (2015); Kocaoglu et al. (2017); Greenewald et al. (2019); Squires et al. (2020)), most of these works ignore the issue of finite sample complexity that this work addresses.
We uncover a non-trivial tradeoff between m 1 and m 2 that shows that as the number of observations increases, we need fewer and fewer (but of course, positive) number of samples from interventions. Our study holds in the setting where X and Y are random variables over a finite domain of size k and are known to be "significantly correlated". For example, we show that if m 1 ∼ k c for 2/3 c 1, then m 2 ∼ k 1-c/2 samples are sufficient, while if m 1 is sufficiently large, m 2 can be completely independent of k. Furthermore, the tradeoffs we establish are nearly tight, in several interesting parameter regimes.
Organization We will define our problem statement in Section 1.1 and state our results precisely in Section 1.2. Related work will be discussed in Section 1.3. We present an overview of our technique in Section 1.4. Due to the page limit, we focus on the regime where m 1 = O(k) in the main paper and present the algorithm and lower bound in Section 2 and Section 3 respectively. We present detailed analysis of other regimes in the supplementary material.
We will work in the semantic framework of structural causal models (SCMs) (Pearl, 2009). Below we provide a complete formulation of the problem statement by tailoring SCMs to our setting.
Our goal is to test causal relationships between two correlated discrete random variables X and Y over a domain Σ of size k. We use a distance from independence as a notion of correlation below.
Definition 1 (TV-correlation). For discrete random variables X and Y define their total variation correlation as
where d TV (., .) is the total variation distance defined for any discrete distributions p and q over a domain Σ of size k as
Let X and Y be two correlated random variables with ρ TV (X, Y ) ε with a causal structure given in Figure 1. We are given access to two types of samples:
-Observational samples. These are draws from the joint distribution P [X, Y ].
-Interventional samples. We can intervene by setting X = x for some x ∈ Σ (resp. Y = y) and observe samples of Y (resp. X) under the intervention. We denote the interventional distribution as
and resp. as
Note the distinction between "intervention" and "interventional samples"; the former corresponds to fixing, say X, to a certain value x whereas the latter corresponds to drawing multiple samples from the interventional distribution
In practice, an intervention corresponds to setting up a certain medical trial and the number of interventional samples correspond to the number of people participating in the trial.
As discussed in the introduction, suppose we intervene do (X = x), if we are in Figure 1(a), the samples of Y we obtain satisfies
whereas if we are in Figure 1(b) or Figure 1(c) then we just obtain samples from P [Y ] as there is no causal influence from X to Y .
We now define our Causal Structure Identification problem.
Definition 2 (Causal Structure Identification). Suppose an SCM on two observable random variables X, Y supported over Σ of size k satisfies ρ TV (X, Y ) ε. Given m 1 observational and m 2 interventional samples, an algorithm solves Causal Structure Identification problem (CSI(k, ε)) if with probability at least 2/3, the algorithm outputs:
Note that while the above definition is for the case of constant probability, we can boost the success of our algorithms to 1 -δ for an arbitrary δ > 0 by the median trick, i.e., repeating a testing algorithm log (1/δ) times and outputting the median response which incurs only a logarithmic increase in the sample complexity.
Figure 2: An illustration of the tradeoffs between m 1 and m 2 for CSI(k, ε) for ε > 1/k 1/4 . The curves in bold are tight up to logarithmic factors. For ε < 1/k 1/4 , the curve is flat at
k/ε 2 until m 1 approaches k 2 /ε 2 and then becomes O 1/ε 2 . The x-axis is scaled such that all regimes of interest appear equal in length.
We provide sample complexity bounds for solving CSI(k, ε) with the number of interventional samples sublinear in k. The upper bounds we obtain have interesting phase transitions on the trade-offs between the number of interventional and observational samples in different regimes. We also show that the obtained upper bounds are tight when m 1 = O(k) and m 1 > k 2 /ε 2 . While our main tradeoffs are in terms of the interventional samples, we view it as a positive that the number of distinct interventions that our algorithms need is independent of the domain size.
Based on the number of observational samples available, we present our results in the following four regimes: (1) Zero (few) observational samples:
The bounds we obtain are shown in Figure 2. The above regimes are separated when ε 1/k 1/4 , which is the regime where interesting phase transitions happen. We note that all described results hold for all regimes of ε but regimes (1)-(3) will overlap and lead to the same sample for m 2 when ε < 1/k 1/4 . Zero (few) observational samples: m 1 = O(k 2/3 /ε 4/3 ).
Here we discuss the case when the number of observational samples is small. The next theorem shows that we can solve CSI(k, ε) with m 2 = O(k 2/3 /ε 4/3 ) even when the number of observational samples m 1 is zero.
Theorem 1.1. There exists an algorithm that uses zero observational samples and
Interestingly, as we will see in Theorem 1.3, the requirement on m 2 cannot be improved even when m 1 = Θ(k 2/3 /ε 4/3 ). This shows that the above interventional complexity is optimal.
Sublinear observational samples: m 1 = O(k). In this case, we show that the tradeoff between observational samples and interventional samples largely resembles the tradeoff for asymmetric closeness testing (see Definition 3) (Acharya et al., 2014a;Bhattacharya and Valiant, 2015;Diakonikolas and Kane, 2016;Diakonikolas et al., 2021). Theorem 1.2. When m 1 = Ω(k 2/3 /ε 4/3 ), there exists an algorithm that takes m 1 observational samples and
The algorithm we use relies on asymmetric closeness testing between conditional distributions P [Y | x] (or P [X | y]) and interventional distributions P x [Y ] (or P y [X]). While asymmetric closeness testing only deals with two distributions, the causal structure identification problem involves k conditional distributions and interventional distributions, which makes it trickier to handle. To resolve this, we use Levin's investment strategy (Levin, 1985;Goldreich, 2014) to select a sequence of conditional and interventional distributions to conduct closeness tests. See Section 1.4 for an overview of the technique.
We also prove a lower bound showing that the result is tight in the sublinear regime m 1 = O(k).
Theorem 1.3. For m 1 = Ω(k 2/3 /ε 4/3 ) and m 1 = O(k), any algorithm that takes m 1 observational samples must take m 2 = Ω(max(k/(
Superlinear observational samples: m 1 = Ω(k) and m 1 = O(k 2 /ε 2 ). In this regime, we obtain a sample complexity upper bound of O( √ k/ε 2 ), which doesn't improve as m 1 increases. The result follows immediately from Theorem 1.2 as the upper bound in Theorem 1.2 doesn't improve when m 1 > k. As we will see when m 1 is sufficiently large Ω(k 2 /ε 2 ), the interventional complexity can be further reduced. We leave improving the interventional complexity in the superlinear regime or proving hardness results as future work.
Sufficient observational samples: m 1 = Ω(k 2 /ε 2 ). In this regime, we have enough observational samples to get near-"perfect" estimates of P [Y ] and P
Hence the problem can be solved using simple hypothesis testing between
, there exists an algorithm that takes m 1 observational samples and m 2 = O(1/ε 2 ) interventional samples and solves CSI(k, ε). Moreover, the algorithm only needs to make one distinct intervention.
We also show that this simple hypothesis testing approach is optimal with the following lower bound, showing that increasing m 1 beyond k 2 /ε 2 does not help reducing the intervention complexity up to logarithmic factors.
Theorem 1.5. Any algorithm that solves CSI(k, ε) requires m 2 = Ω(1/ε 2 ) interventional samples.
Causal discovery from observational and experimental data has been subject to intense study, both from the potential outcomes (Rubin, 1974;Rosenbaum and Rubin, 1983) and the graphical model (Pearl, 2009) schools of causality. For the particular case of two variables, there is also a newer line of research (Peters et al., 2017) that constrain the mechanisms underlying parent-child relationships in the causal model, allowing the causal direction to be identifiable solely from observations. A high-level account of different approaches to learn the causal direction from observations can be found in Guyon et al. (2019). The effect of sample size on causal structure discovery has been empirically studied in several contexts Mooij et al. (2016). Compton et al. (2022) obtain finite-sample results for the two-variable system under the assumption of causal sufficiency and an assumption on the entropy of the exogenous variable. Wadhwa and Dong (2021) study the sample complexity of causal discovery with multiple nodes by applying finite-sample conditional independence testers Canonne et al. (2018) to the inferred causation algorithm Pearl and Verma (1991). Bello and Honorio (2018) study the sample complexity of causal discovery for discrete causal Bayesian networks but have a negative dependence on a parameter quantifying the minimal causal effect that can be arbitrarily small for our setting. With access to interventions Eberhardt et al. (2010) and Yang et al. (2018) experimentally demonstrated how the sample complexity affects structure learning. Both these studies compared perfect interventions (the notion used here) with soft interventions; in the future, we hope to extend our theory also to soft interventions.
Some of the techniques we use were developed in the context of distribution property testing; see Canonne (2020b) for an excellent survey. Specifically, we rely on existing work for the asymmetric closeness testing problem, where given sample access to two distributions p and q, the question is for a given m 1 number of samples from p, how many samples m 2 are required from q such that the hypothesis p = q can be distinguished from d TV (p, q) > ε with probability at least 2/3. The problem interpolates between the case when p is known (identity testing) and when p is not known (closeness testing). Sample complexity bounds for asymmetric closeness testing were first studied by Acharya et al. (2014b) who showed that it is sufficient to have
samples from q, where k is the size of the support of p and q. The relation between m 1 and m 2 was made tight by the work of Bhattacharya and Valiant (2015); Diakonikolas et al. (2021), where they showed that it is sufficient to have
, and that in fact, this is optimal.
Our setting is also related to the problem of testing against a collection of distributions Levi et al. (2013); Diakonikolas and Kane (2016), where given sample access to a collection of distributions p 1 , p 2 , . . . , p s , the goal is to test whether they are identical or there doesn't exist a distribution p such that (1/s)
Our algorithm for the zero observation case (Theorem 1.1) can be viewed as a modified version the algorithm proposed in Diakonikolas and Kane (2016) in the query model in the setting where the distribution mixture is not necessarily uniform.
In this section, we give an overview of our algorithms and the lower bound constructions. We will focus mostly on the sublinear regime where m 2 = O(k) as it exhibits the main intuition on how sublinear interventional complexity can be achieved. We briefly elaborate on the techniques employed in the zero(few) and sufficient observational samples cases and refer the reader to the supplementary material for details.
Our algorithm. Consider the testing problem of whether X -→ Y , which corresponds to Figure 1(a), or X -→ Y , which corresponds to Figure 1(b) and Figure 1(c). By symmetry, whether Y -→ X or Y -→ X can be distinguished similarly. By definition, the testing problem reduces to distinguishing the following two cases.
(1)
A naive algorithm would be to intervene on all x ∈ Σ and use existing techniques on asymmetric closeness testing to test whether
Clearly, this would result in a sample complexity at least linear in k. We resolve this issue by using different methods in two regimes: (1)
or not using existing algorithms on closeness testing. This shows that if τ is large, we see an informative element less often and it takes less samples to test. While if τ is small, we see an informative element more often but it also takes more samples to test. However, without knowing τ , it is hard to "invest" the right amount of samples to test P x [Y ] for each x. In the general case, we resolve this by using Levin's investment strategy (Lemma 1) which shows that it is sufficient to design a collection of τ 's that form a geometric sequence and do as well as if τ is fixed and known . The upper bound we obtain recovers the O(max{k/ε 2 √ m 1 , √ k/ε 2 }) rate similar to asymmetric closeness testing. See details in Section 2.
Lower bound construction. Our construction for m 1 = O(k) uses the lower bound construction of Bhattacharya and Valiant (2015) for asymmetric closeness testing as a primitive. They showed that there exist distributions p and q such that given access to O(m 1 ) samples from p any asymmetric closeness tester, requires Ω min
samples from q to distinguish p = q versus d TV (p, q). We construct q -, a slight modification of q, such that a uniform mixture of q and q -is p.
Using p, q, and q -we construct SCMs with marginal and conditional distributions as follows. For simplicity, we take X as a binary random variable while Y takes values from Σ. The marginal probabilities P [X = 0] = P [X = 1] are 1/2. The conditional distributions are P [Y | X = 0] = q and P [Y | X = 1] = q -, thus obtaining P [X, Y ]. Note that the marginal distribution P [Y ] is p by construction. Note that there exists two SCMs, under Figure 1(a) and Figure 1(c) that could generate P [X, Y ]. We show that it is impossible to distinguish these two figures using the available
To do this, we extend the wishful thinking theorem Valiant (2011) to distinguishing a collection of four distributions and show that their fourth-order moments are close. See Section 3 for details.
Again consider testing X -→ Y versus X -→ Y . We use a similar strategy as that of the sublinear observational samples algorithm with a modification. Instead of finding symbols to intervene by sampling x from P [X] to test whether
While we do not have access to the observational marginal P [X], if X -→ Y , we can instead simulate P [X] by sampling from P y [X] for an arbitrary y. Note that if X -→ Y , then the interventional distributions P x1 [Y ] and P x2 [Y ] are identical.
We show that a single intervention is sufficient when we observe Ω(k 2 /ε 2 ) observational samples. The crux of the algorithm in this regime is to identify the symbol to intervene upon. Assume that we want to test if X -→ Y or X -→ Y . By a similar reasoning as Section 1.4.1, we want to find a x ∈ Σ such that d
A folklore result states that for a discrete distribution of domain size k, the optimal sample complexity of estimating the distribution up to total variation distance ε is θ k ε 2 Canonne (2020a). Therefore, given Ω(k 2 /ε 2 ) samples from the joint distribution P [X, Y ], empirical estimates of the marginals are O(ε)-close in total variation distance. However, not all conditional distributions are guaranteed to be ε-close since it is possible that if P [X] is small enough, the number of samples to empirically estimate P [Y | X] might not be sufficient. We claim that there exists a symbol x * ∈ Σ such that with a high probability there are sufficient samples to obtain ε-close estimates of P [Y | X = x * ] and P [Y ] and ensure
Therefore, a simple hypothesis test with O 1/ε 2 samples from
2 Sublinear Observational Samples: Algorithm
Here we discuss trade-offs between m 1 and m 2 when m 1 is sublinear in k. We show Theorem 1.2 in this section, where we present an almost optimal algorithm that solves CSI(k, ε)
, a modification of this algorithm combined with further analysis results in Theorem 1.1, which is included in supplementary material.
The following lemma is critical to our analysis.
Lemma 1. Levin (1985); Goldreich (2014) Let D be a probability distribution, q : supp(D) → [0, 1], and ε ∈ (0, 1]. Suppose that E[q(s)] > ε, and let = log 2 (2/ε) .
Then, there exists j
Our algorithm uses the asymmetric closeness tester in Diakonikolas et al. ( 2021) as a primitive.
Definition 3 (Closeness Testing). Given sample access to unknown discrete distributions p and q over domain [k], a closeness tester CT (m 1 , m 2 , ε, δ) draws m 1 samples from p, m 2 samples from q and outputs "YES" if p = q and "NO" if d TV (p, q) > ε with probability atleast 1 -δ where ε, δ > 0.
Lemma 2 (Theorem 1.5 in Diakonikolas et al. (2021)). For discrete distributions p and q over [k], there exists a computationally efficient closeness tester CT (m 1 , m 2 , ε, δ) where m 1
Theorem 1.2. When m 1 = Ω(k 2/3 /ε 4/3 ), there exists an algorithm that takes m 1 observational samples and
)) interventional samples and solves CSI(k, ε). The number of distinct interventions the algorithm makes is O (1/ε) log 2 (1/ε) .
Proof. We analyze Algorithm 1 in two parts to prove the theorem. In the first part, we test whether X -→ Y or X -→ Y . If this test doesn't return X -→ Y , we move to the second part and use essentially the same steps to test Algorithm 1:
Input :ε > 0, sample access to
We apply Levin's investment strategy (Lemma 1), for the above choice of q. Let j := ( + 5 -j) 2 and s j := 2 j ε / ( j ) 2 . Lemma 1 guarantees the existence of j * ∈ [ ] such that:
Therefore, in 20/s j * samples from P [X], by Chernoff bound, with probability at least 1 -e -10 , there exists a sample x i that satisfies d
If X -→ Y , there exists j * ∈ [ ] and a sample x i that satisfies d
Consider the following test: for every j ∈ [ ], Algorithm 1 samples x i , 20/s j times from P [X] to distinguish
For n j 1 = Ω k 2/3 /2 -4j/3 and n j 2 = O(k/ n j 1 2 -2j ), each closeness test requires n j 1 samples from P [Y ] and n j 2 log(1/δ j ) samples from P x [Y ] to succeed with probability 1 -δ j . If any of the tests output "NO", then the algorithm returns X -→ Y .
Test whether Y -→ X or Y -→ X. If all tests return "YES" then with a high probability, X -→ Y and the algorithm proceeds to distinguish Y -→ X and Y -→ X using the same steps as before. Similar to the previous part, each individual test requires n j 1 samples from P [X] and n j 2 log(1/δ j ) samples from P y [X] to succeed with probability 1 -δ j . The algorithm returns Y -→ X if one of the tests outputs "NO". If all tests return "YES", then the algorithm returns
, and hence all of the previous closeness tests are "YES" instances.
Similarly, the total number of interventional samples taken by the algorithm in the first stage is
Error analysis. Now we analyze the error probability. The total number of tests performed is at most O j=1 (20/s j ) . Hence by union bound the probability of failure of these tests is at most
When X -→ Y , the probability of the algorithm failing to find a sample x satisfying d TV (P x [Y ], P [Y ]) > 2 -j is at most 1/300. The analysis is the same for graph X ←-Y . Hence the algorithm returns the correct graph with error probability at most 1/150.
taken by the algorithm is upper bounded by the number of x i 's and y i 's drawn, which is:
3 Sublinear Observational Samples: Hardness
We now prove Theorem 1.3, which establishes an almost optimal lower bound on the tradeoff between m 1 and m 2 when m 1 is O (k), through a reduction to canonical results on property testing. We construct causal models under different structures (see Figure 1) with the same observational distribution. We base our construction on the hard instance for asymmetric closeness testing in Bhattacharya and Valiant (2015).
For testing causal models, extra care is needed to prove hardness since the adversary has sample access to multiple interventional distributions. To handle this, we extend Valiant (2008Valiant ( , 2011))'s wishful thinking theorem (see Theorem 4.6.9 in Valiant (2008)) which distinguishes two distribution pairs to the case of distinguishing two distribution quadruplets. While the extension is immediate, we remark that the constants become much larger for the quadruplet case. For completeness, we state the extension below and defer the proofs to the supplementary material.
For the rest of this section we denote the sequence x 1 , x 2 , x 3 , x 4 by x 1:4 . Definition 4. For integers n 1:4 > 0, the (n 1:4 )-based moment m (a 1:4 ) of the distribution quadruplet (p 1:4 ) is defined as m(a 1:4 ) :=
Proposition 1. Given integers n 1:4 > 0, and two distribution quadruplets p + 1:4 and p - 1:4 , where p + i , p - i have frequencies at most 1 cni , for constant c > 0. If m + and m - are the (n 1:4 )-based moments of p - 1:4 and p - 1:4 respectively that satisfy
for some constant c > 0, then p - 1:4 cannot be distinguished from p - 1:4 with probability greater than 0.5 using a tester that takes Poi(n i ) samples from p + i , p - i for each i ∈ [4].
Theorem 1.3. For m 1 = Ω(k 2/3 /ε 4/3 ) and m 1 = O(k), any algorithm that takes m 1 observational samples must take m 2 = Ω(max(k/(
Proof Sketch. We present a proof sketch and defer the details to the supplementary material. Some definitions. Let π be a permutation of [k] chosen uniformly at random. Let A = {π(1), π(2), . . . , π(a)} and B = {π(a + 1), π(a + 2), . . . , π(a + b)} be disjoint subsets of [k] of size a = (3/4)m 1 and b = k/C, where C is a constant. For S ⊆ [k], let 1 S be the indicator function of set S. For permutation π, define distributions p, q and q - over [k] as following:
Construction. Consider an SCM on variables X and Y over support {0, 1} and [k] resp. with 1. X ∼ Bernoulli (0.5)
Note that ρ TV (X, Y ) = ε because each pair of the three distributions p, q, q -has TV distance ε and the marginal distribution P [Y ] is p.
for a sufficiently small c. Let p + 1:4 := (q, q -, p, p) and p - 1:4 := (q, q -, q, q -). Suppose, for contradiction, there exists an algorithm A that solves CSI(k, ε) that uses n 1 observational samples and n 3 interventional samples. A single sample from each of the two conditionals simulates one sample of P [X, Y ]. Hence, we consider quadruplets of the form
). It is sufficient to show that p + 1:4 cannot be distinguished from p - 1:4 with probability greater than 0.5 by any tester that takes Poi(n i ) samples from p + i , p - i . We show this in the supplementary material by bounding the difference in moments
for the choices of n 1 , n 2 , n 3 , n 4 , which by Proposition 1 prove the theorem.
We view our work as the first to provide finite sample complexity guarantees for the simplest causal structure identification problem, namely categorical two-variable systems. We parameterize the system using a quantitative notion of correlation between the two variables and quantify the tradeoff between observational and interventional data. Our sample complexity bounds on interventional samples, m 2 , as a function of observation samples, m 1 , exhibit interesting phase transitions and are tight when m 1 , as a function of the domain size k, is either sublinear O(k) or sufficient Ω k 2 /ε 2 . In addition the number of interventional samples is always sublinear in k.
There are several directions for future work. The most immediate is improving upon the sample complexity of the superlinear regime and proving hardness results for the same. While the simplest property testing algorithms have only recently been studied for synthetic data Gupta and Price (2022), validating our proposed algorithms on real-world data is an important next step.
Jayadev Acharya and Saravanan Kandasamy are supported in part by the grant NSF-CCF-1846300 (CAREER), and a fellowship from Google. Sourbh Bhadane is supported by grants NSF-CCF-1846300 (CAREER) and NSF-CCF-1934985. Arnab Bhattacharyya is supported in part by an NRF Fellowship for AI, and part of this work was done while he was visiting the Simons Institute for the Theory of Computing.
Here we look at the case when the number of observational samples m 1 is small. The algorithmic strategy is similar to the one discussed in Section 2 for sublinear observations. For Algorithm 1 because we had access to a large number of observational samples, we were able to estimate the marginals P [X] and P [Y ] and test if the marginals are far from interventions. Since m 1 is small here, we may not have access to the marginals. The idea here is to check if there exists interventions that are far apart, which is aided by the following lemma.
Lemma 3. Let X and Y be two random variables with joint distribution P [X, Y ] such that ρ TV (X, Y ) ε. Then,
Proof.
(By Jensen's inequality)
Similarly, Let
We now use this result prove that CSI(k, ε) can be solved using O k 2/3 /ε 4/3 samples from interventions even with zero samples from observations. Theorem 1.1. There exists an algorithm that uses zero observational samples and m 2 = O max(k 2/3 /ε
Because ρ TV (X, Y ) ε, by Lemma 3, we get,
We apply Levin's investment strategy (Lemma 1), for the above choice of q. Therefore, there exists j * ∈ [ ] such that:
where s(j) := (2 j ε)/( + 5 -j) 2 , for all j ∈ [ ]. For such j * , if we sample (x 1 , x 2 ) from (P [X], P [X]), 20/s(j * ) times, by Chernoff bound, with probability at least 1 -e -10 , there exists (x 1 , x 2 ) in the samples satisfying,
Part I. The first half of the algorithm considers testing whether X -→ Y or X -→ Y . ) is zero versus greater than 2 -j , with probability 1 -δ j , is
Hence, with probability 1 -e -10 , there exists j * ∈ [ ] and a sample (x 1 , x 2 ) that satisfies
For
We now analyze the total number of interventional samples. Let t (j) = ( + 5 -j). The total number of samples taken from interventions to perform the closeness tests in each part is:
Error Analysis. The total number of tests performed at Part I is at most O j=1 s j where s(j) = 20( + 5 -j) 2 /2 j ε. Hence, by union bound, the probability of failure of these tests is at most
Similarly, for Part II, the error probability of the algorithm is at most 1/300. Hence the algorithm returns the correct graph with error probability at most 1/150.
Here we analyze the tradeof between m 1 and m 2 when m 1 is Ω k 2 /ε 2 . We show that O(1/ε 2 ) interventional samples are sufficient and necessary to solve CSI(k, ε).
). First we prove a claim that assures the existence of x ∈ Σ such that we get sufficient samples on X = x and also τ x is small. Claim 1. With probability at least 2/3, there exists x ∈ [k] such that:
(3) Also,
Combining Equations ( 3) and (4),
x P (x) (τ x ) 2 1 {τx>ε/10} > 99ε 2 /100.
Hence, there exists x ∈ [k] that satisfies (i) τ x ε 10 and
Applying Chernoff bound,
.
(For any C > 5.)
This proves the claim. We also have the following: Hardness. Next we show that even with infinite samples from observations, it requires at least Ω 1/ε 2 samples from interventions to solve CSI(k, ε).
Let P denote the set of all distributions P : [k] → [0, 1] of the form
where z i is either -1 or +1. Let q 0 be uniformly chosen at random from P. Let q 1 be the distribution obtained from q 0 by swapping the probabilities of odd and even coordinates (i.e., q 1 (2i) = q 0 (2i -1) and q 1 (2i -1) = q 0 (2i)).
Let the marginal distribution P [X] be P [X = 0] = P [X = 1] = 1/2 and the conditional distributions be P [Y | X = i] = q i . Here E [d TV (unif(k), q i )] > ε. Also the marginal P [Y ] is unif[k] because (1/2) q 0 + (1/2)
Acharya, Bhadane, Bhattacharyya, Kandasamy, Sun
See(Valiant and Valiant,
2011, Theorem 3 and 4) for a constant probability version and the small error probability can be obtained using the boosting trick.