Kendall's Tau

Background

Kendall's tau is a rank-correlation coefficient that measures the strength and direction of association between two variables using concordant minus discordant pairs, normalised by the total number of pairs. Unlike Pearson, it depends only on the ordering of the data — robust to outliers and non-linear monotone transforms. It is the canonical secondary measure used alongside Spearman when LLM-as-judge scores are calibrated against human gold sets.

Problem statement

Implement kendalls_tau(x, y) returning the tau-a statistic:

$$\tau \;=\; \frac{C - D}{\tfrac{1}{2}\,n(n-1)}$$

where $C$ is the number of concordant pairs ($(x_i-x_j)$ and $(y_i-y_j)$ same sign), $D$ is the number of discordant pairs (opposite sign), and the denominator is the total number of pairs.

Input

• x — array-like of floats, length $n \ge 2$.
• y — array-like of floats, same length as x.

Output

Returns a Python float in $[-1, 1]$.

Examples

Example 1 — perfect concordance

Input:  x = [1, 2, 3, 4], y = [10, 20, 30, 40]
Output: 1.0

Example 2 — perfect discordance

Input:  x = [1, 2, 3, 4], y = [40, 30, 20, 10]
Output: -1.0

Example 3 — hand-computed mixed case

Input:  x = [1, 2, 3], y = [2, 1, 3]
Output: 1/3 ≈ 0.3333

Explanation: 3 pairs. (1,2): $\Delta x=+, \Delta y=-$ → discordant. (1,3): both $+$ → concordant. (2,3): both $+$ → concordant. $\tau = (2-1)/3 = 1/3$.

Constraints

• Length mismatch or $n < 2$ raises ValueError.
• Tied pairs (sign $= 0$) contribute neither to $C$ nor $D$ — they're skipped, matching the tau-a convention.
• $O(n^2)$ time. For $n > 10^4$ use the merge-sort variant (out of scope here).

Notes

• vs Spearman. Spearman is Pearson on ranks; Kendall counts inversions directly. They agree on direction but Kendall has tighter confidence intervals at small $n$ and is more robust to outliers.
• tau-a vs tau-b. This is tau-a (no tie correction in the denominator). Tau-b adjusts for tied groups; for large datasets the two differ by < 1%.