My stuff
A New Measure of Conditional Dependence

Measuring conditional dependencies among the variables of a network is of great interest to many disciplines. This paper studies some shortcomings of the existing dependency measures in detecting direct causal influences or their lack of ability for group selection to capture strong dependencies and accordingly introduces a new statistical dependency measure to overcome them. This measure is inspired by Dobrushin’s coeffi-cients and based on the fact that there is no dependency between X and Y given another variable Z, if and only if the conditional distribution of Y given X = x and Z = z does not change when X takes another realization  x′while Z takes the same realization z. We show the advantages of this measure over the related measures in the literature. Moreover, we establish the connection between our measure and the integral probability metric (IPM) that helps to develop estimators of the measure with lower complexity compared to other relevant information theoretic based measures. Finally, we show the performance of this measure through numerical simulations.

Identifying the conditional independencies (CIs) among the variables or processes in a systems is a fundamental problem in scientific investigations in different fields such as biology, econometric, social sciences, and many others.

In probability theory, two events X and Y are conditionally independent given a third event Z, if the occurrence or nonoccurrence of X and Y are “independent” events in their conditional probability distribution given Z (Gorodetskii, 1978). There are several CI measures in literature that have been developed for different applications to capture such independency. For instance, the most commonly used one is conditional mutual information (CMI) (Gorodetskii, 1978) that is an information theoretical quantity. This measure has been used in different fields such as communication engineering, channel coding (Cover and Thomas, 2012), and causal discovery (Spirtes et al., 2000b). CMI between X and Y given Z is defined by comparing two conditional distributions: P(X|Y, Z) and P(X|Z) using KL-divergence and then taking average over the conditioning variable Z. Hence, it is limited to those realizations with positive probability (see Section 4.1). One shortcoming of such measure is that it cannot capture CIs that occur rarely or even over zero measure sets. Another shortcoming of this measure is that it is symmetric and thus it fails to encode asymmetric dependencies such as causal directions in a network.

Most of the conditional dependency/independency measures are defined similar to the CMI in a sense that they take average over the conditioning variables. Kernel-based method in (Zhang et al., 2011) is another example. Consequently, such measures may fail to distinguish the range of the conditioning variable Z in which the dependency between the variables of interest X and Y is more clearer. For example, consider a treatment that has different effects on a special disease for different genders. There are scenarios in which the previous CI measures (e.g., CMI) fail to identify for which gender the effect of the treatment on the disease is maximized (see Section 4.3).

Discovering the causal relationships in a network is one of the main applications for CI measures (Spirtes et al., 2000b). In this area, it is important to capture the direct causal influence between two variables in a network independent of the other causal indirect influences between them. As we will show in Section 4.2, previous CI measures (e.g., CMI) cannot capture the direct causal influ-ences between two variables (cause and effect) in a network when some variables in the indirect causal path depend on the cause almost deterministically.

The main contribution of this paper is the introduction of a statistical metric inspired by Dobrushin’s coefficient (Dobrushin, 1970) to measure the dependency/independency between X and Y given Z in a network from their realizations. Our metric has been developed based on the paradigm that if Y has no dependency on X given Z, then the conditional distribution of Y given X = x and Z = z will not change if x varies and Z takes the same realization z. We will show that this dependency measure overcomes the aforementioned limitations. Moreover, we will establish the connection between our meausre and the IPM to develop estimators for our metric with lower complexity compared to other relevant information-theoretic based measures such as CMI. This is because the proposed estimators depend on the sample points only through the metric of the space, and thus its complexity is independent of the dimension of the samples.

Perhaps the best known paradigm for visualizing the CIs among the variables of a network is Bayesian networks (Pearl, 2003). They are directed acyclic graphs (DAGs) in which nodes represent random variables and directed edges denote the direction of causal influences. Analogously, using the dependency measure in this work, we can represent the causal structure of a network via a DAG that possesses the same properties as the Bayesian networks.

It is also worth mentioning that there exist several measures to capture CIs and the causal influences among time series, for instance, transfer entropy (Schreiber, 2000) and directed information (Massey, 1990). Measuring the reduction of uncertainty in one variable after knowing another variable is the key idea in such measures. Because these measure are defined based on CMI, they also suffer the aforementioned limitations. Note that the proposed measure can easily be modified to capture such influences in time series as well.

In this Section, we review some basic definitions and our notation. Throughout this paper we use capital letters to represent random variables, lowercase letters to denote a realization of a random variable, and bold capital letters to denote matrices. We denote a subset of random variables with index set  K ⊆ [m], where [m] := {1, ..., m} by  XKand [m] \ {j} by  −{j}.

In a directed graph −→G = (V, −→E ), we denote the parent set of a node  i ∈ Vby  Pai := {j : (j, i) ∈ −→E }, and denote the set of its non-descendant1 by  Ndi. We use  X ⊥⊥ Y |Zto denote X and Y are independent given Z.

Bayesian Network: A Bayesian network is a graphical model that represents the conditional independencies among a set of random variables via a directed acyclic graph (DAG) (Spirtes et al., 2000b). A set of random variables Xis Bayesian with respect to a DAG −→G, if


Up to some technical conditions (Lauritzen, 1996), this factorization is equivalent to the causal Markov condition. Causal Markov condition states that a DAG is only acceptable as a possible causal hypothesis if every node is conditionally independent of its non-descendant given its parents.

Corresponding DAG of a joint distribution possesses Global Markov condition if for any disjoint set of nodes A, B, and C for which A and B are d-separated2 by C, then  XA ⊥⊥ X

B|XC. It is shown in (Lauritzen, 1996) that causal Markov condition and Global Markov condition are equivalent.

Faithfulness: A joint distribution is called faithful with respect to a DAG if all the conditional independence (CI) relationships implied by the distribution can also be found from its corresponding DAG using d-separation and vice versa3 (Pearl, 2014). It is possible that several DAGs encode the same set of CI relationships. In this case, they are called Markov equivalence.

As we mentioned earlier, we use the following paradigm to define our measure of independency: if Y has no dependency on X given Z, then the conditional distribution of Y given X = x and Z = z should not change when X takes different realization  x′while Z takes the same realization z. This paradigm is similar in nature to Pearl’s paradigm of causal influence (Pearl, 2003). He proposed that the in-fluence of a variable (potential cause) on another variable (effect) in a network is assessed by assigning different values to the potential cause, while other variables’ effects are removed, and observing the behavior of the effect variable. Below, we formally introduce our dependency measure.

Consider Xa collection of m random variables. In order to identify the dependency of  Xion  Xj, we select a set of indices K, where  K ⊆ −{i, j}and consider the following two probability measures:


where  xK∪{j}and  yK∪{j} ∈ E|K|+1are two realizations for  XK∪{j}that are the same every where except at  Xj. Further, assume  xK∪{j}at position  Xjequals x and  yK∪{j}equals  y (y ̸= x) at this position. If there exists a subset K ⊆ −{i, j}such that for all such realizations,  µi(xK∪{j})and  µi(yK∪{j})are the same, then we say  Xihas no depen- dency on  Xj. This is analogous to the conditional independence that states if  Xjand  Xiare independent given some XK, then there is no causal influence between them. Note that using mere observational data, comparing the two conditional probabilities in (2) reveals the dependency between Xiand  Xj. However, when interventional data is available, we can identify whether  Xjcauses  Xi, i.e., the direction of influence.

In order to compare the two probability measure in (2), a metric on the space of probability measures is required. There are several metrics that can be used such as KLdivergence, total variation, etc (Gibbs and Su, 2002). For instance, using the KL-divergence will lead to develop CI test-based approaches (Singh and Valtorta, 1995). In this work, we use Wasserstein distance and discuss the advantage of using such metric in Section 5.1.

Definition 1. Let (E, d) be a metrical complete and separable space equipped with the Borel field B, and let M be the space of all probability measures on (E, B). Given ν1, ν2 ∈ M, the Wasserstein metric between  ν1, ν2is given by  Wd(ν1, ν2) := infπ (Eπ[d(x, y)]), where the infimum is taken over all probability measures  πon  E × Esuch that its marginal distributions are  ν1and  ν2, respectively.

Using the above distance, we define the dependency of  Xion  Xjgiven  K ⊆ −{i, j}as follows:


The suprimum is over all realizations  xK∪{j}and  yK∪{j}that only differ at the jth variable. Moreover, we assume  xK∪{j}at jth position equals x and y

K∪{j}equals y (y ̸= x) at this position. When  K = −{i, j}, cKi,jis called Dobrushin’s coefficient (Dobrushin, 1970). Similarly, we define the dependency of a set of nodes B on a disjoint set A given K, where  K ∩ (A ∪ B) = ∅, as follows,


Remark 1. An alternative way of interpreting the above measure is via an equivalent network in which all the nodes in the set  K ∪ {j}are injected with independent inputs that have distributions equal to their marginals, i.e., node k is injected with an independent random variable that has distribution  P(Xk). In this equivalent network, the dependency of i on j given K can be expressed by


Clearly, this expression is bounded above by (3).

3.1. Maximum Mean Discrepancy

Using a special case of the duality theorem of Kantorovich and Rubinstein (Villani, 2003), we obtain an alternative approach for computing the Wasserstein metric as follows:


where  FLis the set of all continuous functions satisfying the Lipschitz condition: ||f||Lip := supx̸=y |f(x) −f(y)|/d(x, y) ≤ 1.This representation of the Wasserstein metric is a special form of integral probability metric (IPM) (M¨uller, 1997) that has been studied extensively in probability theory (Dudley, 2002) with applications in empirical process theory (Van Der Vaart and Wellner, 1996), transportation problem (Villani, 2003), etc. IPM is defined similar to (5) but instead of  FL, the suprimum is taken over a class of real-valued bounded measurable functions on E.

One particular instance of IPM is maximum mean discrepancy (MMD) in which the suprimum is taken over FH := {f : ||f||H ≤ 1}. More precisely, MMD is de-fined as


Here, H represents a reproducing kernel Hilbert space (RKHS) (Aronszajn, 1950) with reproducing kernel  k(·, ·). MMD has been used in statistical applications such as independence testing and testing for conditional independence (Gretton et al., 2007; Fukumizu et al., 2007; Sun et al., 2007).

It is shown in (Gretton et al., 2006) that when H is a universal RKHS (Micchelli et al., 2006), defined on the compact metric space E, then MMD(ν1, ν2) = 0if and only if ν1 = ν2. In this case, MMD can also be used to compare the two conditional distributions in (2). This is because, MMD(µi(xK∪{j}), µi(yK∪{j})) = 0implies that the two conditional distributions are the same. This allows us to define a new dependency measure which we denoted it by ˜cKi,jsimilar to (3) that uses MMD instead of Wasserstein distance. It is straight forward to show that this measure has similar properties as the one in (3). The main difference between these two measures is their estimation method that we discuss in Section 5.1.

Herein, we discuss the advantages of our measure over other dependency measures in the literature.

4.1. Mutual Information and Information Flow

Conditional mutual information is an information theoretic measure that has been used in the literature to identify the conditional independence structure of a network. This measure compares two probability measures P(Xi|Xj, XK)and  P(Xi|XK)using the KL-divergence as follows,


This measure is symmetric and hence it cannot capture the direction of influence. Moreover, it only compares the probability measures over all pairs  (Xi, Xj)that have positive probability. Note that any other measures in the literature that is based on conditional independence test such as the kernel-based methods in (Sun et al., 2007; Zhang et al., 2011) have the similar limitation.

Example 1. Consider a network of two variables X and Y , in which  X ∼ N(0, 1)is a zero mean Gaussian variable and Y is N(0, 1) whenever X is a rational number and N(1, 2) otherwise. In this network, Y is dependent on X but it cannot be captured using CI. This is because I(X; Y ) = 0. On the other hand, we have  cy,x > 0and cx,y = 0.

Another quantity that has been introduced in the literature to quantify causal influences in a network is information flow (Ay and Polani, 2008). This quantity is defined using Pearl’s do-calculus (Pearl, 2003). Intuitively, operating do(xi)removes the dependencies of  Xion its parents, and replaces  P(Xi|XP ai)with the delta function. Herein, to give an interpretation on how (3) can be used to identify causal relationships that are defined in terms of intervention, we compare our measure with information flow.

Below, we introduce the formal definition of information flow from  XAto X

K, I(XA →XB|do(X


This is defined analogous to the conditional mutual information in (7). But unlike the conditional mutual information, the information flow is defined for all pairs  (xA; xC)rather than being limited to those with positive probability (similar to our measure). Similar measures are introduced in (Janzing et al., 2013; Ay and Krakauer, 2007) which are also based on do-calculation. Analogously, we can define our measure based on do-operation in order to capture the direction of causal influences in a network by substituting the conditional distributions in (2) with their do versions.

Because the Wasserstein metric can be estimated using a linear programming (see Section 5.1), our measure has computational advantages over the information flow or other similar measures that uses KL-divergence. Another advantage of (3) over the information flow is that it requires less number of interventions in case of using interventional data. More precisely, calculating (8) requires at least two do-operations  (do(xA∪K)and  do(xK))but (3) re- quires only one  (do(xK∪{j})). Moreover, as the next ex- ample shows, unlike our measure, the information flow depends on the underlying DAG.

Example 2. Consider a network of three binary random variables {X, Y, Z} with  Z = X ⊕ Yan XOR. Suppose the underlying DAG of this network is given by Figure 1(b), in which X takes zero with probability b. In this case, I(X → Z|do(Y )) = H(b), where H denotes the entropy4. However, if the underlying DAG is given by Figure 1(a), we have  I(X → Z|do(Y )) = H(ǫ). Now, consider a scenario in which  ǫtends to zero. In this scenario, both DAGs describe a system in which X = Y and Z = 0. However, in (b), we have  I(X → Z|do(Y )) = H(b) > 0, while in (a),  I(X → Z|do(Y )) → 0. But  cyz,xin both DAGs is independent of  ǫand it is positive.

4.2. A Better Measure for Direct Causal Influences

Consider a network comprises of three random variables {X, Y, Z}, in which  Y = f(X, W1)and Z = g(X, Y, W2), such that the transformations from  (X, W1)to (X, Y ) and from  (X, Y, W1)to (X, Y, Z) are invertible and  W1and  W2are independent exogenous noises. In other words, there exist functions  φand  ϕsuch that W1 = φ(X, Y )and  W2 = ϕ(X, Y, Z). Furthermore, f is an injective function in its first argument, i.e., if  f(x1, w) =f(x2, w)for some w, then  x1 = x2.

In order to measure the direct influence from X to Z, one may compute the conditional mutual information between


Figure 1. DAGs for which information flow fails to capture the influence.

X and Z given Y , i.e., I(X; Z|Y ). However, this is not a good measure because as the dependency of Y on X grows, i.e.,  H(Y |X) → 0, then  I(X; Z|Y ) → 0. This can be explained by the fact that as H(Y |X) goes to zero, in other words, as  PW1tends to  δw0(W1)for some fixed value  w0, then by specifying the value of X, the ambiguity about the value of Y will go to zero. Thus, using the injective property of f, it is straight forward to see that  I(X; Z|Y ) → 0.

This analysis shows that I(X; Z|Y ) fails to capture the direct influence between X and Z when Y depends on X almost in a deterministic manner. However, looking at  cyz,x, we have


where  Px,y(Z) := PW2(ϕ(x, y, Z))| ∂g∂W2 (x, y, ϕ(x, y, Z))|−1.This distribution depends only on realizations of (X, Y ) and it is independent of  PX,Y. Hence, changing the dependency between X and Y will not affect  cyz,x, which makes it a better candidate to measure the direct influences between variables of a network. As an illustration, we present a simple example. But first, we need the following result.

Theorem 1. Consider

diagonals and its support represents a DAG.W is a vector of zero mean independent random variables. Then, cP ai\{j}i,j = |Ai,j|.

Example 3. Consider a network of three variables {X, Y, Z} in which  Y = aX + W1and Z = bX + cY + W2for some non-zero coefficients {a, b, c} and exogenous noises  {W1, W2}. Hence,


As we mentioned earlier, by reducing the variance of  W1, the first term in (9) tends to  H(bX + W2|X) = H(W2). Hence, (9) goes to zero. But, using the result of Theorem 1, we have  cyz,x = |b|, which is independent of the variance of W1.

4.3. Group Selection for Effective Intervention

Consider a network of three variables {X, Y, C} in which C is a common cause for X and Y , and X influences Y . In this network, to measure the influence of X on Y , one may consider P(Y |do(X)) that is given by �c P(Y |X, c)P(c) =Ec[P(Y |X, c)]. See, e.g., the back-door criterion in (Pearl, 2003). This conditional distribution is an average over all possible realizations of the common cause C.

Consider an experiment that is been conducted on a group of people with different ages C in which the goal is to identify the effect of a treatment X on a special disease Y . Suppose that this treatment has clearer effect on that disease for elderly people and less obvious effect for younger ones. In this case, averaging the effect of the treatment on the disease for all people with different ages, i.e., P(Y |do(X)) might not reveal the true effect of the treatment. Hence, it is important to identify a regime (in this example age range) of C in which the influence of X on Y is maximized. As a consequence, we can identify the group of subjects on which the intervention is effective.

Note that this problem cannot be formalized using do-operation or other measures that take average over all possible realizations of C. However, using the measure in (3), we can formulate this problem as follows: given X = x and two different realizations for C, say c and  c′, we obtain two conditional probabilities P(Y |x, c) and  P(Y |x, c′). Then, we say in group C = c, the causal influence between X and Y is more obvious compare to the group  C = c′, if given C = c, changing the assignments of X leads to larger variation of the conditional probabilities compared to changing the assignment of X given  C = c′. More precisely, if  cC=cy,x ≥ cC=c′y,x, where


Note that  ccy,x = supc cC=cy,x, where  ccy,xis given in (3). Us- ing this new formulation, we define the range of C in which the influence from X to Y is maximized as  arg maxc cC=cy,x.

Example 4. Suppose that  Y = CX+W2and  X = W1/C, where C takes value from {1, ..., M} w.p.  {p1, ..., pM}and Wi ∼ N(0, 1). In this case, we have  cC=cy,x = |c|. Thus, C = M will show the influence of X on Y more clearer. On the other hand, such property cannot be detected using other measures. For example, we have I(X; Y |C = c) = 0.5 log(2), for all c.

Lemma 1. The measure defined in (3) possesses the following properties: (1) Asymmetry: In general  cKi,j ̸= cKj,i. (2)  cKi,j ≥ 0and when it is zero, we have  Xi ⊥⊥ Xj|XK. (3) Decomposition:  cKi,{j,k} = 0implies  cKi,j =cKi,k =0. (4) Weak union: If  cKi,{j,k} = 0, then  cK∪{k}i,j = cK∪{j}i,k = 0. (5) Contraction: If  cKi,j = ci,K = 0, then  ci,K∪{j} = 0. (6) Intersection: If  cK∪{k}i,j = cK∪{j}i,k = 0, then  cKi,{j,k} = 0.

Note that unlike the intersection property of the conditional independence, which does not always hold, the intersection property of the dependency measure in (3) always holds. This is due to the fact that (3) is defined for all realizations (xj, xK)not only those with positive measure. See Exam- ple 1 for the asymmetric property of  cKi,j.

We say a DAG possesses global Markov property with respect to (3) if for any node i and disjoint sets B, and C for which i is d-separated from B by C, we have  cCi,B =cCB,i = 0. Using the above Lemma and the results of Theo- rem 3.27 in (Lauritzen, 1996), it is straightforward to show that a faithful network of m random variables whose causal structure is a DAG possesses the global Markov property5. This property can be used to develop reconstruction algorithms (e.g., PC algorithm (Spirtes et al., 2000b)) for the causal structure of a network.

5.1. Estimation

The measure introduced in (3) can be computed explicitly for special probability measures. For instance, if the joint distribution of Xis Gaussian with mean  ⃗µand covariance matrix  Σ, then using the results of (Givens et al., 1984), we obtain  cKi,j = |Σi,{j,K}�Σ{j,K},{j,K}�−1e1|,where  Σi,{j,K}denotes the sub-matrix of  Σcomprising row i and columns {j, K}, and e1 = (1, 0, ..., 0)T. Hence, in such systems, one can estimate the dependency measure by estimating the covariance matrix. However, this is not the case in general. Therefore, we introduce a non-parametric method for estimating our dependency measure using kernel method.

Given  {x(1), ..., x(N1)}and  {x(N1+1), ..., x(N1+N2)}that are i.i.d. samples drawn randomly from  ν1and ν2, respectively, the estimator of (5) is given by (Sriperumbudur et al., 2010),


such that  |αi − αj| ≤ d(x(i), x(j)), ∀i, j.In this equation, ˆν1and  ˆν2are empirical estimator of  ν1and  ν2, respectively. The estimator of MMD is given by


where  yi := 1/N1for  i ≤ N1and  yi := −1/N2, elsewhere. k(·, ·)represents the kernel of H. It is shown in (Sriperumbudur et al., 2010) that (11) converges to (5) as  N1, N2 → ∞almost surely as long as the underlying metric space is totally bounded. It is important to mention that the estimator in (11) depends on  {x(j)}s only through the metric  d(·, ·), and thus its complexity is independent of the dimension of  x(i), unlike the KLdivergence estimator (Wang et al., 2005). The estimator in (12) also converges to (6) almost surely with the rate of order  O(1/√N1 + 1/√N2), when  k(·, ·)is measurable and bounded.

Consider a network of m random variables X. Given N i.i.d. realizations of X, {z

(N)}, where  z(l) ∈ Em, we use (11) and define


such that z

K∪{j} = z(k)K∪{j}off j. Similarly, one can in- troduce an estimator for  ˜cKi,jusing (12). By applying the result of Corollary 5 in (Spirtes et al., 2000a), we obtain the following result.

Corollary 1. Let (E, d) be a totally bounded metric space and a network of random variables with positive probabilities, then  �cKi,jconverges to  cKi,jalmost surely as N goes to infinity.

Herein, we present two simulations in order to verify the theoretical results. In particular, the first experiment ver-ifies the group selection advantages and the second one shows an application of the measure for capturing rare dependencies.

Group selection for : In this simulation, we considered a group of individuals (C ∈{male,female}) to study the effect of an special treatment X on their health condition Y . For instance, X can denote sleep aids and Y can represent the individual’s awareness level in the next morning. Most psychotropic drugs are metabolized in the liver. Because the male body breaks down Ambien and other sleep aids faster, women typically have more of the drug in their system the next morning. For this simulation, we considered a mathematical model between X, Y , and C as follows: X = N(1.5, 1) and Y = 2X + N(0, 1), when C =female and X = N(1, 4) and Y = 3X +N(0, 9), otherwise. Accordingly, we generated different sample sizes N ∈ {40, ..., 1200}and estimated I(X; Y |c) and  ˆccy,x. Figure 3 depicts the results. Since for given c, (X, Y ) is jointly Gaussian, we estimated I(X; Y |c) by estimating the covariance matrix (Cover and Thomas, 2012), and estimated our measure using (12) with Gaussian kernels. As Figure 3 shows, although the treatment has different effects on different genders, I(X; Y |C) cannot capture that.

Capturing rare dependencies: We simulated the following non-linear system with  Wi ∼ U[−1, 1]and learned its corresponding structure.


We used the estimator of MMD given in (12) with Gaussian kernels and estimated the dependency measures. We


Figure 2. Recovered DAGs of the system given in (14) for different sample sizes. (a)-(b) use the measure in (3) and pure observation. (c)-(d) use kernel-based method and pure observation. (e)-(f) use the measure in (3) and interventional data. (f) shows the true structure.


N 100 200 300 400 500 600 700 800 900 1000 1100 1200 0.5

Figure 3. Estimated measures for different N.

obtained the corresponding DAG of this network given a set of observation of size  N ∈ {900, 2500}. Using the results on the convergence rate of the MMD estimator, we used a threshold of order  O(1/√N)to distinguish positive and zero measure. Figure 2 depicts the resulting DAGs. We also compared the performance of our measure with the kernel-based method proposed in (Zhang et al., 2011). Note that in this example, since the influence of  X3on X5is not detectable by mere observation, the best we can learn from mere observation is the DAG presented in Figure 2(b). However, with the same number of observations, the kernel-based method identifies an extra edge, Figure 2(d).

Next, we fixed the value of  X3to be natural number and irrational, separately and observed the outcome of the other variables for different sample sizes. Figures 2(e)-(f) depict the outcomes of the learning algorithm that uses our measure. In this case,  X3 → X5was identified and then the Meek rules helped to detect all the directions even the direction of  X1 − X5as it is shown in Figure 2(f).

Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337–404, 1950.

Nihat Ay and David C Krakauer. Geometric robustness theory and biological networks. Theory in biosciences, 125(2):93–121, 2007.

Nihat Ay and Daniel Polani. Information flows in causal networks. Advances in complex systems, 11(01):17–41, 2008.

Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.

Roland L Dobrushin. Prescribing a system of random variables by conditional distributions. Theory of Probability & Its Applications, 15(3):458–486, 1970.

Richard M Dudley. Real analysis and probability, volume 74. Cambridge University Press, 2002.

Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Sch¨olkopf. Kernel measures of conditional dependence. In NIPS, volume 20, pages 489–496, 2007.

Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419–435, 2002.

Clark R Givens, Rae Michael Shortt, et al. A class of wasserstein metrics for probability distributions. Michigan Math. J, 31(2):231–240, 1984.

VV Gorodetskii. On the strong mixing property for linear sequences. Theory of Probability & Its Applications, 22(2):411–413, 1978.

Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Sch¨olkopf, and Alex J Smola. A kernel method for the two-sample-problem. In Advances in neural information processing systems, pages 513–520, 2006.

Arthur Gretton, Kenji Fukumizu, Choon H Teo, Le Song, Bernhard Sch¨olkopf, and Alex J Smola. A kernel statistical test of independence. In Advances in neural information processing systems, pages 585–592, 2007.

Dominik Janzing, David Balduzzi, Moritz GrosseWentrup, Bernhard Sch¨olkopf, et al. Quantifying causal influences. The Annals of Statistics, 41(5):2324–2358, 2013.

Steffen L Lauritzen. Graphical models. Oxford University Press, 1996.

James Massey. Causality, feedback and directed information. In Proc. Int. Symp. Inf. Theory Applic.(ISITA-90), pages 303–305. Citeseer, 1990.

Christopher Meek. Strong completeness and faithfulness in bayesian networks. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pages 411–418. Morgan Kaufmann Publishers Inc., 1995.

Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(Dec):2651–2667, 2006.

Alfred M¨uller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, pages 429–443, 1997.

Judea Pearl. Causality: models, reasoning, and inference. Econometric Theory, 19:675–685, 2003.

Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 2014.

Thomas Schreiber. Measuring information transfer. Physical review letters, 85(2):461, 2000.

Moninder Singh and Marco Valtorta. Construction of bayesian network structures from data: a brief survey and an efficient algorithm. International journal of approximate reasoning, 12(2):111–131, 1995.

Pater Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wimberly. Constructing bayesian network models of gene expression networks from microarray data. 2000.

Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search, volume 81. MIT press, 2000.

Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Sch¨olkopf, and Gert Lanckriet. Nonparametric estimation of integral probability metrics. In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 1428–1432. IEEE, 2010.

Xiaohai Sun, Dominik Janzing, Bernhard Sch¨olkopf, and Kenji Fukumizu. A kernel-based causal learning algorithm. In Proceedings of the 24th international conference on Machine learning, pages 855–862. ACM, 2007.

Aad W Van Der Vaart and Jon A Wellner. Weak Conver- gence. Springer, 1996.

Cedric Villani. Topics in optimal transportation (graduate studies in mathematics, vol. 58). 2003.

Qing Wang, Sanjeev R Kulkarni, and Sergio Verd´u. Divergence estimation of continuous distributions based on data-dependent partitions. IEEE Transactions on Information Theory, 51(9):3064–3074, 2005.

K. Zhang, J. Peters, D. Janzing, and B. Sch¨olkopf. Kernelbased conditional independence test and application in causal discovery. pages 804–813, Corvallis, OR, USA, July 2011. AUAI Press.

7.1. Proof of Lemma 1

 cKi,j ≥ 0since Wasserstein is a metric. If  cKi,j = 0, we have  Wd (P(Xi|xj, xK), P(Xi|yj, xK)) = 0,for all real- izations  xj, yjand  xK. Using the fact that Wasserstein is a metric on the space of probability measures, the above equality, and total probability law, we obtain


The above equality holds for all  yjand  xK. This implies Xi ⊥⊥ Xj|XK.

We show this by an example. Let  X = U[0,1]to be uniformly distributed between zero and one, and


where  A = { ii+1 : i ∈ N}, and  V[0,1]is a random variable independent of U that is distributed non-uniformly over [0, 1]. In this case, we have


On the other hand, it is easy to see that Y has a uniform distribution over [0, 1] almost surely. Furthermore, for two measurable sets C and B in the  σ-algebra, we have


The last equality uses the fact that  P(Y ∈ B) = P(Y ∈B|X̸∈A) = P(Y ∈B|X∈C\A). Thus, changing the value of Y will not affect the conditional distribution of X given Y , i.e.,  cx,y = 0.

If  cKi,{j,k} = 0, Wd(P(Xi|xj, xk, xK), P(Xi|yj, yk, xK)) =0, for all realization  xj, yj, xk, yk, xK. By the total proba- bility law, we obtain


This implies that  P(Xi|xk, xK) = P(Xi|yj, yk, xK) =P(Xi|yk, xK). Hence,  cKi,k = 0. Similarly, we can prove that  cKi,j = 0.

Suppose  cKi,{j,k} = 0, then from the previous proof, we have  P(Xi|xk, xK) = P(Xi|yk, yj, xK), for all realizations  yj, xk, yk, xK. Thus, P(Xi|xk, xK) =P(Xi|yk, xj, xK)This is equivalent to say  cK∪{j}i,k = 0. The other part can be shown similarly.

If  cKi,j = ci,K = 0, then from  cKi,j = 0and total probabil- ity law, we obtain that


On the other hand, using the triangle inequality of the Wasserstein metric, we have


The first and third expressions on the right hand side are zero due to (15) and the second expression is zero due to ci,K = 0.


7.2. The Global Markov Property

Since the influence structure of this network is a DAG, there exists an ordering of the variables such that for every node i, all its parents have indices less that i. Without loss of generality suppose that  {X1, ..., Xm}is that ordering. Furthermore, using the chain rule, we have


where  X{<i}denotes all the variables with indices less than i. Due to the nature of this ordering, all the nodes in {< i} that do not belong to  Paiare non-descendants of node i. Hence, by the definition of ID, they have zero influence on  Xigiven the parents of i and because of the first property in Lemma 1, they can be dropped from the conditioning in (16).

The global Markov property is a direct consequence of Lemma 1 and Theorem 3.27 in (Lauritzen, 1996).

7.3. Proof of Theorem 1

In order to complete the proof, we need the following technical lemmas. When  d(·, ·)is the Euclidean distance, we denote the Wasserstein metric by  WE(·, ·).

Lemma 2. For real-valued random variables, we have


where  πis any joint distribution of x and y such that its marginals are  ν1and  ν2.

Proof. The lower bound is due to the dual representation of the Wasserstein metric and the fact that f(x) = x is Lipschitz.

For the upper bound, we use the Jensen’s inequality, that is


for  p ≥ 1. For p = 2, we use the monotonicity of √x, and the fact that the space of probability measures is complete and obtain the result.

Consider a network of variables in which every variable  Xifunctionally depends on a subset of other variables  XF pi(the parent set of node i) as follows,


where  Fi, Giare arbitrary functions such that  Gi ̸= 0. {Wi}s denote exogenous noises with mean zero.

Lemma 3. For a system described by (19), the influence of node j on its child i given the rest of i’s parents  Fpi \ {j}under Euclidean metric, is bounded as follows


where the suprimum is taking over all realizations of X−{i}that are only different at  Xj.

Proof. Using the lower bound in Lemma 2 and the fact that Wis have zero mean, we obtain the lower bound in (20).

To obtain the upper bound, we again use the result of Lemma 2, with the following joint distribution  π(Xi, Yi),


Gi(xF pi ) ,and  fWidenotes the probability density function of  Wiand I denotes the indicator function. Using this joint distribution, we obtain the upper bound in (20).

Applying the above result to a linear system in which Fi(yF pi) = (Ax)iand  Gi(xF pi) = 1, we obtain that


Designed for Accessibility and to further Open Science