A survey of some recent developments in measures of association

Measuring associations between variables is one of the central goals of data analysis. Arguably, the three most popular classical measures of association are Pearson’s correlation coefficient, Spearman’s $\rho$, and Kendall’s $\tau$. Although these coefficients are powerful for detecting monotonic associations, a practical problem is that they are not effective for detecting associations that are not monotonic. There have been many proposals to address this deficiency of the classical coefficients [66], such as the maximal correlation coefficient [59, 45, 92, 17], various coefficients based on joint cumulative distribution functions and ranks [43, 34, 54, 8, 83, 123, 124, 125, 29, 89, 61, 13, 94, 95, 30, 122], kernel-based methods [86, 48, 50, 99, 130], information theoretic coefficients [71, 74, 93], coefficients based on copulas [32, 76, 108, 98, 127], and coefficients based on pairwise distances [117, 115, 58, 41, 77].

This survey is about some recent developments in this area, beginning with a new coefficient of correlation proposed by the author in the paper [22]. This coefficient has the following desirable features: (a) It has a simple expression, like the classical coefficients. (b) It is a consistent estimator of a measure of dependence which is $0$ if and only if the variables are independent and $1$ if and only if one is a measurable function of the other. (c) It has a simple asymptotic theory under the hypothesis of independence.

The new coefficient is defined as follows. Let $(X,Y)$ be a pair of random variables defined on the same probability space, where $Y$ is not a constant. Let $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ be i.i.d. pairs of random variables with the same law as $(X,Y)$, where $n\geq 2$. Rearrange the data as $(X_{(1)},Y_{(1)}),\ldots,(X_{(n)},Y_{(n)})$ such that $X_{(1)}\leq\cdots\leq X_{(n)}$. (Note that $Y_{(i)}$ is just the $Y$-value ‘paired with’ $X_{(i)}$ in the original data, and not the $i^{th}$ order statistic of the $Y$’s.) If there are ties among the $X_{i}$’s, then choose an increasing rearrangement as above by breaking ties uniformly at random. Let $r_{i}$ be the number of $j$ such that $Y_{(j)}\leq Y_{(i)}$, and let $l_{i}$ to be the number of $j$ such that $Y_{(j)}\geq Y_{(i)}$. Then define

$\displaystyle\xi_{n}(X,Y):=1-\frac{n\sum_{i=1}^{n-1}|r_{i+1}-r_{i}|}{2\sum_{i=1}^{n}l_{i}(n-l_{i})}.$

(1.1)

This is the correlation coefficient proposed in [22]. When there are no ties among the $Y_{i}$’s, $l_{1},\ldots,l_{n}$ is just a permutation of $1,\ldots,n$, and so the denominator in the above expression is just $n(n^{2}-1)/3$. The following theorem is the main consistency result for $\xi_{n}$.

The limiting value $\xi(X,Y)$ appeared in the literature prior to [22], in a paper of Dette, Siburg, and Stoimenov [32] (see also [43, 70]). The paper [32] gave a copula-based estimator for $\xi(X,Y)$ when $X$ and $Y$ are continuous, that is consistent under smoothness assumptions on the copula and is computable in time $n^{5/3}$ for an optimal choice of tuning parameters.

Note that neither $\xi_{n}$ nor the limiting value $\xi$ is symmetric in $X$ and $Y$. A symmetrized version of $\xi_{n}$ can be constructed by taking the maximum of $\xi_{n}(X,Y)$ and $\xi_{n}(Y,X)$.

The complete proof of Theorem 1.1 is available in the supplementary materials of [22], and also in the arXiv version of the paper. It is not too hard to see why $\xi(X,Y)$ has the properties listed in Theorem 1.1, although filling in the details takes some work. The proof of convergence of $\xi_{n}(X,Y)$ to $\xi(X,Y)$ is less obvious. The following is a very rough sketch of the proof, reproduced from a similar discussion in [22].

For simplicity, consider only the case of continuous $X$ and $Y$, where the denominator in (1.2) is simply $n(n^{2}-1)/3$. First, note that by the Glivenko–Cantelli theorem, $r_{i}/n\approx F(Y_{(i)})$, where $F$ is the cumulative distribution function of $Y$. Thus,

$\displaystyle\xi_{n}(X,Y)\approx 1-\frac{3}{n}\sum_{i=1}^{n}|F(Y_{i})-F(Y_{N(i)})|,$

(2.1)

where $N(i)$ is the unique index $j$ such that $X_{j}$ is immediately to the right of $X_{i}$ if we arrange the $X$’s in increasing order. If $X_{i}$ is the rightmost value, define $N(i)$ arbitrarily; it does not matter since the contribution of a single term in the above sum is of order $1/n$. Next, observe that for any $x,y\in\mathbb{R}$,

$\displaystyle|F(x)-F(y)|$

$\displaystyle=\int(1_{\{t\leq x\}}-1_{\{t\leq y\}})^{2}d\mu(t),$

(2.2)

where $\mu$ is the law of $Y$. This is true because the integrand is $1$ between $x$ and $y$ and $0$ outside.

Suppose that we condition on $X_{1},\ldots,X_{n}$. Since $X_{i}$ is likely to be very close to $X_{N(i)}$, the random variables $Y_{i}$ and $Y_{N(i)}$ are likely to be approximately i.i.d. after this conditioning. This leads to the approximation

	$\displaystyle\mathbb{E}[(1_{\{t\leq Y_{i}\}}-1_{\{t\leq Y_{N(i)}\}})^{2}|X_{1},\ldots,X_{n}]$	$\displaystyle\approx 2\mathrm{Var}(1_{\{t\leq Y_{i}\}}|X_{1},\ldots,X_{n})$
		$\displaystyle=2\mathrm{Var}(1_{\{t\leq Y_{i}\}}|X_{i}).$

This gives

	$\displaystyle\mathbb{E}(1_{\{t\leq Y_{i}\}}-1_{\{t\leq Y_{N(i)}\}})^{2}$	$\displaystyle\approx 2\mathbb{E}[\mathrm{Var}(1_{\{t\leq Y\}}|X)]$
		$\displaystyle=2\mathrm{Var}(1_{\{t\leq Y\}})-2\mathrm{Var}(\mathbb{E}(1_{\{t\leq Y\}}|X)).$

Combining this with (2.2), we get

$\displaystyle\mathbb{E}|F(Y_{i})-F(Y_{N(i)})|$

$\displaystyle\approx\int 2[\mathrm{Var}(1_{\{t\leq Y\}})-\mathrm{Var}(\mathbb{E}(1_{\{t\leq Y\}}|X))]d\mu(t).$

But note that $\mathrm{Var}(1_{\{t\leq Y\}})=F(t)(1-F(t))$, and $F(Y)\sim\textup{Uniform}[0,1]$. Thus,

$$\int\mathrm{Var}(1_{\{t\leq Y\}})d\mu(t)=\int F(t)(1-F(t))d\mu(t)=\int_{0}^{1}x(1-x)dx=\frac{1}{6}.$$

Therefore by (2.1),

$\displaystyle\mathbb{E}(\xi_{n}(X,Y))\approx 6\int\mathrm{Var}(\mathbb{E}(1_{\{t\leq Y\}}|X))d\mu(t)=\xi(X,Y),$

where the last identity holds because $\int\mathrm{Var}(1_{\{t\leq Y\}})d\mu(t)=1/6$, as shown above. This establishes the convergence of $\mathbb{E}(\xi_{n}(X,Y))$ to $\xi(X,Y)$. Concentration inequalities are then used to show that $\xi_{n}(X,Y)-\mathbb{E}(\xi_{n}(X,Y))\to 0$ almost surely.

Let $X$, $Y$ and $\xi_{n}$ be as in the previous section. For each $t\in\mathbb{R}$, let $F(t):=\mathbb{P}(Y\leq t)$ and $G(t):=\mathbb{P}(Y\geq t)$. Let $\phi(y,y^{\prime}):=\min\{F(y),F(y^{\prime})\}$. Define

$$\tau^{2}=\frac{\mathbb{E}\phi(Y_{1},Y_{2})^{2}-2\mathbb{E}(\phi(Y_{1},Y_{2})\phi(Y_{1},Y_{3}))+(\mathbb{E}\phi(Y_{1},Y_{2}))^{2}}{(\mathbb{E}G(Y)(1-G(Y)))^{2}},$$

(3.1)

where $Y_{1},Y_{2},Y_{3}$ are independent copies of $Y$. The following theorem gives the limiting distribution of $\xi_{n}$ under the null hypothesis that $X$ and $Y$ are independent.

The reason why $\tau^{2}$ does not depend on the law of $Y$ if $Y$ is continuous is that in this case $F(Y)$ and $G(Y)$ are Uniform$[0,1]$ random variables, which implies that the expectations in (3.1) do not depend on the law of $Y$. If $Y$ is not continuous, then $\tau^{2}$ may depend on the law of $Y$. For example, it is not hard to show that if $Y$ is a Bernoulli$(1/2)$ random variable, then $\tau^{2}=1$. Fortunately, if $Y$ is not continuous, there is a simple way to estimate $\tau^{2}$ from the data using the estimator

$$\widehat{\tau}^{2}_{n}=\frac{a_{n}-2b_{n}+c_{n}^{2}}{d_{n}^{2}},$$

where $a_{n}$, $b_{n}$, $c_{n}$ and $d_{n}$ are defined as follows. For each $i$, let

$$R(i):=\#\{j:Y_{j}\leq Y_{i}\},\ \ \ L(i):=\#\{j:Y_{j}\geq Y_{i}\}.$$

(3.2)

(Note that $R(i)$ and $L(i)$ are different than $r_{i}$ and $l_{i}$ defined earlier.) Let $u_{1}\leq u_{2}\leq\cdots\leq u_{n}$ be an increasing rearrangement of $R(1),\ldots,R(n)$. Let $v_{i}:=\sum_{j=1}^{i}u_{j}$ for $i=1,\ldots,n$. Define

	$\displaystyle a_{n}:=\frac{1}{n^{4}}\sum_{i=1}^{n}(2n-2i+1)u_{i}^{2},\ \ \ b_{n}:=\frac{1}{n^{5}}\sum_{i=1}^{n}(v_{i}+(n-i)u_{i})^{2},$
	$\displaystyle c_{n}:=\frac{1}{n^{3}}\sum_{i=1}^{n}(2n-2i+1)u_{i},\ \ \ d_{n}:=\frac{1}{n^{3}}\sum_{i=1}^{n}L(i)(n-L(i)).$

Then the following holds.

The question of proving a central limit theorem for $\xi_{n}$ in the absence of independence is much more difficult than the independent case. This was left as an open question in [22] and recently resolved in complete generality by Lin and Han [73], following earlier proofs of Deb, Ghosal, and Sen [31] and Shi, Drton, and Han [104] under additional assumptions. Lin and Han [73] also give a consistent estimator of the asymptotic variance of $\xi_{n}$ in the absence of independence, solving another question that was left open in [22]. A central limit theorem for the symmetrized version of $\xi_{n}$ (defined as the maximum of $\xi_{n}(X,Y)$ and $\xi_{n}(Y,X)$) under the hypothesis of independence was proved by Zhang [129].

A deficiency of $\xi_{n}$, as already pointed out in [22] through simulated examples, is that it has low power for testing independence against ‘standard’ alternatives, such as linear or monotone associations. This was theoretically confirmed by Shi, Drton, and Han [105], where it was shown that the test of independence using $\xi_{n}$ is rate-suboptimal against a family of local alternatives, whereas three other nonparametric tests of independence proposed in [61, 13, 8, 125] are rate-optimal. Like $\xi_{n}$, the three competing test statistics considered in [105] are also computable in $O(n\log n)$ time. Similar results were obtained for a different type of competing test statistic by Cao and Bickel [21].

A more detailed analysis of the power properties of $\xi_{n}$ was carried out by Auddy, Deb, and Nandy [2], where the asymptotic distribution of $\xi_{n}$ under any changing sequence of alternatives converging to the null hypothesis of independence was computed. This analysis yielded exact detection thresholds and limiting power under natural alternatives converging to the null, such as mixture models, rotation models and noisy nonparametric regression. The detection boundary lies at distance $n^{-1/4}$ from the null, instead of the more standard $n^{-1/2}$. This is similar to the power properties of other ‘graph-based’ statistics for testing independence, such as the Friedman–Rafsky statistic [41, 11].

A proposal for ‘boosting’ the power of $\xi_{n}$ for testing independence, by incorporating multiple nearby ranks instead of only the nearest ones, was recently proposed by Lin and Han [72]. This modified estimator was shown to attain near-optimal rates of power against certain classes of alternative hypotheses.

The conceptual reason behind the absence of local power of statistics such as $\xi_{n}$ was explained by Bickel [12]. An interesting question that remains unexplained is the following. It is seen in simulations that although $\xi_{n}$ has low power for testing independence against standard alternatives such as linear and monotone, it becomes more powerful as the signal starts to get more and more oscillatory [22]. This gives an advantage over other coefficients in applications where oscillatory signals arise naturally [25, 97], and suggests that $\xi_{n}$ may be efficient for certain kinds of local alternatives. No result of this sort has yet been proven.

Many methods have been proposed for testing independence nonparametrically in the multivariate setting. This includes classical tests [88, 49, 117] as well as a flurry of recent ones proposed in the last ten years [57, 56, 58, 131, 124, 68, 30, 106, 10, 107, 31].

Most of these papers are concerned only with testing independence, and not with measuring the strength of dependence as measured by a correlation coefficient such as $\xi_{n}$. Unfortunately, the $\xi_{n}$ coefficient and many other popular univariate coefficients do not readily generalize to the multivariate setting because they are based on ranks. Statisticians have started taking a new look at this old problem in recent years by considering a multivariate notion of rank defined using optimal transport. Roughly speaking, the idea is as follows. Let $\nu$ be a ‘reference measure’ in $\mathbb{R}^{d}$, akin to the uniform distribution on $[0,1]$ in $\mathbb{R}$. Given any probability measure $\mu$ in $\mathbb{R}^{d}$, let $F^{\mu}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be the map that ‘optimally transports’ $\mu$ to $\nu$ — that is, if $X\sim\mu$ then $F^{\mu}(X)\sim\nu$, and $F^{\mu}$ minimizes $\mathbb{E}\|X-F(X)\|^{2}$ among all such $F$. By a theorem of McCann [80], such a map exists and is unique if $\mu$ and $\nu$ are both absolutely continuous with respect to Lebesgue measure. For example, when $d=1$, $F^{\mu}$ is just the cumulative distribution function of $X$, which transforms $X$ into a Uniform$[0,1]$ random variable. For properties of this map, see, e.g., Figalli [38] and Hallin et al. [51].

The above idea suggests a natural definition of multivariate rank. If $X_{1},\ldots,X_{n}$ are i.i.d. samples from $\mu$, one can try to estimate $F^{\mu}$ using this data. Let $F_{n}^{\mu}$ be an estimate. Then $F_{n}^{\mu}(X_{i})$ can act as a ‘multivariate rank’ of $X_{i}$ among $X_{1},\ldots,X_{n}$, divided by $n$. Since $F^{\mu}(X_{i})\sim\nu$, we can then assume that $F_{n}^{\mu}(X_{i})$ is approximately distributed according to $\nu$, and then try to test for independence of random vectors using a test for independence that works when the marginal distributions are both $\nu$. This idea has been made precise in a number of recent works in the statistics literature, such as Chernozhukov et al. [27], Deb, Ghosal, and Sen [31], Deb and Sen [30], Hallin et al. [51], Manole et al. [78], Shi, Drton, and Han [106], Ghosal and Sen [47], Mordant and Segers [82] and Shi et al. [107, 103]. For a survey and further discussions, see Han [52].

A direct generalization of $\xi_{n}$ to higher dimensional spaces has not been proposed so far, although the variant proposed in Deb et al. [31] satisfies the same properties as $\xi_{n}$ provided that the space on which $Y$ takes values admits a nonnegative definite kernel and the space on which $X$ takes values has a metric. This covers most spaces that arise in practice. There are a couple of other generalizations, proposed by Azadkia and Chatterjee [3] and Gamboa et al. [44], on measuring the dependence between a univariate random variable $Y$ and a random vector $\mathbf{X}$. The coefficient proposed in [3] (discussed in detail in Section 6) is based on a generalization of the ideas behind the construction of $\xi_{n}$. The coefficient proposed in [44] combines the construction of $\xi_{n}$ with ideas from the theory of Sobol indices. A new contribution of the present paper is a simple generalization of $\xi_{n}$ to standard Borel spaces, which has been overlooked in the literature until now. This is presented in Section 8.

The problem of measuring conditional dependence has received less attention than the problem of measuring unconditional dependence, partly because it is a more difficult task. Non-parametric conditional independence can be tested for discrete data using the classical Cochran–Mantel–Haenszel test [28, 79], which can be adapted for continuous random variables by binning the data [62] or using kernels [42, 128, 111, 33, 100]. Besides these, there are methods based on estimating conditional cumulative distribution functions [75, 85], conditional characteristic functions [112, 67], conditional probability density functions [113], empirical likelihood [114], mutual information and entropy [96, 65, 87], copulas [7, 109, 119], distance correlation [121, 37, 116], and other approaches [101]. A number of interesting ideas based on resampling and permutation tests have been proposed in recent years [20, 100, 9].

In Azadkia and Chatterjee [3], a new coefficient of conditional dependence was proposed, based on the ideas behind the $\xi$-coefficient defined in [22]. Like the $\xi$-coefficient, this one also has a long list of desirable features, such as being fully nonparametric and working under minimal assumptions. The coefficient is defined as follows.

Let $Y$ be a random variable and $\mathbf{X}=(X_{1},\ldots,X_{p})$ and $\mathbf{Z}=(Z_{1},\ldots,Z_{q})$ be random vectors, all defined on the same probability space. Here $q\geq 1$ and $p\geq 0$. The value $p=0$ means that $\mathbf{X}$ has no components at all. Let $\mu$ be the law of $Y$. The following quantity was proposed in [3] as a measure of the degree of conditional dependence of $Y$ and $\mathbf{Z}$ given $\mathbf{X}$:

$$T=T(Y,\mathbf{Z}|\mathbf{X}):=\frac{\int\mathbb{E}(\mathrm{Var}(\mathbb{P}(Y\geq t|\mathbf{Z},\mathbf{X})|\mathbf{X}))d\mu(t)}{\int\mathbb{E}(\mathrm{Var}(1_{\{Y\geq t\}}|\mathbf{X}))d\mu(t)}.$$

(6.1)

If the denominator equals zero, $T$ is undefined. If $p=0$, then $\mathbf{X}$ has no components, and the conditional expectations and variances given $\mathbf{X}$ should be interpreted as unconditional expectations and variances. In this case we write $T(Y,\mathbf{Z})$ instead of $T(Y,\mathbf{Z}|\mathbf{X})$. Note that $T$ is a generalization of the statistic $\xi$ appearing in Theorem 1.1. The following theorem summarizes the main properties of $T$.

Now suppose we have data consisting of $n$ i.i.d. copies $(Y_{1},\mathbf{X}_{1},\mathbf{Z}_{1}),\ldots,(Y_{n},\mathbf{X}_{n},\mathbf{Z}_{n})$ of the triple $(Y,\mathbf{X},\mathbf{Z})$, where $n\geq 2$. For each $i$, let $N(i)$ be the index $j$ such that $\mathbf{X}_{j}$ is the nearest neighbor of $\mathbf{X}_{i}$ with respect to the Euclidean metric on $\mathbb{R}^{p}$, where ties are broken uniformly at random. Let $M(i)$ be the index $j$ such that $(\mathbf{X}_{j},\mathbf{Z}_{j})$ is the nearest neighbor of $(\mathbf{X}_{i},\mathbf{Z}_{i})$ in $\mathbb{R}^{p+q}$, again with ties broken uniformly at random. Let $R_{i}$ be the rank of $Y_{i}$, that is, the number of $j$ such that $Y_{j}\leq Y_{i}$. If $p\geq 1$, define

$$T_{n}=T_{n}(Y,\mathbf{Z}|\mathbf{X}):=\frac{\sum_{i=1}^{n}(\min\{R_{i},R_{M(i)}\}-\min\{R_{i},R_{N(i)}\})}{\sum_{i=1}^{n}(R_{i}-\min\{R_{i},R_{N(i)}\})}.$$

If $p=0$, let $L_{i}$ be the number of $j$ such that $Y_{j}\geq Y_{i}$, let $M(i)$ denote the $j$ such that $\mathbf{Z}_{j}$ is the nearest neighbor of $\mathbf{Z}_{i}$ (ties broken uniformly at random), and let

$$T_{n}=T_{n}(Y,\mathbf{Z}):=\frac{\sum_{i=1}^{n}(n\min\{R_{i},R_{M(i)}\}-L_{i}^{2})}{\sum_{i=1}^{n}L_{i}(n-L_{i})}.$$

In both cases, $T_{n}$ is undefined if the denominator is zero. The following theorem shows that $T_{n}$ is a consistent estimator of $T$.

For various other properties of $T_{n}$, such as rate of convergence, performance in simulations and real data, etc., see [3]. One problem that was left unsolved in [3] was the question of proving a central limit theorem for $T_{n}$ under the null hypothesis, which is crucial for carrying out tests for conditional independence. This question was partially resolved by Shi, Drton, and Han [104], who proved a central limit theorem for $T_{n}$ under the assumption that $Y$ is independent of $(\mathbf{X},\mathbf{Z})$. An improved version of this result was proved recently by Lin and Han [73]. A version for data supported on manifolds was proved by Han and Huang [53].

The paper of Shi et al. [104] also develops the ‘conditional randomization test’ (CRT) framework of Candès et al. [20] to test conditional independence using $T_{n}$, and find that $T_{n}$, like $\xi_{n}$ is an inefficient test statistic. To address this concern, an improved generalization of $T_{n}$, called ‘kernel partial correlation’ (KPC), was proposed by Huang, Deb, and Sen [63]. Unlike $T_{n}$, KPC has the flexibility to use more than one nearest neighbor, which gives it better power properties.

Note that by the above theorems, a test of conditional independence based on $T_{n}$ is consistent against all alternatives. The problem is that in the absence of an asymptotic theory for $T_{n}$, it is difficult to control the significance level of such a test. This is in fact an impossible problem, by a recent result of Shah and Peters [102] that proves hardness of conditional independence testing in the absence of smoothness assumptions. Assuming some degree of smoothness, minimax optimal conditional independence tests were recently constructed by Neykov, Balakrishnan, and Wasserman [84] and Kim et al. [69].

The commonly used variable selection methods in the statistics literature rely on linear or additive models. This includes classical methods [14, 46, 26, 118, 35, 40, 55, 81] as well as modern ones [19, 132, 133, 126, 36, 91]. These methods are powerful and widely used in practice. However, they sometimes run into problems when significant interaction effects or nonlinearities are present. Such problems can be overcome by model-free methods [20, 60, 1, 15, 39, 55, 18, 6, 120, 16]. On the flip side, the theoretical foundations of model-free methods are usually weaker than those of model-based methods.

In an attempt to combine the best of both worlds, a new method of variable selection called Feature Ordering by Conditional Independence (FOCI), was proposed in Azadkia and Chatterjee [3]. This method uses the conditional dependence coefficient $T_{n}$ described in the previous section in a stepwise fashion, as follows. Let $Y$ be the response variable and let $\mathbf{X}=(X_{j})_{1\leq j\leq p}$ be the set of predictors. The data consists of $n$ i.i.d. copies of $(Y,\mathbf{X})$. First, choose $j_{1}$ to be the index $j$ that maximizes $T_{n}(Y,X_{j})$. Having obtained $j_{1},\ldots,j_{k}$, choose $j_{k+1}$ to be the index $j\notin\{j_{1},\ldots,j_{k}\}$ that maximizes $T_{n}(Y,X_{j}|X_{j_{1}},\ldots,X_{j_{k}})$. Continue like this until arriving at the first $k$ such that $T_{n}(Y,X_{j_{k+1}}|X_{j_{1}},\ldots,X_{j_{k}})\leq 0$, and then declare the chosen subset to be $\widehat{S}:=\{j_{1},\ldots,j_{k}\}$. If there is no such $k$, define $\widehat{S}$ to be the whole set of variables. It may also happen that $T_{n}(Y,X_{j_{1}})\leq 0$. In that case declare $\widehat{S}$ to be empty. Note that this variable selection procedure involves no choice of tuning parameters, which may be an advantage in practice.

It was shown in [3] that under mild conditions, the method selects a ‘correct’ set of variables with high probability. More precisely, it was shown that with high probability, the set $\widehat{S}$ selected by FOCI has the property that $Y$ and $(X_{j})_{j\notin S}$ are conditionally independent given $(X_{j})_{j\in\widehat{S}}$. In other words, all the information about $Y$ that one can get from $\mathbf{X}$ is contained in $(X_{j})_{j\in\widehat{S}}$. For further properties of FOCI and its performance in simulations and real data sets, see [3].

An improved version of FOCI called KFOCI (‘Kernel FOCI’) was proposed by Huang et al. [63]. An application of FOCI to causal inference, via an algorithm named DAG-FOCI, was introduced in Azadkia, Taeb, and Bühlmann [5]. For another application to causal inference, see Chatterjee and Vidyasagar [24].

In this section, a simple but wide ranging generalization of $\xi_{n}$ is proposed. In hindsight, this generalization seems obvious, but somehow this was overlooked both in the original paper [22] as well as in the subsequent developments listed in Section 5.

Recall that two measurable spaces are said to be isomorphic to each other if there is a bijection between the two spaces which is measurable and whose inverse is also measurable. Recall that a standard Borel space is a measurable space that is isomorphic to a Borel subset of a Polish space [110, Chapter 3]. In particular, every Borel subset of every Polish space is a standard Borel space. The Borel isomorphism theorem says that any uncountable standard Borel space is isomorphic to the real line (see Rao and Srivastava [90] for an elementary proof). In particular, if $\mathcal{X}$ is any standard Borel space, there is a measurable map $\varphi:\mathcal{X}\to\mathbb{R}$ such that $\varphi$ is injective, $\varphi(\mathcal{X})$ is Borel, and $\varphi^{-1}$ is measurable on $\varphi(\mathcal{X})$. We will say that $\varphi$ is an isomorphism between $\mathcal{X}$ and a Borel subset of the real line, or simply, a ‘Borel isomorphism’.

Now let $\mathcal{X}$ and $\mathcal{Y}$ be two standard Borel spaces. Let $\varphi$ be a Borel isomorphism of $\mathcal{X}$ and $\psi$ be a Borel isomorphism of $\mathcal{Y}$. Let $(X,Y)$ be an $\mathcal{X}\times\mathcal{Y}$-valued pair of random variables, and let $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ be i.i.d. copies of $(X,Y)$. Let $X^{\prime}:=\varphi(X)$ and $Y^{\prime}:=\psi(Y)$, so that $(X^{\prime},Y^{\prime})$ is a pair of real-valued random variables. Let $X_{i}^{\prime}:=\varphi(X_{i})$ and $Y_{i}^{\prime}:=\psi(Y_{i})$ for each $i$. Finally, define

$$\xi_{n}(X,Y):=\xi_{n}(X^{\prime},Y^{\prime}),$$

where $\xi_{n}(X^{\prime},Y^{\prime})$ is defined using $(X_{1}^{\prime},Y_{1}^{\prime}),\ldots,(X_{n}^{\prime},Y_{n}^{\prime})$ as in equation (1.1). Note that the definition of $\xi_{n}(X,Y)$ depends on our choices of $\varphi$ and $\psi$. Different choices of isomorphisms would lead different definitions of $\xi_{n}$. The following theorem generalizes Theorem 1.1.

Just like the univariate case, the generalized $\xi_{n}$ has the advantage of working under zero assumptions and having a simple asymptotic theory, as shown by Theorem 8.1. On the other hand, just like the univariate coefficient, one can expect the generalized coefficient to also suffer from low power for testing independence.

Theorem 8.1 is a nice, clean result, but to implement the idea in practice, one needs to work with actual Borel isomorphisms. Here is an example of a Borel isomorphism between $\mathbb{R}^{d}$ and a Borel subset of $\mathbb{R}$. Take any $x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}$. Let

$$a_{i,1}\cdots a_{i,k_{i}}.b_{i,1}b_{i,2}\cdots$$

be the binary expansion of $|x_{i}|$. Filling in extra $0$’s at the beginning if necessary, let us assume that $k_{1}=\cdots=k_{d}=k$. Then, let us ‘interlace’ the digits to get the number

$$a_{1,1}a_{2,1}\cdots a_{d,1}a_{1,2}a_{2,2}\cdots a_{d,2}\cdots a_{1,k}a_{2,k}\cdots a_{d,k}.b_{1,1}b_{2,1}\cdots b_{d,1}b_{1,2}b_{2,2}\cdots b_{d,2}\cdots.$$

This is an encoding of the $n$-tuple $(|x_{1}|,\ldots,|x_{d}|)$. But we also want to encode the signs of the $x_{i}$’s. Let $c_{i}=1$ if $x_{i}\geq 0$ and $0$ if $x_{i}<0$. Sticking $1c_{1}c_{2}\cdots c_{d}$ in front of the above list, we get an encoding of the vector $x$ as a real number. (The $1$ in front ensures there is no ambiguity arising from some of the leading $c_{i}$’s being $0$.) It is easy to verify that this mapping is measurable, injective, and its inverse (defined on its range) is also measurable.

Numerical simulations with $\xi_{n}$ computed using the above scheme produced satisfactory results. Some examples are as follows. The examples show one potential problem with using statistics such as $\xi_{n}$ in a high dimensional setting: The bias may be quite large (even though the standard deviation is small), resulting in slow convergence of $\xi_{n}(X,Y)$ to $\xi(X,Y)$.

The above examples indicate that it may not be ‘crazy’ to use the generalized version of $\xi_{n}$ as a measure of association in the multivariate setting and beyond. Further investigations, through applications in simulated and real data, would be necessary to arrive at a concrete verdict.

The generalized version of $\xi_{n}$ can also be used to define a coefficient of conditional dependence for random variables taking values in standard Borel spaces, as follows. Let $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ be standard Borel spaces, and $X$, $Y$ and $Z$ be random variables taking values in $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$, respectively. Let $W$ denote the $\mathcal{X}\times\mathcal{Z}$-valued random variable $(X,Z)$. Using Borel isomorphisms, let us define the coefficients $\xi_{n}(X,Y)$ and $\xi_{n}(W,Y)$ as before, based on i.i.d. data $(X_{1},Y_{1},Z_{1}),\ldots,(X_{n},Y_{n},Z_{n})$. One can then define a coefficient of conditional dependence between $Y$ and $Z$ given $X$ as

$$\xi_{n}(Z,Y|X):=\frac{\xi_{n}(W,Y)-\xi_{n}(X,Y)}{1-\xi_{n}(X,Y)},$$

leaving it undefined if the denominator is zero. The following theorem justifies its use as a measure of conditional dependence.