-
Notifications
You must be signed in to change notification settings - Fork 2
/
setup.py
89 lines (76 loc) · 3.9 KB
/
setup.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
from distutils.core import setup, Extension
import os
module1 = Extension(
'_crossprob',
sources = [
'src/common.cc',
'src/string_utils.cc',
'src/poisson_pmf.cc',
'src/fftwconvolver.cc',
'src/ecdf1_mns2016.cc',
'src/ecdf1_new.cc',
'src/ecdf2.cc',
'python_extension/crossprob.cc'
],
extra_compile_args = ['-Wall', '-std=c++11', '-ffast-math', '-march=native'],
# Path to FFTW3:
# Note that if you're running in Anaconda Python, it includes Intel's MKL implementation of FFT
# which is compatible with the FFTW3 API. In that case you don't actually need to link anything and the code will probably run slightly faster on Intel CPUs.
extra_link_args = ['-L/usr/local/lib/', '-lfftw3'],
#undef_macros = ["NDEBUG"]
)
LONG_DESCRIPTION = """crossprob - crossing probabilities for one-dimensional empirical processes
Let X_1,...,X_n be a set of points sampled uniformly from the interval [0,1]
and let X_(1) <= X_(2) <= ... <= X_(n) be the sorted sample.
This module implements several algorithms for computing the probability
Pr[for all i: b_i <= X_(i) <= B_i] (1)
Equivalently, let the empirical cumulative distribution function of X_1,...,X_n be
F_n(t) := \sum_i 1(X_i <= t).
The probability in Eq. (1) is equivalent to the probability that F_n(t) does not cross
a two-sided boundary,
The most versatile function is the two-sided crossing probability
ecdf2(b, B, use_fft)
Its parameters are:
n: the size of the sample
b, B: two lists of length n of the boundaries in Eq. (1) above.
use_fft: If true algorithm the O(n^2 logn) algorithm [MNS2016] is used,
otherwise the O(n^3) algorithm of [KS2001]
Faster functions are available for the special case of a single boundary:
ecdf1_new_b(b)
Implements a new O(n^2) algorithm [NEW]. B_i are implicitly assumed to be 1.
ecdf1_new_B(B)
Implements the O(n^2) algorithm [NEW]. b_i are implicitly assumed to be 0.
ecdf1_mns2016_b(b)
Implements the O(n^2) algorithm of [MNS2016]. B_i are implicitly assumed to be 1.
Generally slower and less numerically stable than ecdf1_new_b()
ecdf1_mns2016_B(B)
Implements the O(n^2) algorithm of [MNS2016]. b_i are implicitly assumed to be 0.
Generally slower and less numerically stable than ecdf1_new_B()
EXAMPLES
For a sample X_1, X_2, X_3 with order statistics X_(1) <= X_(2) <= X(3), the probability
Pr[X_(1)<=0.7 and 0.15<=X_(2)<=0.9 and 0.5<=X_(3)<=0.8]
may be computed using
ecdf2([0, 0.15, 0.5], [0.7, 0.9, 0.8], True)
REFERENCES
[KS2001] Estate Khmaladze, Eka Shinjikashvili (2001). Calculation of noncrossing probabilities for Poisson
processes and its corollaries, Advances in Applied Probability. https://doi.org/10.1239/aap/1005091361
[MNS2016] Amit Moscovich, Boaz Nadler, Clifford Spiegelman (2016). On the exact Berk-Jones statistics and their
p-value calculation. Electronic Journal of Statistics. https://doi.org/10.1214/16-EJS1172
[MN2017] Amit Moscovich, Boaz Nadler (2017). Fast calculation of boundary crossing probabilities for Poisson processes.
Statistics & Probability Letters. https://doi.org/10.1016/j.spl.2016.11.027
[NEW] Amit Moscovich (2020). Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics.
Preprint. https://arxiv.org/abs/2009.04954
MODULE REFERENCE
https://github.com/mosco/crossing-probability
"""
setup(name = 'crossprob',
version = '1.2',
description = 'Fast computation of boundary crossing probabilities empirical processes',
author = 'Amit Moscovich',
author_email = 'amit@moscovich.org',
url = 'https://github.com/mosco/crossing-probability',
license = 'MIT',
ext_modules = [module1],
py_modules = ['crossprob'],
package_dir={'': 'python_extension'},
long_description = LONG_DESCRIPTION)