2.2 Why Rank Statistics Are Distribution-Free
The definition above tells us what distribution-freeness is. It does not tell us how any statistic manages to have the property, and the examples given so far are of a restricted kind: \(U_1\) and \(U_2\) are distribution-free only over classes of normal distributions, so the unknown parameter cancels but the normality does not. What we want is a statistic that is distribution-free over the class of all continuous distributions. That such statistics exist at all rests on the following theorem, which is the foundation of the entire subject.
Theorem 2.2.1 (Probability integral transform). Let \(X\) be a random variable with continuous distribution function \(F\). Then \[U = F(X)\ \sim \ \operatorname {Uniform}(0,1).\]
Proof. Fix \(u\in (0,1)\). Since \(F\) is continuous and non-decreasing, the set \(\{x: F(x)\leq u\}\) is an interval unbounded below; write \(x_u = \sup \{x : F(x)\leq u\}\), so that \(F(x_u) = u\) by continuity. Then \[P(U\leq u) = P\left (F(X)\leq u\right ) = P(X\leq x_u) = F(x_u) = u ,\] and a random variable whose distribution function is \(u\) on \((0,1)\) is uniform on \((0,1)\). □
Read the conclusion slowly, because the whole subject turns on it. Whatever continuous distribution generated the data — normal, exponential, heavy-tailed, bimodal — feeding the observations through their own distribution function produces uniform variables. The particular shape of \(F\) has been transformed away. If a statistic can be arranged to depend on the data only through quantities that survive this transformation unchanged, its null distribution cannot depend on \(F\) either.
Ranks are exactly such quantities.
Corollary 2.2.2 (Ranks are distribution-free over all continuous distributions). Let \(X_1,\dots ,X_n\) be \(iid\) with continuous distribution function \(F\), and let \(R_i\) denote the rank of \(X_i\) in the sample. Then for every permutation \((r_1,\dots ,r_n)\) of \((1,\dots ,n)\), \[P\left (R_1 = r_1,\ \dots ,\ R_n = r_n\right ) = \frac {1}{n!} ,\] whatever \(F\) may be.
Proof. Continuity gives \(P(X_i = X_j)=0\) for \(i\neq j\), so with probability one no ties occur and the ranks are well defined. Put \(U_i = F(X_i)\). By Theorem 2.2.1 the \(U_i\) are \(iid\) uniform on \((0,1)\), and because \(F\) is non-decreasing it preserves order: \(X_i<X_j\) if and only if \(U_i<U_j\). Hence the rank vector of the \(X\)’s equals the rank vector of the \(U\)’s. The joint density of \(U_1,\dots ,U_n\) is \(1\) on the unit cube, which is symmetric under permutation of its arguments, so all \(n!\) orderings have equal probability \(1/n!\). □
Note 2.2.3. Corollary 2.2.2 is the licence for every published table of critical values for a rank test. The null distribution of the Wilcoxon, Mann–Whitney, Kruskal–Wallis and Friedman statistics can be computed once, from the uniform distribution over the \(n!\) permutations, and is then correct for every continuous population. No comparable table can exist for the \(t\)-statistic, whose null distribution requires normality.
Two hypotheses did the work in that proof, and it is worth being explicit about which, since they are precisely the assumptions a rank procedure makes. Continuity was used to exclude ties; real data are rounded, ties do occur, and the tie corrections that appear throughout the subject are patches on the gap between this theorem and the data rather than refinements of the theory. Identical distribution was used to make the joint density symmetric — and that is the null hypothesis itself. When it fails the \(n!\) orderings cease to be equally likely, which is what gives a rank test its power.
Exchangeability and the permutation principle
The symmetry exploited above can be isolated and stated on its own, and doing so extends the argument well beyond ranks.
Definition 2.2.4 (Exchangeability). Random variables \(X_1,\dots ,X_n\) are exchangeable if for every permutation \(\pi \) of \(\{1,\dots ,n\}\) \[\left (X_{\pi (1)},\dots ,X_{\pi (n)}\right )\ \overset {d}{=}\ \left (X_1,\dots ,X_n\right ),\] that is, if the joint distribution is invariant under relabelling.
Independent identically distributed variables are exchangeable; the converse fails. Exchangeability permits dependence, provided the dependence treats every observation alike — sampling without replacement from a finite population is the standard example. This is worth knowing because it, and not independence, is the assumption a permutation test actually needs.
Theorem 2.2.5 (Exactness of permutation tests). Suppose \(X_1,\dots ,X_n\) are exchangeable under \(H_0\). Let \(T\) be any statistic whatever, and let \(t_{(1)}\leq \cdots \leq t_{(n!)}\) be its values over all \(n!\) relabellings of the observed data. The test rejecting \(H_0\) when the observed value of \(T\) lies among the largest \(\alpha \cdot n!\) of these has size exactly \(\alpha \), for any \(\alpha \) that is a multiple of \(1/n!\).
Proof. Under exchangeability every one of the \(n!\) relabellings was equally likely to have produced the data in hand, so the observed value of \(T\) is equally likely to occupy each of the \(n!\) positions in the ordered list. The probability that it falls in the upper \(\alpha \cdot n!\) positions is therefore \(\alpha \cdot n!/n! = \alpha \). □
The strength of this result is easy to pass over. The test is exact — not approximate, not asymptotic, exact at every sample size — for any statistic \(T\), chosen on any grounds, under no distributional assumption beyond exchangeability. What is paid for that generality is computation: the null distribution must be constructed afresh for each data set instead of being read from a table.
Remark 2.2.6. Every rank test is a permutation test in disguise. Choosing \(T\) to be a function of the ranks alone makes the permutation distribution identical for every data set of the same size, and it is that invariance — not anything special about ranks as numbers — which allows the distribution to be tabulated in advance. Rank tests are the corner of Theorem 2.2.5 that can be computed once and reused.
The empirical distribution function
Rank statistics discard the numerical values and keep the ordering. A second family of distribution-free procedures keeps the values and estimates \(F\) itself.
Definition 2.2.7 (Empirical distribution function). For a sample \(X_1,\dots ,X_n\), \[F_n(x) = \frac {1}{n}\sum ^{n}_{i=1}\mathbb {I}\left \{X_i\leq x\right \},\] the proportion of observations not exceeding \(x\).
\(F_n\) is built entirely from the order statistics: it is the right-continuous step function that rises by \(1/n\) at each \(X_{(i)}\), as in Figure 1.1. For fixed \(x\), \(nF_n(x)\sim B\left (n,F(x)\right )\), so \[E\left (F_n(x)\right ) = F(x),\qquad \operatorname {var}\left (F_n(x)\right ) = \frac {F(x)\left (1-F(x)\right )}{n},\] and the strong law gives \(F_n(x)\to F(x)\) almost surely for each fixed \(x\). Pointwise convergence is not enough for a goodness-of-fit test, which needs the whole function at once; the following supplies it.
Theorem 2.2.8 (Glivenko–Cantelli). \[D_n \ =\ \sup _{x\in \mathbb {R}}\left |F_n(x) - F(x)\right | \ \xrightarrow {\ a.s.\ }\ 0 \qquad (n\to \infty ).\]
The result is sometimes called the fundamental theorem of statistics, and the name is deserved: the empirical distribution eventually reproduces the entire population distribution, uniformly, under no assumption on \(F\) whatever. Every distribution-free procedure that estimates rather than tests rests on it.
Glivenko–Cantelli says \(D_n\to 0\) but not how fast. The next result bounds the discrepancy at every finite \(n\), again with no assumption on \(F\).
Theorem 2.2.9 (Dvoretzky–Kiefer–Wolfowitz, with Massart’s constant). For every \(\varepsilon >0\) and every \(n\), \[P\left (D_n > \varepsilon \right )\ \leq \ 2e^{-2n\varepsilon ^{2}} .\]
Note 2.2.10. Theorem 2.2.9 is more than a rate. Setting the bound equal to \(\alpha \) and solving gives \[\varepsilon _n = \sqrt {\frac {1}{2n}\,\ln \frac {2}{\alpha }} ,\] and the band \(F_n(x)\pm \varepsilon _n\) then contains the whole of \(F\) simultaneously, with probability at least \(1-\alpha \), for every \(n\) and every continuous \(F\). At \(n=100\) and \(\alpha =0.05\) this is \(\pm 0.136\): wide, but assumption-free and valid over all \(x\) at once. The statistic \(D_n\) is also precisely the Kolmogorov–Smirnov statistic, whose null distribution is distribution-free by the same argument as Corollary 2.2.2.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.