de.lmu.ifi.dbs.elki.math.statistics.distribution

## Class HaltonUniformDistribution

• java.lang.Object
• de.lmu.ifi.dbs.elki.math.statistics.distribution.HaltonUniformDistribution
• All Implemented Interfaces:
Distribution

@Reference(title="Randomized halton sequences",
authors="X. Wang, F. J. Hickernell",
booktitle="Mathematical and Computer Modelling Vol. 32 (7)",
url="https://doi.org/10.1016/S0895-7177(00)00178-3",
bibkey="doi:10.1016/S0895-71770000178-3")
public class HaltonUniformDistribution
extends java.lang.Object
implements Distribution
Halton sequences are a pseudo-uniform distribution. The data is actually too regular for a true uniform distribution, but as such will of course often appear to be uniform.

Technically, they are based on Van der Corput sequence and the Von Neumann Katutani transformation. These produce a series of integers which then are converted to floating point values.

To randomize, we just choose a random starting position, as indicated by

Reference:

X. Wang, F. J. Hickernell
Randomized halton sequences
Mathematical and Computer Modelling Vol. 32 (7)

Important note: this code hasn't been double checked yet. While it probably works for some simple cases such as example data set generation, do not rely on it for e.g. quasi monte carlo methods without double-checking the quality, and looking at more advanced methods!

Let me repeat this: this code was written to generate toy datasets. It may have deficits for other uses! There is a high chance it will produce correlated data when used for more than one dimension. - for toy data sets, try different random seeds until you find one that works for you.

TODO: find an improved algorithm that takes care of a better randomization, for example by adding scrambling.

Since:
0.5.5
Author:
Erich Schubert
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
static class  HaltonUniformDistribution.Parameterizer
Parameterization class TODO: allow manual parameterization of sequence parameters!
• ### Field Summary

Fields
Modifier and Type Field and Description
private static double ALMOST_ONE
Threshold
(package private) short base
Base value
(package private) int counter
Counter, for max iterations of fast function.
(package private) double current
Current value
(package private) double invbase
Inverse of base, for faster division by multiplication.
(package private) long inverse
Integer inverse
private double len
Len := max - min
(package private) double logbase
Logarithm of base.
private double max
Maximum
private static int MAXFAST
Maximum number of iterations of fast variant
(package private) int maxi
Maximum integer to use
private double min
Minimum
• ### Constructor Summary

Constructors
Constructor and Description
HaltonUniformDistribution(double min, double max)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
HaltonUniformDistribution(double min, double max, int base, double seed)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
HaltonUniformDistribution(double min, double max, java.util.Random rnd)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
HaltonUniformDistribution(double min, double max, RandomFactory rnd)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
• ### Method Summary

All Methods
Modifier and Type Method and Description
double cdf(double val)
Return the cumulative density function at the given value.
private static int choosePrime(java.util.Random rnd)
Choose a random prime.
double getMax()
double getMin()
private long inverse(double current)
Compute the inverse with respect to the given base.
double logpdf(double val)
Return the log density of an existing value
private double nextRadicalInverse()
double nextRandom()
Generate a new random value
double pdf(double val)
Return the density of an existing value
double quantile(double val)
Quantile aka probit (for normal) aka inverse CDF (invcdf, cdf^-1) function.
private double radicalInverse(long i)
Compute the radical inverse of i.
java.lang.String toString()
Describe the distribution
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
• ### Field Detail

• #### min

private double min
Minimum
• #### max

private double max
Maximum
• #### len

private double len
Len := max - min
• #### MAXFAST

private static final int MAXFAST
Maximum number of iterations of fast variant
Constant Field Values
• #### ALMOST_ONE

private static final double ALMOST_ONE
Threshold
Constant Field Values
• #### base

final short base
Base value
• #### invbase

final double invbase
Inverse of base, for faster division by multiplication.
• #### logbase

final double logbase
Logarithm of base.
• #### maxi

final int maxi
Maximum integer to use
• #### counter

int counter
Counter, for max iterations of fast function.
• #### current

double current
Current value
• #### inverse

long inverse
Integer inverse
• ### Constructor Detail

• #### HaltonUniformDistribution

public HaltonUniformDistribution(double min,
double max,
int base,
double seed)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
Parameters:
min - Minimum value
max - Maximum value
base - Base value
seed - Random seed (starting value)
• #### HaltonUniformDistribution

public HaltonUniformDistribution(double min,
double max)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
Parameters:
min - Minimum value
max - Maximum value
• #### HaltonUniformDistribution

public HaltonUniformDistribution(double min,
double max,
java.util.Random rnd)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
Parameters:
min - Minimum value
max - Maximum value
rnd - Random generator
• #### HaltonUniformDistribution

public HaltonUniformDistribution(double min,
double max,
RandomFactory rnd)
Constructor for a halton pseudo uniform distribution on the interval [min, max[
Parameters:
min - Minimum value
max - Maximum value
rnd - Random generator
• ### Method Detail

• #### choosePrime

private static int choosePrime(java.util.Random rnd)
Choose a random prime. We try to avoid the later primes, as they are known to cause too correlated data.
Parameters:
rnd - Random generator
Returns:
Prime
• #### pdf

public double pdf(double val)
Description copied from interface: Distribution
Return the density of an existing value
Specified by:
pdf in interface Distribution
Parameters:
val - existing value
Returns:
distribution density
• #### logpdf

public double logpdf(double val)
Description copied from interface: Distribution
Return the log density of an existing value
Specified by:
logpdf in interface Distribution
Parameters:
val - existing value
Returns:
log distribution density
• #### cdf

public double cdf(double val)
Description copied from interface: Distribution
Return the cumulative density function at the given value.
Specified by:
cdf in interface Distribution
Parameters:
val - existing value
Returns:
cumulative density
• #### quantile

public double quantile(double val)
Description copied from interface: Distribution
Quantile aka probit (for normal) aka inverse CDF (invcdf, cdf^-1) function.
Specified by:
quantile in interface Distribution
Parameters:
val - Quantile to find
Returns:
Quantile position
• #### inverse

private long inverse(double current)
Compute the inverse with respect to the given base.
Parameters:
current - Current value
Returns:
Integer inverse

private double radicalInverse(long i)
Compute the radical inverse of i.
Parameters:
i - Input long value
Returns:

private double nextRadicalInverse()
Returns:
Next inverse
• #### nextRandom

public double nextRandom()
Description copied from interface: Distribution
Generate a new random value
Specified by:
nextRandom in interface Distribution
Returns:
new random value
• #### toString

public java.lang.String toString()
Description copied from interface: Distribution
Describe the distribution
Specified by:
toString in interface Distribution
Overrides:
toString in class java.lang.Object
Returns:
description
• #### getMin

public double getMin()
Returns:
the minimum value
• #### getMax

public double getMax()
Returns:
the maximum value