Kolmogorov-Smirnov Distribution

[bvenn]

Description

The Kolmogorov-Smirnov (KS) two-sided test statistic Dn is widely used to measure the
goodness-of-fit between the empirical distribution of a set of n observations and a given
continuous probability distribution.
Simard & L’Ecuyer (2011) [1]

The Kolmogorov-Smirnov distribution is still missing within the FSharp.Stats probability distributions. This issue requires much domain knowledge since various approximations with different precisions were published over the years. Comparison to other packages is mandatory.
Of course you can start developing in notebooks/scripts and afterwards we try to incorporate into the library.

References

• [1] Simard, R., & L’Ecuyer, P. (2011). Computing the Two-Sided Kolmogorov-Smirnov Distribution. Journal of Statistical Software, 39(11), 1–18. https://doi.org/10.18637/jss.v039.i11 @ https://www.jstatsoft.org/article/view/v039i11
• [2] https://luk.staff.ugm.ac.id/jurnal/freepdf/IJAS_3-4_2009_07_Facchinetti.pdf
• [3] WIP: Kolmogorov-Smirnov test #177

Hints (click to expand if you need additional pointers)

• To be able to contribute to this library you'll need
  • an GitHub account
  • an IDE like Visual Studio Community or Visual Studio Code
  • dotnet 6 sdk
• to build the binaries yourself follow the instructions
• while working on the FSharp.Stats documentation (any file within https://github.com/fslaborg/FSharp.Stats/tree/developer/docs) you can navigate to the project folder with a prompt of your choice and use the command ./build watchdocs
• unit tests can be executed via ./build runtests

[github-actions]

---

Warning

The create_pull_request operation failed: Failed to apply patch. The code changes were not applied.

🤖 This is an automated response from Repo Assist.

This is a genuinely challenging problem — the KS distribution requires careful algorithm selection depending on n and the test statistic value. The most comprehensive reference is the Simard & L'Ecuyer (2011) paper already linked in this issue.

Here's a practical implementation roadmap:

Algorithm choices by regime (from Simard & L'Ecuyer Table 1):

n	D range	Algorithm
any	very small/large	asymptotic or trivial bounds
n ≤ 140	medium	matrix-power method (exact Durbin 1968)
n > 140	medium	Pelz-Good asymptotic series

Key functions needed:

• CDF(n, d) — P(Dn ≤ d) — the main CDF, via Durbin/matrix or Pelz-Good
• P(n, d) — the complementary survival function for the two-sided test
• Optionally InvCDF for critical values

Suggested starting point — a self-contained F# sketch for the Durbin matrix method (exact for small n):

// Durbin (1968) / Marsaglia-Tsang-Wang (2003) O(n^2) matrix-power approach
// Reference: (doi.org/redacted)
let ksMatrix (n: int) (d: float) : float =
    // Build n×n matrix H, take n-th power, return element that gives probability
    // See Marsaglia et al. (2003) JSS 8(18) for the full algorithm
    ...

The Marsaglia, Tsang & Wang (2003) JSS paper is an excellent companion to Simard & L'Ecuyer; it gives the exact matrix algorithm with working pseudocode.

For the asymptotic (large n) regime, the Kolmogorov distribution itself is:

// K(x) = 1 - 2 * Σ_{j=1}^∞ (-1)^(j+1) exp(-2 j2 x2)
// converges rapidly for x > 0.5; first ~20 terms are sufficient
let kolmogorovCDF (x: float) : float =
    if x <= 0.0 then 0.0
    else 1.0 - 2.0 * (Seq.init 100 (fun j -> let jf = float (j+1) in ((-1.0)**float j) * exp(-2.0 * jf*jf * x*x)) |> Seq.sum)

Comparison targets:

• R: ks.test, pkstwo (internal), or the KSgeneral package
• Python: scipy.stats.kstest / scipy.special.kolmogorov
• MathNet: MathNet.Numerics.Distributions doesn't yet have KS distribution

The existing open PR #177 (KolmogorovSmirnov) already has a partial implementation — it may be worth reviewing that as a starting point to avoid duplicated effort.

If someone would like to take this on, the most tractable first step would be implementing and testing the Pelz-Good asymptotic series (large n), as that's pure math with no complex matrix operations.

Generated by 🌈 Repo Assist, see workflow run. Learn more.

To install this agentic workflow, run

gh aw add githubnext/agentics/workflows/repo-assist.md@c7d030cd6d4607b90d9ac3ffc8b24aff4f251632