// Catalano Statistics Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2016
// diego.catalano at live.com
//
// Copyright © César Souza, 2009-2013
// cesarsouza at gmail.com
//
// Copyright © Richard Simard, 2010
// Copyright © Pierre L'Ecuyer, 2010
// This source code is based on the original work by Simar and Ecuyer.
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
//

package Catalano.Statistics.Distributions;

import Catalano.Math.Constants;
import Catalano.Math.Matrix;
import Catalano.Math.Special;

/**
 * Kolmogorov-Smirnov distribution.
 * @author Diego Catalano
 */
public class KolmogorovSmirnovDistribution implements IDistribution{
    
    private static int eV;
    
    private int numberOfSamples;

    public int getNumberOfSamples() {
        return numberOfSamples;
    }

    public void setNumberOfSamples(int numberOfSamples) {
        this.numberOfSamples = numberOfSamples;
    }

    public KolmogorovSmirnovDistribution(int samples) {
        this.numberOfSamples = samples;
    }

    @Override
    public double Mean() {
        return Constants.SqrtHalfPI * Constants.Log2 / Math.sqrt(numberOfSamples);
    }

    @Override
    public double Variance() {
        return ((Math.PI * Math.PI) / 12 - (Mean() * Mean())) / numberOfSamples;
    }

    @Override
    public double Entropy() {
        throw new UnsupportedOperationException("Not supported");
    }

    @Override
    public double DistributionFunction(double x) {
        return CumulativeFunction(numberOfSamples, x);
    }

    @Override
    public double ProbabilityDensityFunction(double x) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public double LogProbabilityDensityFunction(double x) {
        throw new UnsupportedOperationException("Not supported.");
    }
    
    public double ComplementaryDistributionFunction(double x){
        return ComplementaryDistributionFunction(numberOfSamples, x);
    }
    
    /**
     * Computes the Upper Tail of the P[Dn >= x] distribution.
     * @param x Value.
     * @return Result.
     */
    public double OneSideDistributionFunction(double x){
        return OneSideUpperTail(numberOfSamples, x);
    }
    
    public static double CumulativeFunction(int n, double x){
        double nxx = n * x * x; // nx²

        // First of all, check if the given values do not represent
        // a special case. There are some combination of values for
        // which the distribution has a known, exact solution.

        // Ruben-Gambino
        if (x >= 1.0 || nxx >= 18.0)
            return 1.0;

        if (x <= 0.5 / n)
            return 0.0;

        if (n == 1)
            return 2.0 * x - 1.0;

        if (x <= 1.0 / n)
            return (n <= 20) ? Special.Factorial(n) * Math.pow(2.0 * x - 1.0 / n, n)
                : Math.exp(Special.LogFactorial(n) + n * Math.log(2.0 * x - 1.0 / n));

        if (x >= 1.0 - 1.0 / n)
            return 1.0 - 2.0 * Math.pow(1.0 - x, n);

        // This is not a special case. Continue processing to
        //  select the most adequade method for the given inputs

        if (n <= 140)
        {
            // This is the first case (i) as referred in Simard's
            // paper. Use exact algorithms depending on nx² with
            // at least 13 to 15 decimal digits of precision.

            // Durbin
            if (nxx < 0.754693)
                return Durbin(n, x);

            // Pomeranz
            if (nxx < 4.0)
                return Pomeranz(n, x);

            // Complementary CDF
            return 1.0 - ComplementaryDistributionFunction(n, x);
        }
        else
        {
            if (n <= 100000)
            {
                // This is the second case (ii) referred in Simard's
                // paper. Use either the Durbin approximation or the
                // Pelz-Good asymptotic series depending on nx^(3/2).

                // Obs:
                //
                //   x^(3/2) = x^(1 + 1/2) = x*x^(1/2) = x*sqrt(x)
                //
                //          (n*x)      * sqrt(x) <= 1.40
                //   sqrt((n*x)*(n*x)) * sqrt(x) <= 1.40
                //   sqrt((n*x)*(n*x)  *      x) <= 1.40
                //        (n*x)*(n*x)  *      x  <= 1.96
                //       
                //    n*n*x*x*x <= 1.96
                //

                if (n * nxx * x <= 1.96)
                    return Durbin(n, x);
                else return PelzGood(n, x);
            }
            else
            {
                // This is the third case (iii) as referred in Simard's
                // paper. Use only the Pelz-Good asymptotic series.
                return PelzGood(n, x);
            }
        }
    }
    
    /**
     * Computes the Complementary Cumulative Distribution Function (1-CDF) for the Kolmogorov-Smirnov statistic's distribution.
     * @param n The sample size.
     * @param x The Kolmogorov-Smirnov statistic.
     * @return Under a sample size n.
     */
    public static double ComplementaryDistributionFunction(int n, double x){
        double nxx = n * x * x; // nx²

        // First of all, check if the given values do not represent
        // a special case. There are some combination of values for
        // which the distribution has a known, exact solution.

        // Ruben-Gambino's Complement
        if (x >= 1.0 || nxx >= 370.0)
            return 0.0;

        if (x <= 0.5 / n || nxx <= 0.0274)
            return 1.0;

        if (n == 1)
            return 2.0 - 2.0 * x;

        if (x <= 1.0 / n)
            return (n <= 20) ? 1.0 - Special.Factorial(n) * Math.pow(2.0 * x - 1.0 / n, n)
                : 1.0 - Math.exp(Special.LogFactorial(n) + n * Math.log(2.0 * x - 1.0 / n));

        if (x >= 1.0 - 1.0 / n)
            return 2.0 * Math.pow(1.0 - x, n);

        // This is not a special case. Continue processing to
        //  select the most adequade method for the given inputs

        if (n <= 140)
        {
            // This is the first region (i) of the complementary
            // CDF as detailed in Simard's paper. It is further
            // divided into two sub-regions.
            if (nxx >= 4.0)
            {
                // For x close to one, Simard's advocates the use of the one-
                // sided Kolmogorov-Smirnov statistic as given by Miller (1956).
                return 2 * OneSideUpperTail(n, x);
            }
            else
            {
                // For higher values of x, the direct cumulative 
                // distribution will be giving enough precision.
                return 1.0 - CumulativeFunction(n, x);
            }
        }
        else
        {
            // This is the second region (ii) of the complementary
            // CDF discussed in Simard's paper. It is again divided
            // into two sub-regions depending on the value of nx².
            if (nxx >= 2.2)
            {
                // In this region, the Miller approximation returns
                // at least 6 digits of precision (Simard, 2010).
                return 2 * OneSideUpperTail(n, x);
            }
            else
            {
                // In this region, the direct cumulative
                // distribution will give enough precision.
                return 1.0 - CumulativeFunction(n, x);
            }
        }
    }
    
    /**
     * Pelz-Good algorithm for computing lower-tail areas of the Kolmogorov-Smirnov distribution.
     */
    public static double PelzGood(int n, double x){
        final int maxTerms = 20;
        final double eps = 1.0e-10;

        final double PI2 = Math.PI * Math.PI;
        final double PI4 = PI2 * PI2;

        double sqrtN = Math.sqrt(n);

        double z = sqrtN * x;
        double z2 = z * z;
        double z3 = z2 * z;
        double z4 = z2 * z2;
        double z5 = z4 * z;
        double z6 = z4 * z2;
        double z7 = z4 * z3;
        double z8 = z4 * z4;
        double z10 = z8 * z2;

        double pz = -PI2 / (2 * z2);
        double term;


        double k0 = 0; // Evaluate K0(z)
        for (int k = 0; k <= maxTerms; k++)
        {
            double h = (k + 0.5);
            k0 += term = Math.exp(h * h * pz);
            if (term <= eps * k0) break;
        }


        double k1 = 0; // Evaluate K1(z)
        for (int k = 0; k <= maxTerms; k++)
        {
            double hh = (k + 0.5) * (k + 0.5);
            k1 += term = (PI2 * hh - z2) * Math.exp(hh * pz);
            if (Math.abs(term) <= eps * Math.abs(k1)) break;
        }


        double k2a = 0; // Evaluate 1st part of K2(z)
        for (int k = 0; k <= maxTerms; k++)
        {
            double hh = (k + 0.5) * (k + 0.5);
            k2a += term = (6 * z6 + 2 * z4
                        + PI2 * (2 * z4 - 5 * z2) * hh
                        + PI4 * (1 - 2 * z2) * hh * hh) * Math.exp(hh * pz);
            if (Math.abs(term) <= eps * Math.abs(k2a)) break;
        }

        double k2b = 0; // Evaluate 2nd part of K2(z)
        for (int k = 1; k <= maxTerms; k++)
        {
            double kk = k * k;
            k2b += term = PI2 * kk * Math.exp(kk * pz);
            if (term <= eps * k2b) break;
        }


        double k3a = 0; // Evaluate 1st part of K3(z)
        for (int k = 0; k <= maxTerms; k++)
        {
            double hh = (k + 0.5) * (k + 0.5);
            k3a += term = (-30 * z6 - 90 * z8
                + PI2 * (135 * z4 - 96 * z6) * hh
                + PI4 * (212 * z4 - 60 * z2) * hh * hh
                + PI2 * PI4 * hh * hh * hh * (5 - 30 * z2)) * Math.exp(hh * pz);
            if (Math.abs(term) <= eps * Math.abs(k3a)) break;
        }

        double k3b = 0; // Evaluate 2nd part of K3(z)
        for (int k = 1; k <= maxTerms; k++)
        {
            double kk = k * k;
            k3b += term = (3 * PI2 * kk * z2 - PI4 * kk * kk) * Math.exp(kk * pz);
            if (Math.abs(term) <= eps * Math.abs(k3b)) break;
        }


        // Evaluate the P[sqrt(N) * Dn <= z | H0]
        double sum = k0 * (Constants.Sqrt2PI / z)
                    + k1 * (Constants.SqrtHalfPI / (sqrtN * 3.0 * z4))
                    + k2a * (Constants.SqrtHalfPI / (n * 36.0 * z7))
                    - k2b * (Constants.SqrtHalfPI / (n * 18.0 * z3))
                    + k3a * (Constants.SqrtHalfPI / (n * sqrtN * 3240.0 * z10))
                    + k3b * (Constants.SqrtHalfPI / (n * sqrtN * 108.0 * z6));

        return sum;
    }
    
    /**
     * Computes the Upper Tail of the P[Dn >= x] distribution.
     */
    public static double OneSideUpperTail(int n, double x) {
        if (n > 200000)
        {
            // Use an asymptotic formula for n too high
            double t = (6 * n * x + 1.0);
            double z = t * t / (18 * n);
            double v = (1.0 - (2 * z * z - 4 * z - 1.0) / (18 * n)) * Math.exp(-z);

            if (v <= 0.0) return 0.0;
            if (v >= 1.0) return 1.0;
            else return 1.0 * v;
        }
        else
        {
            // Use Smirnov's stable formula for computing Pn+, the upper tail of
            // the one-sided Kolmogorov's statistic Dn+. This upper tail of the
            // one-sided statistic can then be used to approximate the upper tail
            // Pn of the Kolmogorov statistic Dn with Pn ~ 2*Pn+.

            int jmax = (int)(n * (1.0 - x));
            if ((1.0 - x - (double)jmax / n) <= 0.0)
                jmax--;

            // Initialize
            int jdiv = (n > 3000) ? 2 : 3;
            int jstart = jmax / jdiv + 1;

            double logBinomial = Special.LogBinomial(n, jstart);
            double LOGJMAX = logBinomial;
            double EPSILON = 1.0E-12;


            // Start computing the series
            double sum = 0;

            for (int j = jstart; j <= jmax; j++)
            {
                double q = (double)j / n + x;
                double term = logBinomial + (j - 1) * Math.log(q) + (n - j) * Special.Log1p(-q);
                double t = Math.exp(term);

                sum += t;
                logBinomial += Math.log((double)(n - j) / (j + 1));

                if (t <= sum * EPSILON)
                    break;
            }

            jstart = jmax / jdiv;
            logBinomial = LOGJMAX + Math.log((double)(jstart + 1) / (n - jstart));

            for (int j = jstart; j > 0; j--)
            {
                double q = (double)j / n + x;
                double term = logBinomial + (j - 1) * Math.log(q) + (n - j) * Special.Log1p(-q);
                double t = Math.exp(term);

                sum += t;
                logBinomial += Math.log((double)j / (n - j + 1));

                if (t <= sum * EPSILON)
                    break;
            }


            return sum * x + Math.exp(n * Special.Log1p(-x));
        }
    }
    
    /**
     * Pomeranz algorithm.
     */
    public static double Pomeranz(int n, double x){
        // The Pomeranz algorithm to compute the KS distribution
        double EPS = 1.0e-15;
        int ENO = 350;
        double RENO = Math.pow(2, ENO); // for renormalization of V
        int renormalizations;
        double t = n * x;
        double w, sum, minsum;
        int k, s;
        int r1, r2; // Indices i and i-1 for V[i][]
        int jlow, jup, klow, kup, kup0;

        double[] A = new double[2 * n + 3];
        double[] floors = new double[2 * n + 3];
        double[] ceilings = new double[2 * n + 3];

        double[][] V = new double[2][];
        for (int j = 0; j < V.length; j++)
            V[j] = new double[n + 2];

        double[][] H = new double[4][];     // = pow(w, j) / Factorial(j)
        for (int j = 0; j < H.length; j++)
            H[j] = new double[n + 2];

        double z = computeLimits(t, floors, ceilings);

        computeA(n, A, z);
        computeH(n, A, H);

        V[1][1] = RENO;
        renormalizations = 1;

        r1 = 0;
        r2 = 1;
        for (int i = 2; i <= 2 * n + 2; i++)
        {
            jlow = (int)(2 + floors[i]);
            if (jlow < 1)
                jlow = 1;
            jup = (int)(ceilings[i]);
            if (jup > n + 1)
                jup = n + 1;

            klow = (int)(2 + floors[i - 1]);
            if (klow < 1)
                klow = 1;
            kup0 = (int)(ceilings[i - 1]);

            // Find to which case it corresponds
            w = (A[i] - A[i - 1]) / n;
            s = -1;
            for (int j = 0; j < 4; j++)
            {
                if (Math.abs(w - H[j][1]) <= EPS)
                {
                    s = j;
                    break;
                }
            }

            minsum = RENO;
            r1 = (r1 + 1) & 1;          // i - 1
            r2 = (r2 + 1) & 1;          // i

            for (int j = jlow; j <= jup; j++)
            {
                kup = kup0;
                if (kup > j)
                    kup = j;
                sum = 0;
                for (k = kup; k >= klow; k--)
                    sum += V[r1][k] * H[s][j - k];
                V[r2][j] = sum;
                if (sum < minsum)
                    minsum = sum;
            }

            if (minsum < 1.0e-280)
            {
                // V is too small: renormalize to avoid underflow of probabilities
                for (int j = jlow; j <= jup; j++)
                    V[r2][j] *= RENO;
                renormalizations++;              // keep track of log of RENO
            }
        }

        sum = V[r2][n + 1];
        w = Special.LogFactorial(n) - renormalizations * ENO * Constants.Log2 + Math.log(sum);
        if (w >= 0)
            return 1;
        return Math.exp(w);
    }
    
    /**
     * Durbin's algorithm for computing P[Dn < d]
     */
    public static double Durbin(int n, double d) {
        double s;

        int k = (int)(n * d) + 1;
        int m = 2 * k - 1;
        double h = k - n * d;
        double[][] H = new double[m][m];
        double[][] Q = new double[m][m];
        double[][] B = new double[m][m];


        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                if (i - j + 1 >= 0)
                    H[i][j] = 1;

        for (int i = 0; i < m; i++)
        {
            H[i][0] -= Math.pow(h, i + 1);
            H[m - 1][i] -= Math.pow(h, m - i);
        }

        H[m - 1][0] += (2 * h - 1 > 0 ? Math.pow(2 * h - 1, m) : 0);

        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                if (i - j + 1 > 0)
                    for (int g = 1; g <= i - j + 1; g++)
                        H[i][j] /= g;

        int pQ = 0;
        matrixPower(H, 0, Q, m, n, B);

        s = Q[k - 1][k - 1];

        for (int i = 1; i <= n; i++)
        {
            s *= (double)i / n;
            if (s < 1.0e-140)
            {
                s *= 1.0e140;
                pQ -= 140;
            }
        }

        return s * Math.pow(10.0, pQ);
    }
    
    /**
     * Computes matrix power. Used in the Durbin algorithm.
     */
    private static void matrixPower(double[][] A, int eA, double[][] V, int m, int n, double[][] B) {
        if (n == 1)
        {
            for (int i = 0; i < m; i++)
                for (int j = 0; j < m; j++)
                    V[i][j] = A[i][j];
            eV = eA;
            return;
        }

        matrixPower(A, eA, V, m, n / 2, B);
        
        B = Matrix.Multiply(V, B);

        int eB = 2 * eV;
        if (B[m / 2][m / 2] > 1.0e140)
        {
            for (int i = 0; i < m; i++)
                for (int j = 0; j < m; j++)
                    B[i][j] *= 1.0e-140;
            eB += 140;
        }

        if (n % 2 == 0)
        {
            for (int i = 0; i < m; i++)
                for (int j = 0; j < m; j++)
                    V[i][j] = B[i][j];
            eV = eB;
        }
        else
        {
            V = Matrix.Multiply(A, B);
            eV = eA + eB;
        }

        if (V[m / 2][m / 2] > 1.0e140)
        {
            for (int i = 0; i < m; i++)
                for (int j = 0; j < m; j++)
                    V[i][j] *= 1.0e-140;
            eV += 140;
        }
    }
    
    /**
     * Initializes the Pomeranz algorithm.
     */
    private static double computeLimits(double t, double[] floors, double[] ceilings){
        double floor = Math.floor(t);
        double ceiling = Math.ceil(t);

        double z = t - floor;
        double w = ceiling - t;

        if (z > 0.5)
        {
            for (int i = 1; i < floors.length; i += 2)
                floors[i] = i / 2 - 1 - floor;
            for (int i = 2; i < floors.length; i += 2)
                floors[i] = i / 2 - 2 - floor;
            for (int i = 1; i < ceilings.length; i += 2)
                ceilings[i] = i / 2 + 1 + floor;
            for (int i = 2; i < ceilings.length; i += 2)
                ceilings[i] = i / 2 + floor;
        }
        else if (z > 0.0)
        {
            ceilings[1] = 1 + floor;
            for (int i = 1; i < floors.length; i++)
                floors[i] = i / 2 - 1 - floor;
            for (int i = 2; i < ceilings.length; i++)
                ceilings[i] = i / 2 + floor;
        }
        else // if (z == 0)
        {
            for (int i = 1; i < floors.length; i += 2)
                floors[i] = i / 2 - floor;
            for (int i = 2; i < floors.length; i += 2)
                floors[i] = i / 2 - 1 - floor;
            for (int i = 1; i < ceilings.length; i += 2)
                ceilings[i] = i / 2 + floor;
            for (int i = 2; i < ceilings.length; i += 2)
                ceilings[i] = i / 2 - 1 + floor;
        }

        if (w < z) z = w;

        return z;
    }
    /**
     * Creates matrix A of the Pomeranz algorithm.
     */
    private static void computeA(int n, double[] A, double z){
        A[0] = 0;
        A[1] = 0;
        A[2] = z;
        A[3] = 1 - z;

        for (int i = 4; i < A.length - 1; i++)
            A[i] = A[i - 2] + 1;

        A[A.length - 1] = n;
    }
    
    /**
     * Computes matrix H of the Pomeranz algorithm.
     */
    private static double computeH(int n, double[] A, double[][] H){
        // Precomputes H[][] = (A[j] - A[j-1]^k / k!

        double w;
        H[0][0] = 1;
        w = 2.0 * A[2] / n;
        for (int j = 1; j <= n + 1; j++)
            H[0][j] = w * H[0][j - 1] / j;

        H[1][0] = 1;
        w = (1.0 - 2.0 * A[2]) / n;
        for (int j = 1; j <= n + 1; j++)
            H[1][j] = w * H[1][j - 1] / j;

        H[2][0] = 1;
        w = A[2] / n;
        for (int j = 1; j <= n + 1; j++)
            H[2][j] = w * H[2][j - 1] / j;

        H[3][0] = 1;
        for (int j = 1; j <= n + 1; j++)
            H[3][j] = 0;
        return w;
    }
    
}

 

Ads help maintain this website.