Kolmogorov-Smirov two sample test, ties — will adding random noise fix the problem?

Question

There are a lot of questions on this site about warning for "ties" in the Kolmogorov-Smirnov test. Here are a few of those questions.

Is there an alternative to the Kolmogorov-Smirnov test for tied data with correction?

https://stackoverflow.com/questions/51987605/problems-with-ks-test-and-ties

"Ties should not be present" in one-sample Kolmgorov-Smirnov test in R

I understand that if there are repeated values in a test sample, then that will throw off the K-S test and generate the warning. However, I have not really seen any of these posts indicate a solution to the problem. Certainly removing repeated values will just change the distribution of the data, so that is not a particularly good solution.

I was thinking that I could just add some random noise to the data, to essentially "jitter" the data. So if I added random normal noise to each observation with mean = 0.0 and variance = 0.01, wouldn't that break the ties and let me perform the test without any problems. My sample size is pretty large, so this should cancel out any artifacts from the addition of noise.

I can run some simulations to try out my idea, but just wanted to see if anyone saw any obvious issues with this approach?

Answer 1

It may be dangerous to base conclusions on one comparison, but at least a close look at one dataset may focus attention on where one must be careful. Absent information as to your sample sizes, I'll compare two gamma samples of size 100.

We begin with simulated data expressed to enough decimal places to avoid any ties. The K-S test has P-value 0.037. With samples of size 100 of modest skewness a Welch t test seems appropriate; it has P-value 0.004. A Wilcoxon rank sum test may not be appropriate because populations are of slightly different shapes, but I include it because it's another test that can be fussy about ties. It has P-value 0.019.

set.seed(623)
x = rgamma(100, 3, .3)
y = rgamma(100, 3, .4)
ks.test(x,y)

        Two-sample Kolmogorov-Smirnov test

data:  x and y
D = 0.2, p-value = 0.03663
alternative hypothesis: two-sided

t.test(x,y)$p.val
[1] 0.00394733
wilcox.test(x,y)$p.val
[1] 0.01943391

Now, to cause trouble with ties, I round data to integers. I get a lot of ties. The K-S test gives P-value 0.054 (not significant at 5%) along with a warning that the P-value may be wrong. The t.test hardly notices the rounding. The Wilcoxon test (wilcox.test in R) seems to rely on approximate P-values for $n \ge 50,$ R gives no warning that the P-value may be wrong. With rounding the P-value is $0.022,$ not much changed from 0.019 above.

xr = round(x); yr = round(y)
length(unique(xr));  length(unique(yr))
[1] 25
[1] 17
ks.test(xr,yr)

        Two-sample Kolmogorov-Smirnov test

data:  xr and yr
D = 0.19, p-value = 0.0541
alternative hypothesis: two-sided

Warning message:
In ks.test(xr, yr) : p-value will be approximate 
  in the presence of ties
t.test(xr,yr)$p.val
[1] 0.004182795
wilcox.test(xr,yr)$p.val
[1] 0.02176584

The K-S test compares the empirical CDFs (ECDFs) of the two samples. Its $D$-statistic is the maximum vertical discrepancy between the two ECDFs. The plots below compare ECDFs for the original data (left) with those for the rounded data. The two plots are similar, but it is easy to see that the maximum vertical discrepancy (somewhere around data values 15) has decreased a bit from $D=.20$ to $D=.19$ with rounding. I would beware of any jittering scheme that made a large difference in $D$-values.

par(mfrow=c(1,2))
 plot(ecdf(x), col="blue", main="Original")
  lines(ecdf(y), col="orange2")
 plot(ecdf(xr), col="blue", main="Rounded")
  lines(ecdf(yr), col="orange2")
par(mfrow=c(1,1)) 

In order to get rid of ties I jitter using 'noise' from $\mathsf{UNIF}(-.1,.1).$ Three iterations of the jittering show some variations in the P-values of the K-S test (0.010, 0.037, 0.025) and smaller variations (0,016, 0.020, 0.020) for Wilcoxon tests, as shown below. (In R, you can remove suffixes $p.val to see the entire printouts.)

set.seed(624)
xr.j1 = xr + runif(100,-.1,.1)
yr.j1 = yr + runif(100,-.1,.1)
ks.test(xr.j1,yr.j1)$p.val
[1] 0.01008352
t.test(xr.j1,yr.j1)$p.val
[1] 0.003858734
wilcox.test(xr.j1,yr.j1)$p.val
[1] 0.01572269

xr.j2 = xr + runif(100,-.1,.1)
yr.j2 = yr + runif(100,-.1,.1)
ks.test(xr.j2,yr.j2)$p.val
[1] 0.03663105
t.test(xr.j2,yr.j2)$p.val
[1] 0.004285968
wilcox.test(xr.j2,yr.j2)$p.val
[1] 0.01994782

xr.j3 = xr + runif(100,-.1,.1)
yr.j3 = yr + runif(100,-.1,.1)
ks.test(xr.j3,yr.j3)$p.val
[1] 0.02431031
t.test(xr.j3,yr.j1)$p.val
[1] 0.004103491
wilcox.test(xr.j3,yr.j1)$p.val
[1] 0.0196894

The larger variations for the K-S test seem capable of changing conclusions---especially, as here, with P-values hovering in the range between 1% and 5%. A simulation with 100,000 jitterings shows the the variation of K-S P-values in greater detail.

While jittered K-S tests reject about 95% of the time and P-values average about 0.3, P-values overall span values from 0.002 to 0.054. I would want to use jittering for K-S tests only with great care.

set.seed(2020)
pv.ksj = replicate(10^5,
            ks.test(xr+runif(100,-.1,.1),
               yr+runif(100,-.1,.1))$p.val)
mean(pv.ksj <= .05)
[1] 0.94522
mean(pv.ksj)
[1] 0.02633538
summary(pv.ksj)
    Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
0.002318 0.015814 0.024310 0.026335 0.036631 0.054103 

Answer 2

Any time you find yourself having to 'inject noise' into your data, something has probably went wrong in the modelling process (most likely you are making an assumption that the distribution is continuous when its actually discrete).

If there are ties in your data then at least part of the generating distribution is discrete, and so a goodness-of-fit statistic which incorporates this should be chosen instead (eg a chi-square test), otherwise you can compute the p-value of the Kolmogorov-Smirnov test statistic yourself using a permutation test rather than relying on the default approximations which assume continuous data.

By the way, Kolmogorov-Smirnov isnt a great test since it only looks at a single point of the empirical distribution (its maximum). A better test which is usually more powerful is Cramer-von-Mises which instead looks at the average value. The Lepage test is also often a sensible choice. See https://www.tandfonline.com/doi/abs/10.1080/02664760220136212

As above, you should use a permutation test to get p-values for all of these statistics (assuming that you are doing a two-sample test), since the built-in p-values in R assume continuous data .