/*
 * Copyright (C) 2018 Edward Raff 
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package jsat.distributions.discrete;

import static jsat.math.SpecialMath.*;
import static java.lang.Math.*;
import jsat.math.Function1D;
import jsat.math.rootfinding.Bisection;


/**
 * This class provides an implementation of the Zipf distribution, a power-law
 * type distribution for discrete values.
 *
 * @author Edward Raff 
 */
public class Zipf extends DiscreteDistribution
{
    private double cardinality;
    private double skew;
    /**
     * Both variants of the Zipf distribution re-use a term of Zeta(1+skew) or Harmonic(cardinality, 1+skew) for most calculations. This value caches this commonly used constant
     */
    private double denomCache;

    /**
     * Creates a new Zipf distribution
     * @param cardinality the number of possible selections (or {@link Double#POSITIVE_INFINITY})
     * @param skew the skewness of the distribution (must be positive value)
     */
    public Zipf(double cardinality, double skew)
    {
        setCardinality(cardinality);
        setSkew(skew);
    }
    
    /**
     * Creates a new Zipf distribution for a set of infinite cardinality
     * @param skew the skewness of the distribution (must be positive value)
     */
    public Zipf(double skew)
    {
        this(Double.POSITIVE_INFINITY, skew);
    }
    
    /**
     * Creates a new Zipf distribution of infinite cardinality and
     * {@link #setSkew(double) skewness} of 1.
     */
    public Zipf()
    {
        this(1.0);
    }

    /**
     * Copy constructor
     * @param toCopy the object to copy
     */
    public Zipf(Zipf toCopy)
    {
        this.cardinality = toCopy.cardinality;
        this.skew = toCopy.skew;
        this.denomCache = toCopy.denomCache;
    }
    
    /**
     * Sets the cardinality of the distribution, defining the maximum number of
     * items that Zipf can return.
     *
     * @param cardinality the maximum output range of the distribution, can be
     * {@link Double#POSITIVE_INFINITY infinite}.
     */
    public void setCardinality(double cardinality)
    {
        if (cardinality < 0 || Double.isNaN(cardinality))
            throw new IllegalArgumentException("Cardinality must be a positive integer or infinity, not " + cardinality);
        this.cardinality = Math.ceil(cardinality);
        fixCache();
    }

    /**
     * 
     * @return the cardinality (maximum value) of the distribution
     */
    public double getCardinality()
    {
        return cardinality;
    }

    /**
     * Sets the skewness of the distribution. Lower values spread out the
     * probability distribution, while higher values concentrate on the lowest
     * ranks.
     *
     * @param skew the positive value for the distribution's skew
     */
    public void setSkew(double skew)
    {
        if(skew <= 0 || Double.isNaN(skew) || Double.isInfinite(skew))
            throw new IllegalArgumentException("Skew must be a positive value, not " + skew);
        this.skew = skew;
        fixCache();
    }

    private void fixCache()
    {
        if (Double.isInfinite(cardinality))
            denomCache = zeta(1 + skew);
        else
            denomCache = harmonic(cardinality, 1 + skew);
    }

    /**
     * 
     * @return the skewness of the distribution
     */
    public double getSkew()
    {
        return skew;
    }
    
    
    @Override
    public double pmf(int x)
    {
        if(x < 1)
            return 0;
        
        if(Double.isInfinite(cardinality))
        {
            //x^(-1 - skew)/Zeta[1 + skew]
            return pow(x, -skew-1)/denomCache;
        }
        else
        {
            if(x > cardinality)
                return 0;
            //x^(-1-skew)/HarmonicNumber[cardinality,1+skew]
            return pow(x, -skew-1)/denomCache;
        }
    }

    @Override
    public double cdf(int x)
    {
        if (x < 1)
            return 0;
        if (x >= cardinality)
            return 1;
        
        if(Double.isInfinite(cardinality))
        {
            //HarmonicNumber[x,1+skew]/Zeta[1+skew]
            return harmonic(x, 1+skew)/denomCache;
        }
        else
        {
            //HarmonicNumber[x,1+skew]/HarmonicNumber[cardinality,1+skew]
            return harmonic(x, 1+skew)/denomCache;
        }
    }

    @Override
    public double invCdf(double p)
    {
        return invCdfRootFinding(p, Math.max(1/cardinality, 1e-14));
    }

    @Override
    protected double invCdfRootFinding(double p, double tol)
    {
        if (p < 0 || p > 1)
            throw new ArithmeticException("Value of p must be in the range [0,1], not " + p);
        //two special case checks, as they can cause a failure to get a positive and negative value on the ends, which means we can't do a search for the root
        //Special case check, p < min value
        if(min() >= Integer.MIN_VALUE)
            if(p <= cdf(min()))
                return min();
        //special case check, p >= max value
        if(max() < Integer.MAX_VALUE)
            if(p > cdf(max()-1))
                return max();
        //stewpwise nature fo discrete can cause problems for search, so we will use a smoothed cdf to pass in

        //Skip default interpolated, compute smooth directly to half cost
        double cnst = p*denomCache;
        Function1D cdfInterpolated = (double x) ->
        {
            double query = x;
            //smooth variants of CDF
            if (Double.isInfinite(cardinality))
                return harmonic(x, 1 + skew)  - cnst;
            else
                return harmonic(x, 1 + skew) - cnst;
        };
        
        
        double a =  min();
        double b = Double.isInfinite(max()) ? Integer.MAX_VALUE*.95 : max();
        
        //Normally would use Zero-in, but Zipf has bad behavior and it just degrades to bisection + overhead 
        double toRet = Bisection.root(tol, a, b, cdfInterpolated);
        return Math.min(Math.round(toRet), cardinality);
    }

    @Override
    public Zipf clone()
    {
        return new Zipf(this);
    }

    @Override
    public double mean()
    {
        if(Double.isInfinite(cardinality))
        {
            if(skew <= 1)
                return Double.POSITIVE_INFINITY;
            //Zeta[skew]/Zeta[1+skew]
            return zeta(skew)/denomCache;
        }
        else
        {
            //HarmonicNumber[cardinality, skew]/HarmonicNumber[cardinality, 1 + skew]
            return harmonic(cardinality, skew)/denomCache;
        }
    }

    @Override
    public double mode()
    {
        return 1;
    }

    @Override
    public double variance()
    {
        if(Double.isInfinite(cardinality))
        {
            if(skew <= 2)
                return Double.POSITIVE_INFINITY;
            //-(Zeta[skew]^2/Zeta[1+skew]^2)+Zeta[-1+skew]/Zeta[1+skew]
            double zSkewP1 = denomCache;
            double zSkewM1 = zeta(skew-1);
            return zSkewM1/zSkewP1 - pow(zeta(skew), 2)/(zSkewP1*zSkewP1);
        }
        else
        {
            //(-HarmonicNumber[cardinality,skew]^2+HarmonicNumber[cardinality,-1+skew] HarmonicNumber[cardinality,1+skew])/HarmonicNumber[cardinality,1+skew]^2
            double hSkewP1 = harmonic(cardinality, 1+skew);
            return (-pow(harmonic(cardinality, skew), 2)+harmonic(cardinality, skew-1) * hSkewP1)/(hSkewP1*hSkewP1);
        }
    }

    @Override
    public double skewness()
    {
        if(Double.isInfinite(cardinality))
        {
            if(skew <= 3)
                return Double.POSITIVE_INFINITY;
            //(2 Zeta[skew]^3-3 Zeta[-1+skew] Zeta[skew] Zeta[1+skew]+Zeta[-2+skew] Zeta[1+skew]^2)/(-Zeta[skew]^2+Zeta[-1+skew] Zeta[1+skew])^(3/2)
            double zSkew = zeta(skew);
            double zSkewP1 = denomCache;
            double zSkewM1 = zeta(skew - 1);
            return (2 * pow(zSkew, 3) - 3 * zSkewM1 * zSkew * zSkewP1 + zeta(-2 + skew) * pow(zSkewP1, 2)) / pow(-pow(zSkew, 2) + zSkewM1 * zSkewP1, 3.0 / 2.0);
        }
        else
        {
            //(2 HarmonicNumber[cardinality,skew]^3-3 HarmonicNumber[cardinality,-1+skew] HarmonicNumber[cardinality,skew] HarmonicNumber[cardinality,1+skew]+HarmonicNumber[cardinality,-2+skew] HarmonicNumber[cardinality,1+skew]^2)/(HarmonicNumber[cardinality,1+skew]^3 ((-HarmonicNumber[cardinality,skew]^2+HarmonicNumber[cardinality,-1+skew] HarmonicNumber[cardinality,1+skew])/HarmonicNumber[cardinality,1+skew]^2)^(3/2))
            double hSkewM1 = harmonic(cardinality, skew-1);
            double hSkew = harmonic(cardinality, skew);
            double hSkewP1 = denomCache;
            //numerator is (2 HarmonicNumber[cardinality,skew]^3-3 HarmonicNumber[cardinality,-1+skew] HarmonicNumber[cardinality,skew] HarmonicNumber[cardinality,1+skew]+HarmonicNumber[cardinality,-2+skew] HarmonicNumber[cardinality,1+skew]^2)
            
            double numer = (2*pow(hSkew, 3)-3*hSkewM1*hSkew*hSkewP1+harmonic(cardinality, skew-2)*pow(hSkewP1, 2));
            
            //denominator is (HarmonicNumber[cardinality,1+skew]^3 ((-HarmonicNumber[cardinality,skew]^2+HarmonicNumber[cardinality,-1+skew] HarmonicNumber[cardinality,1+skew])/HarmonicNumber[cardinality,1+skew]^2)^(3/2))
            double denom = pow(hSkewP1, 3) * pow( (-pow(hSkew, 2) + hSkewM1 * hSkewP1)/pow(hSkewP1, 2)  , 3.0/2.0 );
            return numer/denom;
        }
    }

    @Override
    public double min()
    {
        return 1;
    }

    @Override
    public double max()
    {
        return cardinality;
    }
    
}

 

Ads help maintain this website.