Empirical distribution function
The empirical distribution function (EDF), also known as the empirical cumulative distribution function (ECDF), is a nonparametric estimator of the cumulative distribution function (CDF) of an unknown probability distribution, constructed directly from a finite sample of independent and identically distributed observations.[1] For a sample X_1, X_2, \dots, X_n drawn from the distribution, the EDF is defined as the step function F_n(x) = \frac{1}{n} \sum_{i=1}^n \mathbf{1}_{\{X_i \leq x\}}, where \mathbf{1}_{\{X_i \leq x\}} is the indicator function that equals 1 if X_i \leq x and 0 otherwise; this represents the proportion of sample points less than or equal to x, making F_n(x) a non-decreasing, right-continuous function with jumps of size $1/n at each observed data point.[2][3] A fundamental property of the EDF is its uniform convergence to the true underlying CDF F(x) as the sample size n increases, as established by the Glivenko-Cantelli theorem, which states that \sup_x |F_n(x) - F(x)| \to 0 almost surely.[3] This convergence underpins the reliability of the EDF for large samples and extends to more general empirical processes in advanced statistical theory.[4] The EDF serves as a cornerstone for nonparametric statistical methods, including goodness-of-fit tests such as the Kolmogorov-Smirnov test, which compares F_n(x) to a hypothesized CDF to assess distributional assumptions, and in empirical process theory for deriving asymptotic results in high-dimensional data analysis.[2][5] In practice, the EDF is widely implemented in statistical software for visualizing data distributions and performing inference without parametric assumptions, offering a simple yet powerful tool for exploratory data analysis and robust estimation in fields like reliability engineering, survival analysis, and machine learning.[1] Its simplicity allows for straightforward computation, while its theoretical guarantees ensure consistent performance across diverse applications.[6]Introduction and Definition
Definition
The empirical distribution function (EDF), also known as the empirical cumulative distribution function (ECDF), is a nonparametric estimator of the cumulative distribution function (CDF) of an underlying probability distribution based on a finite sample of observations.[7][2] Given an independent and identically distributed (i.i.d.) sample X_1, \dots, X_n drawn from a distribution with unknown CDF F, the EDF is formally defined as F_n(x) = \frac{1}{n} \sum_{i=1}^n \mathbf{1}_{\{X_i \leq x\}}, where \mathbf{1}_{\{ \cdot \}} denotes the indicator function that equals 1 if the event holds and 0 otherwise.[7][2] This formulation assigns equal probability mass $1/n to each observation, treating the sample as a discrete uniform distribution over the data points. The EDF is a right-continuous step function that remains constant between the observed data points and exhibits jumps at each distinct observation. When the sample values are ordered as X_{(1)} \leq X_{(2)} \leq \dots \leq X_{(n)} (the order statistics), the function jumps by a height of $1/n at each X_{(i)} in the absence of ties.[7][2] In cases of ties, where multiple observations share the same value (common in discrete data), the jump size at that value x_k is adjusted to n_k / n, with n_k representing the multiplicity or frequency of ties at x_k; this ensures the total probability sums to 1 while accommodating the discrete nature of the sample.[2] For continuous distributions, ties are negligible with probability approaching 1 as n increases, but the definition remains applicable without modification.[7] The notation F_n(x) is conventional for the EDF, distinguishing it from the true CDF F(x); alternative symbols such as \hat{F}(x) or F_n^*(x) appear occasionally in literature but convey the same concept.[7][2]Motivation and Basic Interpretation
The empirical distribution function (EDF) serves as a fundamental non-parametric estimator of the unknown cumulative distribution function F of a population, derived directly from a random sample without imposing any assumed parametric form on the underlying distribution. This approach enables flexible, model-free analysis of data distributions, making it essential for exploratory statistics and inference where the true form of F is unspecified or complex.[8] The origins of the EDF trace back to early 20th-century work on probability laws, with Glivenko introducing the concept in 1933 for continuous distributions and Cantelli extending it in 1933 to the general case, thereby establishing it as a cornerstone for distribution-free methods.[9] These contributions motivated its use in uniform convergence results, highlighting the EDF's reliability as an empirical approximation even for large samples. Intuitively, the EDF at any point x computes the proportion of sample values less than or equal to x, providing a direct empirical estimate of the population probability P(X \leq x). This simple proportion-based interpretation allows the EDF to summarize the ordering and spread of data points effectively. Plotted as a step function—often visualized as a staircase graph—the EDF offers an immediate graphical depiction of how the data accumulates, revealing quantiles and tail behavior without further computation.[10][11] Unlike histograms, which estimate the probability density through binning and can distort shapes due to arbitrary bin choices, or kernel density estimates that smooth data via bandwidth parameters, the EDF concentrates on the cumulative perspective, delivering a non-smoothed, exact representation of the sample's ordering. This cumulative focus sidesteps density-related artifacts, making the EDF preferable for tasks like distribution comparison or quantile estimation where preservation of empirical ranks is key.[12][13]Mathematical Properties
Asymptotic Behavior
The asymptotic behavior of the empirical distribution function (EDF) F_n(x) is analyzed under the assumption that the observations X_1, \dots, X_n are independent and identically distributed (i.i.d.) from a continuous distribution function F. This i.i.d. sampling condition ensures that the EDF serves as a nonparametric estimator of F, with properties that strengthen as the sample size n increases, providing foundational results for uniform and functional convergence in empirical process theory.[14] Pointwise, at any fixed x \in \mathbb{R}, the EDF satisfies a central limit theorem: the normalized deviation \sqrt{n}(F_n(x) - F(x)) converges in distribution to a normal random variable with mean 0 and variance F(x)(1 - F(x)).This result arises directly from applying the Lindeberg–Lévy central limit theorem to the sum \sum_{i=1}^n I(X_i \leq x), where I is the indicator function, as F_n(x) is the sample mean of these Bernoulli random variables with success probability F(x).
The variance F(x)(1 - F(x)) reflects the binomial nature of the count of observations not exceeding x.
This pointwise asymptotic normality quantifies the local fluctuation of the EDF around the true F and forms the basis for approximate confidence intervals at specific points.[14] For global behavior, the Glivenko-Cantelli theorem establishes uniform almost sure convergence: \sup_{x \in \mathbb{R}} |F_n(x) - F(x)| \to 0 \quad \text{almost surely as } n \to \infty. Proved by Glivenko for continuous F and extended by Cantelli to the general case, this theorem guarantees that the EDF converges to F uniformly over the entire real line with probability 1, implying consistency of the EDF as an estimator.
It strengthens the pointwise weak law of large numbers to a uniform strong law, essential for sup-norm approximations in nonparametric statistics. A further refinement is given by Donsker's theorem, which describes the weak convergence of the centered and scaled EDF process to a Gaussian process.
Specifically, the process \sqrt{n}(F_n(\cdot) - F(\cdot)), viewed as a random element in the Skorohod space \mathbb{D}[0,1] after suitable linear interpolation to map to [0,1], converges in distribution to a Brownian bridge B^0(t) = B(t) - t B(1), where B is a standard Brownian motion.
This functional central limit theorem, established for the uniform distribution and extended generally under the i.i.d. assumption, captures the joint asymptotic distribution across all x, enabling approximations for functionals of the EDF beyond pointwise or uniform limits alone.
Consistency and Convergence Theorems
The Glivenko–Cantelli theorem provides the foundational result for strong uniform consistency of the empirical distribution function (EDF). For i.i.d. random variables X_1, \dots, X_n with common cumulative distribution function (CDF) F, the supremum deviation \sup_{x \in \mathbb{R}} |F_n(x) - F(x)| converges almost surely to 0 as n \to \infty.[15] This strong consistency holds regardless of the continuity of F, establishing that the EDF F_n approximates the true CDF F uniformly over the entire real line with probability 1.[16] A standard proof sketch exploits the monotonicity of both F_n and F. For any \epsilon > 0, define events A_{n,k} = \{ |F_n(X_{(k)}) - F(X_{(k)})| > \epsilon \} for order statistics X_{(k)}, and bound P(A_{n,k}) using concentration inequalities like Hoeffding's. Summing over k yields P(\sup_x |F_n(x) - F(x)| > \epsilon) \leq C n^{-1} for some constant C, so \sum_n P(\sup_x |F_n(x) - F(x)| > \epsilon) < \infty. The Borel–Cantelli lemma then implies that such deviations occur only finitely often almost surely, ensuring uniform convergence.[17] The strong consistency immediately implies weak consistency in probability: \sup_{x \in \mathbb{R}} |F_n(x) - F(x)| \xrightarrow{P} 0 as n \to \infty.[15] This mode of convergence is less stringent but sufficient for many asymptotic arguments where almost sure uniformity is not required. Under the additional assumption that F is continuous, sharper rates of convergence are available. In particular, the expected supremum deviation satisfies E\left[ \sup_{x \in \mathbb{R}} |F_n(x) - F(x)| \right] = O\left( \sqrt{\frac{\log \log n}{n}} \right), reflecting the influence of the law of the iterated logarithm on the boundary fluctuations of the EDF.[18] Extensions of the Glivenko–Cantelli theorem to non-i.i.d. settings, such as stationary sequences under \alpha-mixing or \beta-mixing conditions, preserve strong uniform consistency provided the mixing coefficients decay at a sufficiently rapid rate (e.g., \sum_n \alpha(n)^{1/2} < \infty).[19] These results apply to dependent data like those from time series, but limitations arise for slower mixing or other dependence structures, where convergence may fail or require adjusted rates and classes of functions.[20]Statistical Inference
Confidence Bands
Confidence bands for the empirical distribution function (EDF) provide a way to quantify the uncertainty in the estimation of the true cumulative distribution function (CDF) F using the EDF F_n. These bands are constructed to contain the true CDF with a specified probability, such as 95%, over the entire support or at specific points. One prominent method is the Kolmogorov-Smirnov (KS) confidence bands, which are based on the distribution of the supremum deviation \sqrt{n} \sup_x |F_n(x) - F(x)|. The KS bands are simultaneous confidence bands that cover the entire CDF uniformly. Critical values for these bands are derived from the Kolmogorov distribution, with tables providing exact values for finite sample sizes n. For example, Massey (1951) tabulated critical values d_{\alpha}(n) such that the probability that \sup_x |F_n(x) - F(x)| \leq d_{\alpha}(n)/\sqrt{n} is at least $1 - \alpha. For large n, the 95% critical value approximates 1.36, yielding bands F_n(x) \pm 1.36 / \sqrt{n}.[21] Non-parametric confidence bands can also be constructed using the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which provides a distribution-free bound on the uniform deviation. The DKW inequality states that for any \epsilon > 0, P\left( \sup_x |F_n(x) - F(x)| > \epsilon \right) \leq 2 \exp(-2n \epsilon^2).[22] This bound allows construction of bands F_n(x) \pm \epsilon_n, where \epsilon_n is chosen to achieve the desired coverage probability, such as solving for \epsilon_n \approx \sqrt{ \frac{ \ln(2/\alpha) }{ 2n } } for approximate $1 - \alpha coverage. The DKW approach is particularly useful for finite-sample guarantees without relying on asymptotic approximations.[22] For pointwise confidence intervals at a fixed x, the EDF F_n(x) follows a binomial distribution with parameters n and p = F(x), leading to an asymptotic normal approximation. The variance of F_n(x) is F(x)(1 - F(x))/n, which can be estimated by \hat{F}_n(x) (1 - \hat{F}_n(x))/n. Thus, a 95% pointwise interval is approximately F_n(x) \pm 1.96 \sqrt{ F_n(x) (1 - F_n(x))/n }. These intervals are narrower than uniform bands but do not control coverage over the entire function. In the presence of right-censored data, adjustments to the EDF are necessary, and confidence bands for the Kaplan-Meier estimator replace the standard EDF. The Kaplan-Meier estimator adapts the product-limit formula to account for censoring, and bands can be constructed using methods like those proposed by Hall and Wellner (1980), which provide simultaneous coverage based on transformed Brownian bridge approximations. These bands ensure uniform confidence levels while handling the irregular steps induced by censoring.Hypothesis Testing Applications
The empirical distribution function (EDF) serves as a foundational tool in nonparametric hypothesis testing for distribution inference, particularly in goodness-of-fit tests against a specified continuous distribution F_0 and in comparing distributions from two independent samples. These applications leverage the EDF's uniform approximation properties to construct test statistics that measure deviations between empirical and hypothesized cumulatives, enabling rejection of the null hypothesis when discrepancies are deemed unlikely under the assumed model. Such tests are distribution-free under the null, making them versatile for various underlying distributions without parametric assumptions. A key example is the one-sample Kolmogorov-Smirnov (KS) test, which assesses whether an i.i.d. sample of size n arises from F_0. The test statistic is the maximum vertical distance between the EDF F_n and F_0, D_n = \sup_x |F_n(x) - F_0(x)|, originally proposed by Kolmogorov. Under the null hypothesis, \sqrt{n} D_n converges in distribution to the Kolmogorov distribution, whose cumulative distribution function is given asymptotically by P(\sqrt{n} D_n \leq t) \approx 1 - 2 \sum_{k=1}^\infty (-1)^{k-1} e^{-2k^2 t^2} for large n, facilitating p-value computation via critical values or simulation. This supremum-based measure is sensitive to any location of deviation but treats all regions equally. The two-sample KS test extends this framework to compare whether two independent samples of sizes n and m originate from the same continuous distribution, as developed by Smirnov. The statistic is D_{n,m} = \sup_x |F_n(x) - F_m(x)|, where F_n and F_m are the respective EDFs. Under the null, the test often references the pooled EDF F_{n,m}(x) = \frac{n F_n(x) + m F_m(x)}{n+m} to approximate the common distribution, with \sqrt{\frac{nm}{n+m}} D_{n,m} asymptotically following a scaled version of the Kolmogorov distribution, similar to the one-sample case but adjusted for effective sample size. This test detects differences in location, scale, or shape without specifying the form. Beyond supremum statistics, integral-based tests like the Cramér-von Mises (CvM) and Anderson-Darling (AD) provide alternatives that aggregate squared deviations, offering potentially higher power against certain alternatives by considering the entire curve. The CvM statistic for the one-sample case is \omega_n^2 = \int_{-\infty}^{\infty} (F_n(x) - F_0(x))^2 \, dF_0(x), introduced by Cramér and von Mises, which weights deviations uniformly and has an asymptotic distribution under the null involving a weighted sum of chi-squared variables. The AD test modifies this with tail emphasis via A_n^2 = \int_{-\infty}^{\infty} \frac{(F_n(x) - F_0(x))^2}{F_0(x) (1 - F_0(x))} \, dF_0(x), yielding greater sensitivity to discrepancies in the distribution tails; its asymptotic null distribution is also known and tabulated. Both tests extend naturally to two-sample settings by replacing F_0 with the pooled EDF. These EDF-based tests exhibit limitations in power and applicability. The KS test's power is moderate against alternatives with localized deviations, such as shifts in the center or tails, and generally lower than integral tests like AD for smooth alternatives. For small sample sizes, all such tests suffer from reduced power to detect departures from the null, compounded by challenges in exact p-value computation, often requiring Monte Carlo approximations or conservative tables that inflate type II errors.Computation and Examples
Algorithmic Implementation
The empirical distribution function (EDF) is computed using a sorting-based algorithm that leverages order statistics to construct a step function estimate of the underlying cumulative distribution function. Given an independent and identically distributed sample X_1, X_2, \dots, X_n from an unknown distribution, sort the observations in non-decreasing order to obtain the order statistics X_{(1)} \leq X_{(2)} \leq \dots \leq X_{(n)}. The EDF is then given by F_n(x) = \frac{1}{n} \sum_{i=1}^n I(X_i \leq x), which evaluates to F_n(x) = 0 for x < X_{(1)}, F_n(x) = \frac{k}{n} for X_{(k)} \leq x < X_{(k+1)} and k = 1, \dots, n-1 (with adjustments for ties by assigning larger jumps at repeated values), and F_n(x) = 1 for x \geq X_{(n)}.[2][23] This approach handles ties naturally by grouping identical observations and incrementing the function by the proportion of tied values at each unique point, ensuring the total probability sums to 1. The resulting step function is right-continuous by convention, with jumps occurring at the order statistics and the value at each jump point including the mass from observations equal to that point; a left-continuous variant can be obtained by using strict inequality I(X_i < x), shifting the mass to the left of each jump. For visualization, linear interpolation between consecutive points (X_{(k)}, k/n) and (X_{(k+1)}, (k+1)/n) is commonly applied to produce a connected plot, facilitating smoother representation without altering the underlying discrete nature.[23][24] The computational efficiency of this sorting-based method stems from standard sorting algorithms like quicksort, yielding a time complexity of O(n \log n) and space complexity of O(n) to store the sorted array, making it suitable for moderate to large datasets. For very large n, where exact step function storage becomes memory-intensive, histogram-based approximations bin the data into intervals and compute the cumulative sum of bin frequencies to estimate F_n(x), trading precision for reduced storage and faster queries at the cost of smoothing over fine details.[25][26] Variants extend this framework to related functions. The empirical quantile function, the inverse of the EDF, is obtained by sorting the data and using piecewise linear interpolation: for a probability p \in (0,1), locate the smallest k such that k/n \geq p, then interpolate between X_{(k)} and X_{(k-1)} if needed. In the multivariate setting, the empirical copula transforms marginal ranks to uniforms via the univariate EDFs and computes the joint EDF on the unit hypercube, often using dimension-wise sorting followed by cumulative counting; efficient streaming algorithms achieve O(1/\epsilon^2 \log(\epsilon n)^2) space for \epsilon-approximations in the bivariate case.[27][28]Illustrative Examples
To illustrate the computation of the empirical distribution function (EDF), consider a simple univariate example with a small sample drawn from a uniform distribution on [0,1]. Suppose the sample consists of n=5 observations: 0.13, 0.27, 0.45, 0.62, 0.89. Ordering these values gives the order statistics: 0.13, 0.27, 0.45, 0.62, 0.89. The EDF, denoted F_n(x), is a step function that starts at 0 for x < 0.13 and jumps by $1/5 = 0.2 at each order statistic: F_n(x) = 0.2 for $0.13 \leq x < 0.27, F_n(x) = 0.4 for $0.27 \leq x < 0.45, F_n(x) = 0.6 for $0.45 \leq x < 0.62, F_n(x) = 0.8 for $0.62 \leq x < 0.89, and F_n(x) = 1 for x \geq 0.89.[29] When plotted, the EDF appears as a staircase with horizontal segments and vertical jumps at the data points, approximating the true cumulative distribution function (CDF) F(x) = x for $0 \leq x \leq 1. The steps closely follow the diagonal line of the true CDF in this case, though deviations occur due to the small sample size, with the largest difference (Kolmogorov distance) of 0.18 near x=0.62. For a real-data application, the Iris dataset provides measurements of sepal lengths from 150 flowers across three species: setosa, versicolor, and virginica. Focusing on the 150 sepal length values (ranging from 4.3 to 7.9 cm, with mean 5.84 cm), the EDF is computed by ordering the data and assigning cumulative proportions. The resulting plot shows a smooth staircase rising from 0 to 1, with notable jumps clustered around 5.0–5.5 cm (common for setosa) and 6.0–7.0 cm (for versicolor and virginica). To assess fit to a normal distribution, a Kolmogorov-Smirnov (KS) test compares the EDF to the normal CDF with estimated parameters (mean 5.84, sd 0.83), yielding a test statistic of approximately 0.07 and p-value 0.1706, failing to reject normality at the 5% level.[30] This indicates the sepal lengths are reasonably consistent with a normal distribution, though the plot reveals slight right-skewness in the upper tail. In a two-sample comparison, overlaying EDFs for setosa (n=50, sepal lengths mean 5.01 cm) and versicolor (n=50, mean 5.94 cm) highlights distributional differences. The setosa EDF rises sharply early (around 4.5–5.5 cm, reaching 0.8 by 5.2 cm), while the versicolor EDF shifts rightward, with slower initial rise and jumps concentrated around 5.5–7.0 cm. A two-sample KS test on these EDFs yields a statistic of about 0.56 and p-value near 0, rejecting the null hypothesis of identical distributions and underscoring the species-specific differences in sepal length variability. For effective visualization, EDFs are best plotted as stairs (step functions) using software like R'splot.ecdf() or MATLAB's ecdf() function, which draw horizontal lines connected by vertical jumps to emphasize the non-parametric nature without smoothing.[31] Jumps indicate the location and multiplicity of data points, while flat regions reflect gaps in the sample, aiding interpretation of density and outliers; for instance, large jumps suggest clustering, and prolonged flats reveal sparse coverage.[32]