Repository: JuliaStats/HypothesisTests.jl
Pull request #282 (2023-01-03 19:24:10)

Enable the two sided KG Test to deal with Ties.
Performance is comparable, fewer allocations.


Patch:
diff --git a/src/kolmogorov_smirnov.jl b/src/kolmogorov_smirnov.jl
index 7868470..0a9dc77 100644
--- a/src/kolmogorov_smirnov.jl
+++ b/src/kolmogorov_smirnov.jl
@@ -163,9 +163,6 @@ Implements: [`pvalue`](@ref)
 """
 function ApproximateTwoSampleKSTest(x::AbstractVector{T}, y::AbstractVector{S}) where {T<:Real, S<:Real}
     n_x, n_y = length(x), length(y)
-    if n_x+n_y > length(unique([x; y]))
-        @warn("This test is inaccurate with ties")
-    end
 
     ApproximateTwoSampleKSTest(ksstats(x, y)...)
 end
@@ -194,11 +191,28 @@ end
 # compute supremum of differences between empirical cdfs.
 function ksstats(x::AbstractVector{T}, y::AbstractVector{S}) where {T<:Real, S<:Real}
     n_x, n_y = length(x), length(y)
-    sort_idx = sortperm([x; y])
-    pdf_diffs = [ones(n_x)/n_x; -ones(n_y)/n_y][sort_idx]
-    cdf_diffs = cumsum(pdf_diffs)
-    δp = maximum(cdf_diffs)
-    δn = -minimum(cdf_diffs)
-    δ = max(δp, δn)
-    (n_x, n_y, δ, δp, δn)
-end
+    all_values = [x; y]
+    sort_idx = sortperm(all_values)
+    δ_y = 1 / n_y
+    δ_x = 1 / n_x
+    δ = δp = δn = zero(δ_y)
+
+    for i in 1:(n_x + n_y)
+        if sort_idx[i] > n_x
+            δ -= δ_y
+        else
+            δ += δ_x
+        end
+
+        # only update δp/δn if the value is about to change or at the last step.
+        if i == n_x + n_y || all_values[sort_idx[i]] != all_values[sort_idx[i + 1]]
+            if δ > δp
+                δp = δ
+            elseif δ < δn
+                δn = δ
+            end
+        end
+    end
+
+    (n_x, n_y, max(δp, -δn), δp, -δn)
+end   
diff --git a/src/mann_whitney.jl b/src/mann_whitney.jl
index df3a715..1bcd38b 100644
--- a/src/mann_whitney.jl
+++ b/src/mann_whitney.jl
@@ -165,11 +165,11 @@ end
 
 struct ApproximateMannWhitneyUTest{T<:Real} <: HypothesisTest
     U::Float64              # test statistic: Mann-Whitney-U statistic
-    ranks::Vector{T}        # ranks
+    ranks::Vector{Float64}  # ranks
     tie_adjustment::Float64 # adjustment for ties
     nx::Int                 # number of observations
     ny::Int
-    median::Float64         # sample median
+    median::T               # sample median
     mu::Float64             # normal approximation: mean
     sigma::Float64          # normal approximation: std
 end
@@ -200,7 +200,7 @@ where ``\\mathcal{T}`` is the set of the counts of tied values at each tied posi
 Implements: [`pvalue`](@ref)
 """
 function ApproximateMannWhitneyUTest(U::Real, ranks::AbstractVector{T},
-    tie_adjustment::Real, nx::Int, ny::Int, median::Float64) where T<:Real
+    tie_adjustment::Real, nx::Int, ny::Int, median::Real) where T<:Real
     mu = U - nx * ny / 2
     sigma = sqrt((nx * ny * (nx + ny + 1 - tie_adjustment /
         ((nx + ny) * (nx + ny - 1)))) / 12)


Test patch:
diff --git a/test/kolmogorov_smirnov.jl b/test/kolmogorov_smirnov.jl
index 584d3ca..e12bd31 100644
--- a/test/kolmogorov_smirnov.jl
+++ b/test/kolmogorov_smirnov.jl
@@ -81,4 +81,11 @@ t = ExactOneSampleKSTest(x, Uniform())
 @test pvalue(t) ≈ 0.4351284228580825
 @test pvalue(t; tail=:left) ≈ 0.3013310572470338
 @test pvalue(t; tail=:right) ≈ 0.2193143479950862
+
+# Check two samples with ties
+
+t = ApproximateTwoSampleKSTest(ones(10), ones(10))
+@test isapprox(t.δ, 0., atol=1e-16)
+@test isapprox(t.δp, 0., atol=1e-16)
+@test isapprox(t.δn, 0., atol=1e-16)
 end
diff --git a/test/mann_whitney.jl b/test/mann_whitney.jl
index 0f61490..d883db1 100644
--- a/test/mann_whitney.jl
+++ b/test/mann_whitney.jl
@@ -54,6 +54,10 @@ end
     @test abs(@inferred(pvalue(ExactMannWhitneyUTest(Float32[1:10;], Float32[2:11;]))) - 0.5096) <= 1e-4
 end
 
+@testset "Issue #113" begin
+    @test abs(pvalue(ApproximateMannWhitneyUTest(Float32[1:10;], Float32[2:11;])) - 0.4948) <= 1e-4
+end
+
 @testset "Issue #126 pvalues above 1" begin
 	A = [1.34937, 1.75722,0.276514, 1.04546, 1.69085, 0.738085, 2.36313]
 	B = [2.62325, 1.16533, 1.1327, 0.728714]
@@ -73,5 +77,4 @@ end
 	m = ApproximateMannWhitneyUTest(A, B)
 	p = @inferred(pvalue(m; tail = :both))
 end
-
 end