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 , where [m] := {1, ..., m} by and [m] \ {j} by .

In a directed graph , we denote the parent set of a node by , and denote the set of its non-descendant1 by . We use to 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 , 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

. 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 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 on , we select a set of indices K, where and consider the following two probability measures:

where and are two realizations for that are the same every where except at . Further, assume at position equals x and equals ) at this position. If there exists a subset such that for all such realizations, and are the same, then we say has no depen- dency on . This is analogous to the conditional independence that states if and are independent given some , 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 and . However, when interventional data is available, we can identify whether causes , 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 , the Wasserstein metric between is given by , where the infimum is taken over all probability measures on such that its marginal distributions are and , respectively.

Using the above distance, we define the dependency of on given as follows:

The suprimum is over all realizations and that only differ at the jth variable. Moreover, we assume at jth position equals x and y

equals y () at this position. When is 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 , 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 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 . 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 is the set of all continuous functions satisfying the Lipschitz condition: 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 , 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 . More precisely, MMD is de-fined as

Here, H represents a reproducing kernel Hilbert space (RKHS) (Aronszajn, 1950) with reproducing kernel . 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 MMDif and only if . In this case, MMD can also be used to compare the two conditional distributions in (2). This is because, MMDimplies that the two conditional distributions are the same. This allows us to define a new dependency measure which we denoted it by similar 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 and 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 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 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 and .

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 removes the dependencies of on its parents, and replaces 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 to X

, IXX

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 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 and but (3) re- quires only one . 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 an 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, , where H denotes the entropy4. However, if the underlying DAG is given by Figure 1(a), we have . 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 , while in (a), . But in 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 and Z = , such that the transformations from to (X, Y ) and from to (X, Y, Z) are invertible and and are independent exogenous noises. In other words, there exist functions and such that and . Furthermore, f is an injective function in its first argument, i.e., if for some w, then .

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., , then . This can be explained by the fact that as H(Y |X) goes to zero, in other words, as tends to for some fixed value , 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 .

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 , we have

where This distribution depends only on realizations of (X, Y ) and it is independent of . Hence, changing the dependency between X and Y will not affect , 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,

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

As we mentioned earlier, by reducing the variance of , the first term in (9) tends to . Hence, (9) goes to zero. But, using the result of Theorem 1, we have , which is independent of the variance of .

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 . 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 , we obtain two conditional probabilities P(Y |x, c) and . Then, we say in group C = c, the causal influence between X and Y is more obvious compare to the group , 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 . More precisely, if , where

Note that , where is 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 .

Example 4. Suppose that and , where C takes value from {1, ..., M} w.p. and . In this case, we have . 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 . (2) and when it is zero, we have . (3) Decomposition: implies . (4) Weak union: If , then . (5) Contraction: If , then . (6) Intersection: If , then .

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 not only those with positive measure. See Exam- ple 1 for the asymmetric property of .

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 . 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 where denotes the sub-matrix of comprising row i and columns {j, K}, and e. 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 and that are i.i.d. samples drawn randomly from and , respectively, the estimator of (5) is given by (Sriperumbudur et al., 2010),

such that In this equation, and are empirical estimator of and , respectively. The estimator of MMD is given by

where for and , elsewhere. represents the kernel of H. It is shown in (Sriperumbudur et al., 2010) that (11) converges to (5) as almost surely as long as the underlying metric space is totally bounded. It is important to mention that the estimator in (11) depends on s only through the metric , and thus its complexity is independent of the dimension of , unlike the KLdivergence estimator (Wang et al., 2005). The estimator in (12) also converges to (6) almost surely with the rate of order , when is measurable and bounded.

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

, where , we use (11) and define

such that z

off j. Similarly, one can in- troduce an estimator for using (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 converges to almost 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 (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 and estimated I(X; Y |c) and . 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 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 . Using the results on the convergence rate of the MMD estimator, we used a threshold of order 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 on is 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 to 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, was identified and then the Meek rules helped to detect all the directions even the direction of as 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

• since Wasserstein is a metric. If , we have for all real- izations and . 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 and . This implies .

• We show this by an example. Let to be uniformly distributed between zero and one, and

where , and 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 . Thus, changing the value of Y will not affect the conditional distribution of X given Y , i.e., .

• If 0, for all realization . By the total proba- bility law, we obtain

This implies that . Hence, . Similarly, we can prove that .

• Suppose , then from the previous proof, we have , for all realizations . Thus, This is equivalent to say . The other part can be shown similarly.

• If , then from and 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 .

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 is that ordering. Furthermore, using the chain rule, we have

where 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 are non-descendants of node i. Hence, by the definition of ID, they have zero influence on given 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 is the Euclidean distance, we denote the Wasserstein metric by .

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

where is any joint distribution of x and y such that its marginals are and .

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 . For p = 2, we use the monotonicity of , and the fact that the space of probability measures is complete and obtain the result.

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

where are arbitrary functions such that . 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 under Euclidean metric, is bounded as follows

where the suprimum is taking over all realizations of that are only different at .

Proof. Using the lower bound in Lemma 2 and the fact that s 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 ,

and denotes the probability density function of and 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 and , we obtain that