ML coding · Statistics in code
Spearman rank correlation (the information coefficient)
Given two equal-length lists x and y, neither constant, return
Spearman's rank correlation: replace each list by its ranks, giving tied values the average of the
ranks they span, and return the Pearson correlation of the two rank vectors.
Examples
Input x = [1, 2, 3, 4], y = [10, 20, 30, 40]
Output 1
Perfectly monotone: 1.
Input x = [1, 2, 3, 4], y = [1, 8, 27, 1000]
Output 1
Pearson is below 1 here; Spearman ignores the scale and gives 1.
Input x = [1, 2, 2, 3], y = [4, 3, 3, 1]
Output -1
Ties share the average rank 2.5. Perfectly reversed: −1.
Constraints
- 2 ≤ n ≤ 10⁵
- Neither list is constant
- Checked to a relative tolerance of 10⁻⁹
Hints
Hint 1
Write one function that ranks a list, and call it on both inputs.
Hint 2
Sort once; a block of equal values occupying sorted positions i..j all get rank (i + j)/2 + 1.
Hint 3
Centre both rank vectors, then r = Σ(ab)/√(Σa² · Σb²).
Where candidates go wrong
- Using 1 − 6Σd²/(n(n² − 1)). It is exact only without ties, and the third example has them.
- Ranking with argsort(argsort(·)), which gives tied values distinct ranks.
- Computing Pearson on the raw values.
The idea
Rank both series with average ranks, which makes the statistic depend only on order and treats ties symmetrically. Then compute an ordinary Pearson correlation of the ranks. The closed-form shortcut in terms of rank differences assumes ranks are a permutation of 1…n, which ties break; computing Pearson directly is exact in every case and costs the same.
Time O(n log n) · Space O(n)
Reference solution
import numpy as np
def average_ranks(a):
a = np.asarray(a, dtype=float)
order = np.argsort(a, kind='mergesort')
srt = a[order]
ranks = np.empty(len(a))
i = 0
while i < len(a):
j = i
while j + 1 < len(a) and srt[j + 1] == srt[i]:
j += 1
ranks[order[i:j + 1]] = (i + j) / 2 + 1 # ties share the mean of their ranks
i = j + 1
return ranks
def spearman(x, y):
rx, ry = average_ranks(x), average_ranks(y)
rx -= rx.mean()
ry -= ry.mean()
return float(rx @ ry / np.sqrt((rx @ rx) * (ry @ ry)))Follow-ups an interviewer asks
- Compute the information coefficient cross-sectionally for each date and report its mean and t-statistic.
- Kendall's tau: count concordant and discordant pairs in O(n log n) with a merge sort.
- Why is a mean IC of 0.03 considered a useful signal? Relate it to the Sharpe ratio through breadth (the fundamental law of active management).
Python runs in your browser with NumPy. The first run downloads the runtime, which takes a few seconds.
Why interviewers ask it
In systematic trading, a signal is judged by its information coefficient, the rank correlation between its value today and returns tomorrow. Quant research interviews ask for it because it tests ranking with ties and the difference between Pearson and Spearman in one short function.
The theory behind it is in the lesson Statistics coding questions: variance, AUC and rank correlation.
Keep going
Running mean and variance in one pass
Report the mean and sample variance after every value of a stream, accurately, even for values near 10⁹.
Open the problem → Medium20 minROC AUC from scores, with ties
Compute the area under the ROC curve in O(n log n) from ranks, with tied scores counted as one half.
Open the problem → Medium15 minSpearman rank correlation (the information coefficient)
Rank both series with average ranks for ties and take the Pearson correlation of the ranks.
Open the problem →