Kendall rank correlation coefficient

All points in the gray area are concordant and all points in the white area are discordant with respect to point ${\displaystyle (X_{1},Y_{1})}$. With ${\displaystyle n=30}$ points, there are a total of ${\displaystyle {\binom {30}{2}}=435}$ possible point pairs. In this example there are 395 concordant point pairs and 40 discordant point pairs, leading to a Kendall rank correlation coefficient of 0.816.

Let ${\displaystyle (x_{1},y_{1}),...,(x_{n},y_{n})}$ be a set of observations of the joint random variables X and Y, such that all the values of (${\displaystyle x_{i}}$) and (${\displaystyle y_{i}}$) are unique (ties are neglected for simplicity). Any pair of observations ${\displaystyle (x_{i},y_{i})}$ and ${\displaystyle (x_{j},y_{j})}$, where ${\displaystyle i<j}$, are said to be concordant if the sort order of ${\displaystyle (x_{i},x_{j})}$ and ${\displaystyle (y_{i},y_{j})}$ agrees: that is, if either both ${\displaystyle x_{i}>x_{j}}$ and ${\displaystyle y_{i}>y_{j}}$ holds or both ${\displaystyle x_{i}<x_{j}}$ and ${\displaystyle y_{i}<y_{j}}$; otherwise they are said to be discordant.

The Kendall τ coefficient is defined as:

${\displaystyle \tau ={\frac {({\text{number of concordant pairs}})-({\text{number of discordant pairs}})}{({\text{number of pairs}})}}=1-{\frac {2({\text{number of discordant pairs}})}{n \choose 2}}.}$[3]

where ${\displaystyle {n \choose 2}={n(n-1) \over 2}}$ is the binomial coefficient for the number of ways to choose two items from n items.

The Kendall rank coefficient is often used as a test statistic in a statistical hypothesis test to establish whether two variables may be regarded as statistically dependent. This test is non-parametric, as it does not rely on any assumptions on the distributions of X or Y or the distribution of (X,Y).

Under the null hypothesis of independence of X and Y, the sampling distribution of τ has an expected value of zero. The precise distribution cannot be characterized in terms of common distributions, but may be calculated exactly for small samples; for larger samples, it is common to use an approximation to the normal distribution, with mean zero and variance

${\displaystyle {\frac {2(2n+5)}{9n(n-1)}}}$.[4]

A pair ${\displaystyle \{(x_{i},y_{i}),(x_{j},y_{j})\}}$ is said to be tied if and only if ${\displaystyle x_{i}=x_{j}}$ or ${\displaystyle y_{i}=y_{j}}$; a tied pair is neither concordant nor discordant. When tied pairs arise in the data, the coefficient may be modified in a number of ways to keep it in the range [−1, 1]:

When two quantities are statistically dependent, the distribution of ${\displaystyle \tau }$ is not easily characterizable in terms of known distributions. However, for ${\displaystyle \tau _{A}}$ the following statistic, ${\displaystyle z_{A}}$, is approximately distributed as a standard normal when the variables are statistically independent:

${\displaystyle z_{A}={3(n_{c}-n_{d}) \over {\sqrt {n(n-1)(2n+5)/2}}}}$

Thus, to test whether two variables are statistically dependent, one computes ${\displaystyle z_{A}}$, and finds the cumulative probability for a standard normal distribution at ${\displaystyle -|z_{A}|}$. For a 2-tailed test, multiply that number by two to obtain the p-value. If the p-value is below a given significance level, one rejects the null hypothesis (at that significance level) that the quantities are statistically independent.

Numerous adjustments should be added to ${\displaystyle z_{A}}$ when accounting for ties. The following statistic, ${\displaystyle z_{B}}$, has the same distribution as the ${\displaystyle \tau _{B}}$ distribution, and is again approximately equal to a standard normal distribution when the quantities are statistically independent:

${\displaystyle z_{B}={n_{c}-n_{d} \over {\sqrt {v}}}}$

where

${\displaystyle {\begin{array}{ccl}v&=&(v_{0}-v_{t}-v_{u})/18+v_{1}+v_{2}\\v_{0}&=&n(n-1)(2n+5)\\v_{t}&=&\sum _{i}t_{i}(t_{i}-1)(2t_{i}+5)\\v_{u}&=&\sum _{j}u_{j}(u_{j}-1)(2u_{j}+5)\\v_{1}&=&\sum _{i}t_{i}(t_{i}-1)\sum _{j}u_{j}(u_{j}-1)/(2n(n-1))\\v_{2}&=&\sum _{i}t_{i}(t_{i}-1)(t_{i}-2)\sum _{j}u_{j}(u_{j}-1)(u_{j}-2)/(9n(n-1)(n-2))\end{array}}}$

This is sometimes referred to as the Mann-Kendall test.[10]

The direct computation of the numerator ${\displaystyle n_{c}-n_{d}}$, involves two nested iterations, as characterized by the following pseudocode:

numer := 0
for i := 2..N do
    for j := 1..(i − 1) do
        numer := numer + sign(x[i] − x[j]) × sign(y[i] − y[j])
return numer

Although quick to implement, this algorithm is ${\displaystyle O(n^{2})}$ in complexity and becomes very slow on large samples. A more sophisticated algorithm[11] built upon the Merge Sort algorithm can be used to compute the numerator in ${\displaystyle O(n\cdot \log {n})}$ time.

Begin by ordering your data points sorting by the first quantity, ${\displaystyle x}$, and secondarily (among ties in ${\displaystyle x}$) by the second quantity, ${\displaystyle y}$. With this initial ordering, ${\displaystyle y}$ is not sorted, and the core of the algorithm consists of computing how many steps a Bubble Sort would take to sort this initial ${\displaystyle y}$. An enhanced Merge Sort algorithm, with ${\displaystyle O(n\log n)}$ complexity, can be applied to compute the number of swaps, ${\displaystyle S(y)}$, that would be required by a Bubble Sort to sort ${\displaystyle y_{i}}$. Then the numerator for ${\displaystyle \tau }$ is computed as:

${\displaystyle n_{c}-n_{d}=n_{0}-n_{1}-n_{2}+n_{3}-2S(y),}$

where ${\displaystyle n_{3}}$ is computed like ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$, but with respect to the joint ties in ${\displaystyle x}$ and ${\displaystyle y}$.

A Merge Sort partitions the data to be sorted, ${\displaystyle y}$ into two roughly equal halves, ${\displaystyle y_{\mathrm {left} }}$ and ${\displaystyle y_{\mathrm {right} }}$, then sorts each half recursive, and then merges the two sorted halves into a fully sorted vector. The number of Bubble Sort swaps is equal to:

${\displaystyle S(y)=S(y_{\mathrm {left} })+S(y_{\mathrm {right} })+M(Y_{\mathrm {left} },Y_{\mathrm {right} })}$

where ${\displaystyle Y_{\mathrm {left} }}$ and ${\displaystyle Y_{\mathrm {right} }}$ are the sorted versions of ${\displaystyle y_{\mathrm {left} }}$ and ${\displaystyle y_{\mathrm {right} }}$, and ${\displaystyle M(\cdot ,\cdot )}$ characterizes the Bubble Sort swap-equivalent for a merge operation. ${\displaystyle M(\cdot ,\cdot )}$ is computed as depicted in the following pseudo-code:

function M(L[1..n], R[1..m]) is
    i := 1
    j := 1
    nSwaps := 0
    while i ≤ n and j ≤ m do
        if R[j] < L[i] then
            nSwaps := nSwaps + n − i + 1
            j := j + 1
        else
            i := i + 1
    return nSwaps

A side effect of the above steps is that you end up with both a sorted version of ${\displaystyle x}$ and a sorted version of ${\displaystyle y}$. With these, the factors ${\displaystyle t_{i}}$ and ${\displaystyle u_{j}}$ used to compute ${\displaystyle \tau _{B}}$ are easily obtained in a single linear-time pass through the sorted arrays.

• R's statistics base-package implements the test cor.test(x, y, method = "kendall") in its "stats" package (also cor(x, y, method = "kendall") will work, but the latter does not return the p-value).
• For Python, the SciPy library implements the computation of ${\displaystyle \tau }$ in scipy.stats.kendalltau

• Correlation
• Kendall tau distance
• Kendall's W
• Spearman's rank correlation coefficient
• Goodman and Kruskal's gamma
• Theil–Sen estimator
• Mann–Whitney U test - it is equivalent to Kendall's tau correlation coefficient if one of the variables is binary.

• Abdi, H. (2007). "Kendall rank correlation" (PDF). In Salkind, N.J. (ed.). Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage.
• Daniel, Wayne W. (1990). "Kendall's tau". Applied Nonparametric Statistics (2nd ed.). Boston: PWS-Kent. pp. 365–377. ISBN 978-0-534-91976-4.
• Kendall, Maurice; Gibbons, Jean Dickinson (1990) [First published 1948]. Rank Correlation Methods. Charles Griffin Book Series (5th ed.). Oxford: Oxford University Press. ISBN 978-0195208375.
• Bonett, Douglas G.; Wright, Thomas A. (2000). "Sample size requirements for estimating Pearson, Kendall, and Spearman correlations". Psychometrika. 65 (1): 23–28. doi:10.1007/BF02294183. S2CID 120558581.

• Tied rank calculation
• Software for computing Kendall's tau on very large datasets
• Online software: computes Kendall's tau rank correlation