Kolmogorov-Smirnov Statistic

Compute the two-sample Kolmogorov-Smirnov (KS) statistic between two samples.

The KS statistic is another way to detect drift in a numeric feature, and it needs no bins. It is the largest vertical gap between the two empirical CDFs:

F_a(v) = fraction of values in a that are <= v
F_b(v) = fraction of values in b that are <= v
D      = max over v of |F_a(v) - F_b(v)|

Both CDFs are step functions that only change at sample values, so you only need to check v at every value in a and b. D is 0 for identical samples and 1 when every value of one sample is below every value of the other.

Function signature

def ks_statistic(a, b):

Example

Input

ks_statistic(np.array([1.0, 2.0, 3.0]), np.array([2.0, 3.0, 4.0, 5.0]))

Output

0.5

Reasoning

At v = 3, all of a is at or below v, so F_a = 1. Only 2 and 3 from b are at or below it, so F_b = 0.5. The gap of 0.5 is the largest at any sample value.

Constraints and notes

• The samples are 1D and can have different lengths. Values can repeat.
• Use <= in the CDF. With ties, a strict < gives wrong answers.
• Sorting both samples once and using np.searchsorted gives O(n log n).