5.3 Nonparametric Tests and Rank Correlation
Tests that need no normal model: the sign and Wilcoxon signed-rank tests, the Mann–Whitney and median tests, the runs test, the Kolmogorov–Smirnov tests and Spearman's and Kendall's rank correlations — with exact null distributions for small samples, normal approximations for large ones, and an honest account of what each test assumes and what it costs.
The $z$, $t$, $\chi^2$ and $F$ tests of §5.1 are exact only when the population is normal, and the large-sample tests of §5.2 are only approximately right for large $n$. Real data are often far from both situations: eight patients in a pilot study, survival times with a long right tail, a sensory panel that can only rank six wines, or a laboratory measurement with one wild outlier. A nonparametric (or distribution-free) test avoids the problem by replacing the observations with something whose null distribution does not depend on the unknown population at all: the signs of the observations, their ranks, the number of runs in a sequence, or the empirical distribution function. Because the null distribution is the same for every continuous population, it can be computed exactly by counting — and for small samples it is. The price is that some information is thrown away; the surprise, which we make precise with Pitman's asymptotic relative efficiency, is how little: against normal data the Wilcoxon tests are $3/\pi\approx95\%$ as efficient as the $t$ tests, and against heavy-tailed data they can be far more efficient.
This section builds the standard one- and two-sample rank tests from a single fact — for an iid sample from a continuous law, every ordering of the observations is equally likely — and proves the exact null distributions, means and variances that examiners ask for. We then treat the runs test, the Kolmogorov–Smirnov tests based on the empirical distribution function, and the rank correlation coefficients of Spearman and Kendall with their use as tests of independence. CSIR Part B questions typically ask for a null mean or variance (of $T^+$, $U$ or the number of runs), an exact small-sample $p$-value, or the value of $r_s$ or $\tau$ for given ranks. Part C questions test the hypotheses behind each test: symmetry for the signed-rank test, continuity and a completely specified $F_0$ for Kolmogorov–Smirnov, what a Mann–Whitney test can and cannot detect, and what a zero rank correlation does not imply.
Distribution-Free Inference and the Sign Test
Throughout, "continuous" means that the cdf is continuous, so that single points have probability $0$. Quantiles are upper-$\alpha$ points as in §4.3: $z_\alpha$ is exceeded with probability $\alpha$ by an $N(0,1)$ variable, and $\Phi$ is the standard normal cdf. In a nonparametric problem the unknown distribution ranges over a huge family, such as all continuous cdfs or all continuous cdfs symmetric about some point, and the null hypothesis is a sub-family of it.
Let the joint law of the observations $X_1,\dots,X_N$ belong to a family $\mathcal{P}$, and let $\mathcal{P}_0\subseteq\mathcal{P}$ be a null hypothesis.
- A statistic $T$ is distribution-free over $\mathcal{P}_0$ if its distribution is the same for every $P\in\mathcal{P}_0$. A test whose rejection region is $\{T\in C\}$ for such a $T$ then has the same size for every $P\in\mathcal{P}_0$; it is a distribution-free test.
- The rank of $X_i$ among $X_1,\dots,X_N$ is $R_i=\sum_{j=1}^{N}\mathbf{1}\{X_j\le X_i\}$. When there are no ties, $R=(R_1,\dots,R_N)$ is a permutation of $\{1,\dots,N\}$ and $X_i=X_{(R_i)}$, where $X_{(1)}\lt\cdots\lt X_{(N)}$ are the order statistics (§4.1).
- The antirank $D_k$ is the index of the $k$-th smallest observation: $X_{D_k}=X_{(k)}$, so $D$ is the inverse permutation of $R$.
With ties, tied observations receive the average of the ranks they occupy (midranks).
Let $X_1,\dots,X_N$ be iid with a continuous cdf $F$. Then:
- $P(X_i=X_j\text{ for some }i\ne j)=0$;
- the rank vector $R$ is uniformly distributed over the $N!$ permutations of $\{1,\dots,N\}$;
- $R$ is independent of the vector of order statistics $(X_{(1)},\dots,X_{(N)})$;
- each $R_i$ is uniform on $\{1,\dots,N\}$, with $E[R_i]=\frac{N+1}{2}$, $\operatorname{Var}(R_i)=\frac{N^2-1}{12}$ and $\operatorname{Cov}(R_i,R_j)=-\frac{N+1}{12}$ for $i\ne j$.
Consequently every statistic that is a function of $R$ alone is distribution-free over the family of all iid continuous laws.
Proof. (1) For $i\ne j$, by independence and Fubini, $P(X_i=X_j)=\int P(X_j=x)\,dF(x)=0$, because a continuous $F$ gives every single point probability $0$; a finite union of null events is null.
(2) and (3) Let $\pi$ be any permutation and put $X^\pi=(X_{\pi(1)},\dots,X_{\pi(N)})$. Because the $X_i$ are iid, $X^\pi$ has the same joint distribution as $X$. The order statistics of $X^\pi$ are those of $X$, and the rank vector of $X^\pi$ is $R\circ\pi$. Hence for every permutation $r$ and every Borel set $B$,
$$P\big(R=r,\ X_{(\cdot)}\in B\big)=P\big(R\circ\pi=r,\ X_{(\cdot)}\in B\big)=P\big(R=r\circ\pi^{-1},\ X_{(\cdot)}\in B\big).$$As $\pi$ runs over all permutations, $r\circ\pi^{-1}$ runs over all permutations, so the $N!$ events $\{R=r,\ X_{(\cdot)}\in B\}$ have equal probabilities. By (1) they partition $\{X_{(\cdot)}\in B\}$ up to a null set, so each has probability $P(X_{(\cdot)}\in B)/N!$. Taking $B$ to be everything gives $P(R=r)=1/N!$, and then $P(R=r,X_{(\cdot)}\in B)=P(R=r)P(X_{(\cdot)}\in B)$, which is independence.
(4) Exactly $(N-1)!$ permutations put the value $k$ in place $i$, so $P(R_i=k)=1/N$. Then $E[R_i]=\frac{N+1}{2}$ and $E[R_i^2]=\frac{(N+1)(2N+1)}{6}$, so $$\operatorname{Var}(R_i)=\frac{(N+1)(2N+1)}{6}-\frac{(N+1)^2}{4}=\frac{N^2-1}{12}.$$ Finally $\sum_iR_i=\frac{N(N+1)}{2}$ is constant, so $0=\operatorname{Var}\left(\sum_iR_i\right)$, that is, $N\operatorname{Var}(R_1)+N(N-1)\operatorname{Cov}(R_1,R_2)=0$, which gives $\operatorname{Cov}(R_1,R_2)=-\frac{N+1}{12}$. ∎
Everything in this section rests on Theorem 5.20: once a test statistic is a function of ranks (or signs, or runs), its null distribution is a counting problem. The simplest such statistic uses only signs.
Let $X_1,\dots,X_n$ be iid with cdf $F$ and median $\theta$, and let $\theta_0$ be a given number with $P(X_1=\theta_0)=0$. The sign statistic is
$$S=\#\{i: X_i\gt\theta_0\}=\sum_{i=1}^{n}\mathbf{1}\{X_i\gt\theta_0\}.$$The sign test of $H_0:\theta=\theta_0$ rejects for large $S$ against $\theta\gt\theta_0$, for small $S$ against $\theta\lt\theta_0$, and for $S$ far from $n/2$ against $\theta\ne\theta_0$. For paired data $(X_i,Y_i)$ the test is applied to the differences $D_i=Y_i-X_i$. Observations exactly equal to $\theta_0$ (which occur when data are rounded) are discarded and $n$ is reduced accordingly; the test is then carried out conditionally on the number of non-zero differences.
In the setting of Definition 5.14 let $p=P(X_1\gt\theta_0)$.
- $S\sim\operatorname{Bin}(n,p)$. Under $H_0$ (that is, $F(\theta_0)=\frac12$) $S\sim\operatorname{Bin}\left(n,\frac12\right)$ for every such $F$: the sign test is distribution-free.
- The test "reject when $S\ge k$" has size $\alpha_k=2^{-n}\sum_{j=k}^{n}\binom nj$ and power $\beta(p)=P(\operatorname{Bin}(n,p)\ge k)$, which is strictly increasing in $p$ for $1\le k\le n$. Hence it also has size $\alpha_k$ for the composite hypothesis $p\le\frac12$ (median $\le\theta_0$).
- (Consistency) Fix $\alpha\in(0,1)$ and let $k_n$ be the smallest $k$ with $\alpha_k\le\alpha$. If $p\gt\frac12$, the power $P(S\ge k_n)\to1$ as $n\to\infty$.
- The one-sided $p$-value for observed $S=s$ is $P\left(\operatorname{Bin}(n,\frac12)\ge s\right)$. For large $n$, $\dfrac{S-n/2}{\sqrt n/2}\xrightarrow{d}N(0,1)$ under $H_0$, and $P(S\ge s)\approx1-\Phi\left(\dfrac{s-\frac12-\frac n2}{\sqrt n/2}\right)$ with the continuity correction.
Proof. (1) The indicators $\mathbf 1\{X_i\gt\theta_0\}$ are iid Bernoulli with success probability $p=1-F(\theta_0)$, which equals $\frac12$ under $H_0$; their sum is binomial.
(2) The size is the binomial tail at $p=\frac12$. For monotonicity, couple: let $V_1,\dots,V_n$ be iid $U(0,1)$ and $S_p=\sum\mathbf 1\{V_i\le p\}\sim\operatorname{Bin}(n,p)$. If $p\lt p'$ then $S_p\le S_{p'}$ pointwise, so $P(S_p\ge k)\le P(S_{p'}\ge k)$; the inequality is strict because the event $\{S_p=k-1,\ S_{p'}\ge k\}$ (for instance exactly $k-1$ of the $V_i$ below $p$ and one more in $(p,p']$) has positive probability. So $\sup_{p\le1/2}\beta(p)=\beta(\frac12)=\alpha_k$.
(3) Under $p=\frac12$, Chebyshev's inequality gives $\alpha_k\le P\left(|S-\frac n2|\ge k-\frac n2\right)\le\dfrac{n/4}{(k-n/2)^2}$, so every $k\ge\frac n2+\frac{\sqrt n}{2\sqrt\alpha}$ satisfies $\alpha_k\le\alpha$, and therefore $k_n\le\frac n2+\frac{\sqrt n}{2\sqrt\alpha}+1$. Thus $k_n/n\le\frac12+\varepsilon_n$ with $\varepsilon_n\to0$. If $p\gt\frac12$, the weak law of large numbers gives $S/n\xrightarrow{P}p$, so $P(S\ge k_n)\ge P(S/n\ge\frac12+\varepsilon_n)\to1$.
(4) The $p$-value is the null probability of a result at least as extreme as $s$. The normal limit is the de Moivre–Laplace theorem (§2.3), and the continuity correction replaces $P(S\ge s)$ by the normal area beyond $s-\frac12$. ∎
Two remarks place the sign test among the tests of §5.1. Given only the signs, $S$ is sufficient for $p$ and the binomial family has monotone likelihood ratio in $S$; by the Karlin–Rubin theorem (§5.1) the one-sided sign test is UMP among tests that use only the signs. And the sign test has an exact dual confidence interval made of order statistics.
Proof. Let $V=\#\{i:X_i\le m\}\sim\operatorname{Bin}(n,\frac12)$. Now $X_{(k)}\le m$ holds iff at least $k$ observations are $\le m$, i.e. $V\ge k$. Also $X_{(n-k+1)}\ge m$ holds iff at most $n-k$ observations are $\lt m$; since $P(X_i=m)=0$, the number of observations below $m$ equals $V$ almost surely, so this is $V\le n-k$. Hence the coverage is $P(k\le V\le n-k)$, which is $1-P(V\le k-1)-P(V\ge n-k+1)$, that is, $1-2P(V\le k-1)$, by the symmetry of $\operatorname{Bin}(n,\frac12)$. The duality statement is the same argument with $m$ replaced by $\theta_0$: $\theta_0\in[X_{(k)},X_{(n-k+1)}]$ iff $k\le\#\{X_i\le\theta_0\}\le n-k$ iff $k\le S\le n-k$. ∎
The Wilcoxon Signed-Rank Test
The sign test uses only whether each observation lies above or below $\theta_0$; an observation $0.01$ above counts as much as one $4$ kg above. If we are willing to assume that the distribution is symmetric about its centre, the sizes of the deviations can be used too — through their ranks, which keeps the test distribution-free.
Let $Z_i=X_i-\theta_0$ ($i=1,\dots,n$), assumed non-zero with distinct absolute values. Let $R_i^+$ be the rank of $|Z_i|$ among $|Z_1|,\dots,|Z_n|$. The signed-rank statistics are
$$T^+=\sum_{i=1}^{n}R_i^+\,\mathbf 1\{Z_i\gt0\},\qquad T^-=\sum_{i=1}^{n}R_i^+\,\mathbf 1\{Z_i\lt0\},$$so that $T^++T^-=\frac{n(n+1)}{2}$. The Wilcoxon signed-rank test of $H_0$: "the distribution of $X$ is symmetric about $\theta_0$" rejects for large $T^+$ against a shift to the right ($\theta\gt\theta_0$), for small $T^+$ against a shift to the left, and for both against $\theta\ne\theta_0$. For paired data it is applied to the differences. Zero differences are discarded; tied $|Z_i|$ receive midranks.
Let $Z_1,\dots,Z_n$ be iid with a continuous distribution symmetric about $0$. Then:
- the signs $\operatorname{sgn}(Z_1),\dots,\operatorname{sgn}(Z_n)$ are iid, equal to $\pm1$ with probability $\frac12$ each, and independent of $(|Z_1|,\dots,|Z_n|)$;
- $T^+$ has the same distribution as $V=\sum_{k=1}^{n}k\,B_k$, where $B_1,\dots,B_n$ are iid Bernoulli$\left(\frac12\right)$;
- $E[T^+]=\dfrac{n(n+1)}{4}$ and $\operatorname{Var}(T^+)=\dfrac{n(n+1)(2n+1)}{24}$;
- $T^+$ and $T^-$ have the same distribution, which is symmetric about $\frac{n(n+1)}4$; $P(T^+=t)=c_n(t)/2^n$, where $c_n(t)$ is the number of subsets of $\{1,\dots,n\}$ with sum $t$; the probability generating function is $E\left[s^{T^+}\right]=\prod_{k=1}^{n}\frac{1+s^k}{2}$, and $c_n(t)=c_{n-1}(t)+c_{n-1}(t-n)$;
- $\left(T^+-\frac{n(n+1)}4\right)\big/\sqrt{\frac{n(n+1)(2n+1)}{24}}\xrightarrow{d}N(0,1)$ as $n\to\infty$.
Proof. (1) By continuity $P(Z_1=0)=0$. Symmetry means $-Z_1$ has the same law as $Z_1$. For a Borel set $A\subseteq(0,\infty)$, the events $\{Z_1\gt0,|Z_1|\in A\}=\{Z_1\in A\}$ and $\{Z_1\lt0,|Z_1|\in A\}=\{-Z_1\in A\}$ therefore have equal probabilities, and together they make up $\{|Z_1|\in A\}$ up to a null set. So $P(Z_1\gt0,\ |Z_1|\in A)=\frac12P(|Z_1|\in A)$: the sign of $Z_1$ is independent of $|Z_1|$ and fair. Independence across $i$ gives the statement for the vectors.
(2) Write $T^+=\sum_{k=1}^{n}k\,\mathbf 1\{Z_{D_k}\gt0\}$, where $D_k$ is the index of the $k$-th smallest $|Z_i|$ (Definition 5.13). The antiranks $D_k$ are functions of $(|Z_1|,\dots,|Z_n|)$. Conditionally on the absolute values, $D$ is fixed and, by (1), the signs are still iid fair; so the conditional law of $T^+$ is the law of $V$. It does not depend on the absolute values, so it is also the unconditional law.
(3) $E[V]=\sum k\cdot\frac12=\frac{n(n+1)}4$ and $\operatorname{Var}(V)=\sum k^2\cdot\frac14=\frac{n(n+1)(2n+1)}{24}$.
(4) The map $(B_k)\mapsto(1-B_k)$ preserves the law of $(B_k)$ and sends $V$ to $\frac{n(n+1)}2-V$; under $H_0$ this is $T^-$. Each of the $2^n$ sign patterns is equally likely and $V=t$ exactly for the patterns whose set $\{k:B_k=1\}$ has sum $t$. The pgf factorises by independence: $E[s^{kB_k}]=\frac{1+s^k}{2}$. For the recursion, split the subsets with sum $t$ according to whether they contain $n$.
(5) The summands $Y_k=k(B_k-\frac12)$ are independent, centred and bounded by $n/2$. Lyapunov's condition holds: $\sum_kE|Y_k|^3=\sum_k k^3/8=O(n^4)$, while $s_n^3=\operatorname{Var}(V)^{3/2}$ is of order $n^{9/2}$, so the ratio tends to $0$ and the central limit theorem for independent non-identical summands applies. ∎
Small-sample tables. Because the null distributions are discrete, a test can rarely have size exactly $\alpha$. The table gives, for one-sided tests at nominal level $5\%$, the largest $c$ with $P(S\le c)\le0.05$ (sign test; by symmetry also reject when $S\ge n-c$) and the largest $c$ with $P(T^+\le c)\le0.05$ (signed-rank test), together with the attained sizes. All entries were computed by exact enumeration.
| $n$ | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 15 |
|---|---|---|---|---|---|---|---|---|---|
| sign: reject if $S\le c$ | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
| attained size | 0.0313 | 0.0156 | 0.0078 | 0.0352 | 0.0195 | 0.0107 | 0.0327 | 0.0193 | 0.0176 |
| signed rank: reject if $T^+\le c$ | 0 | 2 | 3 | 5 | 8 | 10 | 13 | 17 | 30 |
| attained size | 0.0313 | 0.0469 | 0.0391 | 0.0391 | 0.0488 | 0.0420 | 0.0415 | 0.0461 | 0.0473 |
The signed-rank statistic has a second description that explains what it really measures when symmetry fails, and leads to a robust estimator of the centre.
Let $z_1,\dots,z_n$ be real numbers, non-zero, with distinct absolute values. Then
$$T^+=\#\left\{(i,j):1\le i\le j\le n,\ z_i+z_j\gt0\right\},$$the number of positive Walsh averages $\frac{z_i+z_j}{2}$ ($i\le j$). Consequently, for $Z_1,\dots,Z_n$ iid continuous (symmetric or not),
$$E[T^+]=n\,p_1+\binom n2p_2,\qquad p_1=P(Z_1\gt0),\quad p_2=P(Z_1+Z_2\gt0).$$Proof. Consider a pair $i\le j$ and let $k$ be the one of the two with the larger absolute value (if $i=j$, $k=i$). Then $z_i+z_j$ has the sign of $z_k$: if $i=j$ this is clear, and if $i\ne j$ the other term has absolute value strictly smaller than $|z_k|$ and cannot change the sign. So the pairs with a positive Walsh average are exactly the pairs whose larger-in-absolute-value member is positive. A positive $z_k$ whose absolute rank is $R_k^+$ is the larger member of exactly $R_k^+$ pairs: itself, and the $R_k^+-1$ pairs formed with the observations of smaller absolute value. Summing over the positive $z_k$ gives $\sum_kR_k^+\mathbf 1\{z_k\gt0\}=T^+$. For the expectation, take expectations of the $n$ indicators with $i=j$ and of the $\binom n2$ indicators with $i\lt j$. ∎
Applying the theorem to $z_i=x_i-\theta$ shows that $T^+(\theta)$ decreases by one each time $\theta$ passes a Walsh average $\frac{x_i+x_j}{2}$. The value of $\theta$ that makes $T^+(\theta)$ closest to its null centre $\frac{n(n+1)}4$ is the median of the $\frac{n(n+1)}{2}$ Walsh averages — the Hodges–Lehmann estimator of the centre of symmetry, a robust alternative to $\bar x$; and if $c$ is the largest value with $P(T^+\le c)\le\alpha/2$, the Walsh averages ranked $c+1$ and $\frac{n(n+1)}2-c$ from below are the end points of the $1-2P(T^+\le c)$ confidence interval dual to the signed-rank test.
How much is lost by using ranks instead of the observations? The standard answer compares the sample sizes two tests need to reach the same power against small alternatives.
Let $X_1,\dots,X_n$ be iid with density $f(x-\theta)$, where $f$ is continuous, symmetric about $0$ and has finite variance $\sigma^2$, and consider tests of $\theta=0$ against $\theta\gt0$. The Pitman asymptotic relative efficiency (the limiting ratio of the sample sizes needed by the $t$ test and by the other test for the same power against alternatives $\theta_n=h/\sqrt n$) is
$$e_{S,t}=4\sigma^2f(0)^2,\qquad e_{W,t}=12\sigma^2\left(\int_{-\infty}^{\infty}f^2(x)\,dx\right)^2$$for the sign test $S$ and the signed-rank test $W$. The same value $e_{W,t}$ is the efficiency of the Mann–Whitney test relative to the two-sample $t$ test in the shift model. For the normal law $e_{S,t}=2/\pi=0.637$ and $e_{W,t}=3/\pi=0.955$; for the Laplace law $2$ and $1.5$; for the logistic law $0.822$ and $1.097$; for $t_3$ $1.62$ and $1.90$. For every such $f$, $e_{W,t}\ge108/125=0.864$ (Hodges–Lehmann).
Proof sketch. For a test based on $T_n$ whose mean $\mu_n(\theta)$ and null standard deviation $\sigma_n$ satisfy $\sqrt n\,\sigma_n\to\sigma_T$ and $\mu_n'(0)\to\mu'$, the asymptotic power against $h/\sqrt n$ is $1-\Phi(z_\alpha-h\,\mu'/\sigma_T)$, so the efficacy is $(\mu'/\sigma_T)^2$ and the ARE of two tests is the ratio of their efficacies. For $\bar X$ (the $t$ test) the efficacy is $1/\sigma^2$. For $S/n$: mean $1-F(-\theta)$ with derivative $f(0)$, null sd $\frac1{2\sqrt n}$, efficacy $4f(0)^2$. For $T^+/\binom n2$: by Theorem 5.24 its mean is $p_2(\theta)+O(1/n)=P(Z_1+Z_2\gt-2\theta)$, with derivative $2\int f^2$ at $0$, and its null sd is about $\frac{\sqrt{n^3/12}}{n^2/2}=\frac{1}{\sqrt{3n}}$, so the efficacy is $12\left(\int f^2\right)^2$. The quoted values follow by evaluating $f(0)$ and $\int f^2$; for instance, for $N(0,1)$, $f(0)^2=\frac1{2\pi}$ and $\int f^2=\frac1{2\sqrt\pi}$. The lower bound $0.864$ comes from minimising $\sigma^2\left(\int f^2\right)^2$ over symmetric densities, which is attained by a parabolic density. ∎
Two-Sample Rank Tests: Mann–Whitney–Wilcoxon and the Median Test
Now we observe two independent samples, $X_1,\dots,X_m$ from $F$ and $Y_1,\dots,Y_n$ from $G$, both continuous, with $N=m+n$. The null hypothesis is $H_0:F=G$; the alternative of main interest is that the $Y$'s tend to be larger (or smaller) than the $X$'s — for example the shift model $G(x)=F(x-\Delta)$ with $\Delta\ne0$. Under $H_0$ the $N$ observations are iid, so by Theorem 5.20 every arrangement of the labels "$x$" and "$y$" in the combined ordering is equally likely.
Rank all $N$ observations together. The Wilcoxon rank-sum statistic $W$ is the sum of the ranks of the $Y$'s, and the Mann–Whitney statistic is
$$U=\#\{(i,j): X_i\lt Y_j\}=\sum_{i=1}^{m}\sum_{j=1}^{n}\mathbf 1\{X_i\lt Y_j\}.$$The Mann–Whitney–Wilcoxon test rejects $H_0:F=G$ for large $W$ (equivalently large $U$) when the alternative is that the $Y$'s tend to be larger, for small values in the opposite case, and in both tails for a two-sided alternative. $U/(mn)$ estimates $p=P(X\lt Y)$.
Let $X_1,\dots,X_m$ iid $F$ and $Y_1,\dots,Y_n$ iid $G$ be independent, with $F,G$ continuous.
- $W=U+\dfrac{n(n+1)}{2}$ (with probability one).
- For any $F,G$: $E[U]=mn\,p$, where $p=P(X_1\lt Y_1)$.
- Under $H_0:F=G$, the set of ranks of the $Y$'s is uniformly distributed over the $\binom Nn$ subsets of size $n$ of $\{1,\dots,N\}$. Hence $P(U=u)=c_{m,n}(u)\big/\binom Nn$, where $c_{m,n}(u)$ is the number of arrangements of $m$ letters $x$ and $n$ letters $y$ in which exactly $u$ pairs have the $x$ before the $y$; these satisfy $c_{m,n}(u)=c_{m-1,n}(u)+c_{m,n-1}(u-m)$, with $c_{m,0}(0)=c_{0,n}(0)=1$.
- Under $H_0$: $E[U]=\dfrac{mn}2$, $\operatorname{Var}(U)=\dfrac{mn(N+1)}{12}$, $E[W]=\dfrac{n(N+1)}2$ and $\operatorname{Var}(W)=\operatorname{Var}(U)$; $U$ and $mn-U=\#\{(i,j):Y_j\lt X_i\}$ have the same distribution, symmetric about $\frac{mn}2$.
- Under $H_0$, $\dfrac{U-mn/2}{\sqrt{mn(N+1)/12}}\xrightarrow{d}N(0,1)$ as $\min(m,n)\to\infty$. If $m/N\to\lambda\in(0,1)$, the two-sided test at a fixed level is consistent against $(F,G)$ if and only if $p\ne\frac12$.
Proof. (1) Let $Y_{(1)}\lt\cdots\lt Y_{(n)}$ be the ordered $Y$'s. The combined rank of $Y_{(j)}$ is the number of $X$'s below it plus the number of $Y$'s at or below it, namely $\#\{i:X_i\lt Y_{(j)}\}+j$. Summing over $j$, $W=\sum_j\#\{i:X_i\lt Y_{(j)}\}+\sum_jj=U+\frac{n(n+1)}2$.
(2) $E[\mathbf 1\{X_i\lt Y_j\}]=p$ for each of the $mn$ pairs.
(3) Under $H_0$ the $N$ observations are iid continuous, so their rank vector is uniform over all permutations (Theorem 5.20); the set of positions occupied by the $Y$'s is then uniform over the $n$-subsets (each subset arises from $m!\,n!$ permutations). $U$ is a function of the arrangement only. For the recursion, look at the largest observation. If it is an $X$, it lies before no $y$, contributes nothing to $U$, and removing it leaves an arrangement of $m-1$ $x$'s and $n$ $y$'s with the same $U$. If it is a $Y$, all $m$ $x$'s lie before it, so it contributes $m$, and removing it leaves an arrangement with $U-m$.
(4) Write $I_{ij}=\mathbf 1\{X_i\lt Y_j\}$. Under $H_0$, $P(I_{ij}=1)=\frac12$ and $\operatorname{Var}(I_{ij})=\frac14$. If $i\ne k$ and $j\ne l$, $I_{ij}$ and $I_{kl}$ are independent. If $i=k$, $j\ne l$: $P(I_{ij}=I_{il}=1)$ is the probability that $X_i$ is the smallest of $X_i,Y_j,Y_l$, namely $\frac13$, so $\operatorname{Cov}=\frac13-\frac14=\frac1{12}$; likewise for $j=l$, $i\ne k$ ($Y_j$ the largest of three). There are $mn(n-1)$ ordered pairs of the first kind and $nm(m-1)$ of the second, so
$$\operatorname{Var}(U)=\frac{mn}{4}+\frac{mn(n-1)+mn(m-1)}{12}=\frac{mn(m+n+1)}{12}.$$Then $E[W]=\frac{mn}2+\frac{n(n+1)}2=\frac{n(N+1)}2$ by (1). Reading the arrangement from right to left gives another equally likely arrangement in which every "$x$ before $y$" pair becomes "$y$ before $x$"; so $U$ and $mn-U$ have the same law.
(5) The normal limit can be proved by writing $U$ as a $U$-statistic (Hoeffding's projection) or from the generating function of $c_{m,n}$; we omit it. For consistency: $\operatorname{Var}(U/mn)\to0$ under any $(F,G)$ (a similar covariance count), so $U/mn\xrightarrow{P}p$, while the null critical values of $U/mn$ tend to $\frac12$ (by the normal limit, they are $\frac12+O(N^{-1/2})$). If $p\ne\frac12$ the power tends to $1$; if $p=\frac12$ the statistic stays centred at $\frac{mn}2$ and the power converges to a limit strictly below $1$. ∎
Ties. With tied observations use midranks; the null mean of $W$ is unchanged and, conditionally on the tie pattern, $\operatorname{Var}(W)=\frac{mn}{12}\left[N+1-\frac{\sum(t^3-t)}{N(N-1)}\right]$, the sum running over groups of $t$ tied values. The table gives exact one-sided $5\%$ critical values for equal sample sizes: reject in favour of "$Y$ smaller" when $U\le c$.
| $m=n$ | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|
| reject if $U\le c$ | 0 | 1 | 4 | 7 | 11 | 15 |
| attained size | 0.0500 | 0.0286 | 0.0476 | 0.0465 | 0.0487 | 0.0415 |
A cruder but very simple two-sample test classifies each observation as above or below the combined median and compares the two samples by a $2\times2$ table.
Proof. The event $\{Y_j\gt M\}$ means that $Y_j$ occupies one of the $t$ largest ranks, a fixed set of $t$ ranks. By Theorem 5.26(3) the $n$ ranks of the $Y$'s form a uniformly random $n$-subset of $\{1,\dots,N\}$, so the number of them among the top $t$ ranks is the number of "marked" items in a sample of size $n$ drawn without replacement from $N$ items of which $t$ are marked — the hypergeometric law (§2.1), with the stated mean and variance. Conditioning on the margins of the $2\times2$ table is exactly Fisher's exact test. ∎
Runs and the Kolmogorov–Smirnov Tests
The tests so far look for a difference in location. Two further classical tools look at a sample in other ways: the runs test asks whether a sequence of two kinds of symbols looks random, and the Kolmogorov–Smirnov tests compare whole distribution functions.
Consider a sequence of $N=m+n$ symbols, $m$ of type $a$ and $n$ of type $b$. A run is a maximal block of consecutive identical symbols; $R$ denotes the total number of runs. (For example $aab\,bba\,b$ — that is, $aabbbab$ — has the four runs $aa,\ bbb,\ a,\ b$.) The runs test of the hypothesis that all $\binom Nm$ arrangements are equally likely rejects when $R$ is too small (clustering, a trend) or too large (alternation). Two standard uses are:
- Randomness of a sequence of observations $x_1,\dots,x_N$ taken in time order: label each $a$ or $b$ according as it is above or below the sample median (or success/failure), and count runs.
- The Wald–Wolfowitz two-sample test of $F=G$: order the combined sample, label each observation $x$ or $y$, and reject when $R$ is small.
If all $\binom Nm$ arrangements of $m$ $a$'s and $n$ $b$'s are equally likely ($m,n\ge1$), then for $k\ge1$
$$P(R=2k)=\frac{2\binom{m-1}{k-1}\binom{n-1}{k-1}}{\binom Nm},$$ $$P(R=2k+1)=\frac{\binom{m-1}{k}\binom{n-1}{k-1}+\binom{m-1}{k-1}\binom{n-1}{k}}{\binom Nm},$$and
$$E[R]=1+\frac{2mn}{N},\qquad \operatorname{Var}(R)=\frac{2mn(2mn-N)}{N^2(N-1)}.$$As $m,n\to\infty$ with $m/N\to\lambda\in(0,1)$, $R$ is asymptotically normal with this mean and variance.
Proof. The number of ways to write $m$ symbols $a$ as an ordered sequence of $r$ non-empty runs is the number of compositions of $m$ into $r$ positive parts, $\binom{m-1}{r-1}$ ("stars and bars": choose $r-1$ of the $m-1$ gaps). Runs of $a$ and $b$ alternate. If $R=2k$ there are $k$ runs of each type, and the sequence starts with $a$ or with $b$: $2\binom{m-1}{k-1}\binom{n-1}{k-1}$ arrangements. If $R=2k+1$, one type has $k+1$ runs and starts and ends the sequence, the other has $k$: $\binom{m-1}{k}\binom{n-1}{k-1}$ arrangements with $k+1$ runs of $a$, plus the symmetric term. Divide by the number $\binom Nm$ of arrangements.
For the mean, let $J_i=\mathbf 1\{\text{positions }i-1\text{ and }i\text{ differ}\}$, $i=2,\dots,N$, so that $R=1+\sum_{i=2}^{N}J_i$. Any two given positions carry one $a$ and one $b$ with probability $\frac{2mn}{N(N-1)}$, so $E[R]=1+(N-1)\frac{2mn}{N(N-1)}=1+\frac{2mn}{N}$. For the variance one needs, in addition, for adjacent indicators (patterns $aba$ or $bab$) $$P(J_i=J_{i+1}=1)=\frac{mn(m-1)+nm(n-1)}{N(N-1)(N-2)}=\frac{mn}{N(N-1)},$$ and when $|i-k|\ge2$ $$P(J_i=J_k=1)=\frac{4m(m-1)n(n-1)}{N(N-1)(N-2)(N-3)}$$ (the four positions involved hold two $a$'s and two $b$'s in one of four admissible orders). Summing the $N-1$ variances, the $2(N-2)$ adjacent covariances and the $(N-2)(N-3)$ remaining ones and simplifying gives the formula. The normal limit is a central limit theorem for this sum of weakly dependent indicators; we omit it. ∎
For $m=n$ the formulas become $E[R]=n+1$ and $\operatorname{Var}(R)=\frac{n(n-1)}{2n-1}$. As a two-sample test the Wald–Wolfowitz test is consistent against all alternatives $F\ne G$ but has low power against shifts; Mann–Whitney is preferred for location problems.
The tests above use ranks or signs. The Kolmogorov–Smirnov tests use the whole empirical distribution function, the natural nonparametric estimate of $F$.
For a sample $X_1,\dots,X_n$ the empirical distribution function is $F_n(x)=\frac1n\#\{i:X_i\le x\}$, a step function rising by $\frac1n$ at each observation. For a completely specified continuous cdf $F_0$ the one-sample Kolmogorov–Smirnov statistics are
$$D_n=\sup_x|F_n(x)-F_0(x)|,\quad D_n^+=\sup_x\big(F_n(x)-F_0(x)\big),\quad D_n^-=\sup_x\big(F_0(x)-F_n(x)\big).$$The KS test of $H_0:F=F_0$ rejects for large $D_n$. For two independent samples with empirical cdfs $F_m$ (of the $X$'s) and $G_n$ (of the $Y$'s), the two-sample statistic is $D_{m,n}=\sup_x|F_m(x)-G_n(x)|$, and the test rejects $F=G$ for large $D_{m,n}$.
Let $X_1,\dots,X_n$ be iid with cdf $F$.
- For each $x$, $nF_n(x)\sim\operatorname{Bin}(n,F(x))$, so $E[F_n(x)]=F(x)$, $\operatorname{Var}(F_n(x))=\frac{F(x)(1-F(x))}{n}$, $F_n(x)\to F(x)$ almost surely and $\sqrt n\,(F_n(x)-F(x))\xrightarrow{d}N\big(0,F(x)(1-F(x))\big)$.
- For $x\le y$, $\operatorname{Cov}(F_n(x),F_n(y))=\frac{F(x)(1-F(y))}{n}$.
- (Glivenko–Cantelli) $\sup_x|F_n(x)-F(x)|\to0$ almost surely.
Proof. (1) $nF_n(x)$ is a sum of $n$ iid Bernoulli$(F(x))$ indicators $\mathbf 1\{X_i\le x\}$; apply the strong law and the central limit theorem. (2) Indicators with different $i$ are independent, and $\operatorname{Cov}(\mathbf 1\{X\le x\},\mathbf 1\{X\le y\})=F(x)-F(x)F(y)$; divide by $n$.
(3) We give the proof for continuous $F$ (the general case adds the jump points to the grid). Fix $k\in\mathbb N$. By the intermediate value theorem choose $x_1\lt\cdots\lt x_{k-1}$ with $F(x_j)=j/k$, and put $x_0=-\infty$, $x_k=+\infty$ (with $F_n=F=0$ at $-\infty$ and $1$ at $+\infty$). For $x_{j-1}\le x\le x_j$, monotonicity gives
$$F_n(x)-F(x)\le F_n(x_j)-F(x_{j-1})=F_n(x_j)-F(x_j)+\tfrac1k,$$ $$F_n(x)-F(x)\ge F_n(x_{j-1})-F(x_j)=F_n(x_{j-1})-F(x_{j-1})-\tfrac1k.$$Hence $$\sup_x|F_n(x)-F(x)|\le\max_{0\le j\le k}|F_n(x_j)-F(x_j)|+\frac1k.$$ By (1) the maximum of these finitely many terms tends to $0$ almost surely, so $\limsup_n\sup_x|F_n-F|\le\frac1k$ almost surely. Intersecting the countably many almost-sure events for $k=1,2,\dots$ gives the limit $0$. ∎
Let $F_0$ be continuous, let $X_1,\dots,X_n$ be iid $F_0$, and put $U_{(i)}=F_0(X_{(i)})$.
- $D_n$, $D_n^+$ and $D_n^-$ have the same distributions as the corresponding statistics computed from $n$ iid $U(0,1)$ observations against the uniform cdf: they are distribution-free over all continuous $F_0$.
- They can be computed from the order statistics: $$D_n^+=\max_{1\le i\le n}\left(\frac in-U_{(i)}\right),\qquad D_n^-=\max_{1\le i\le n}\left(U_{(i)}-\frac{i-1}n\right),$$ and $D_n=\max(D_n^+,D_n^-)$.
- (Kolmogorov) For $x\gt0$, $P(\sqrt n\,D_n\le x)\to K(x)$, where $$K(x)=1-2\sum_{k=1}^{\infty}(-1)^{k-1}e^{-2k^2x^2}.$$ The upper $10\%$, $5\%$ and $1\%$ points of $K$ are $1.2238$, $1.3581$ and $1.6276$. (Smirnov) $P(\sqrt n\,D_n^+\le x)\to1-e^{-2x^2}$.
- If the $X_i$ are iid $F\ne F_0$, then $D_n\to\sup_x|F(x)-F_0(x)|\gt0$ almost surely, and the KS test at any fixed level is consistent against every such alternative.
- For two samples with $F=G$ continuous, $D_{m,n}$ depends only on the arrangement of the $x$'s and $y$'s in the combined ordering, so it is distribution-free; $P\left(\sqrt{\tfrac{mn}{N}}\,D_{m,n}\le x\right)\to K(x)$ as $m,n\to\infty$. For $m=n$ and $k\in\mathbb N$, $$P\left(D_{n,n}\ge\tfrac kn\right)=\frac{2\sum_{j\ge1}(-1)^{j-1}\binom{2n}{n-jk}}{\binom{2n}n}.$$
Proof. (1) By the probability integral transform (§1.3) the $U_i=F_0(X_i)$ are iid $U(0,1)$; let $G_n$ be their empirical cdf. Since $F_0$ is non-decreasing, $X_i\le x$ implies $U_i\le F_0(x)$. Conversely, $U_i\le F_0(x)$ with $X_i\gt x$ forces $F_0$ to be constant on $[x,X_i]$, i.e. $X_i$ lies in an interval of constancy of $F_0$; there are at most countably many maximal such intervals, each of probability $0$, so with probability one this never happens. Hence, almost surely, $F_n(x)=G_n(F_0(x))$ for all $x$, and
$$D_n=\sup_x\big|G_n(F_0(x))-F_0(x)\big|=\sup_{0\lt u\lt1}|G_n(u)-u|,$$because the continuous $F_0$ takes every value in $(0,1)$ (intermediate value theorem). The same argument applies to $D_n^\pm$.
(2) Put $U_{(0)}=0$, $U_{(n+1)}=1$. On $[U_{(i)},U_{(i+1)})$ the function $G_n$ equals $\frac in$ while $u$ increases, so $G_n(u)-u$ is largest at the left end, where it equals $\frac in-U_{(i)}$, and $u-G_n(u)$ approaches its supremum $U_{(i+1)}-\frac in$ at the right end. Taking the maximum over $i$ (the terms with $i=0$ and $i=n$ are $\le0$ or repeat others) gives the formulas.
(3) and the two-sample limit in (5) are deep theorems (Kolmogorov 1933, Smirnov 1939; a modern proof shows that $\sqrt n\,(G_n(u)-u)$ converges to a Brownian bridge, whose maximum absolute value has cdf $K$); we only quote them. The formula for $P(D_{n,n}\ge k/n)$ comes from counting lattice paths by the reflection principle.
(4) By the triangle inequality, $\big|D_n-\sup_x|F-F_0|\big|\le\sup_x|F_n-F|\to0$ almost surely (Theorem 5.29). The critical values $c_n$ of $D_n$ at a fixed level tend to $0$ (by (3) they are about $c/\sqrt n$), so $P(D_n\gt c_n)\to1$.
(5) $F_m-G_n$ is a step function that changes only at the observations, and its value just after the $k$-th smallest combined observation is determined by how many $x$'s and $y$'s are among the first $k$. Under $H_0$ all arrangements are equally likely (Theorem 5.20), which does not depend on $F$. ∎
Practical values. Exact $5\%$ critical values of $D_n$ are $0.5633$, $0.4092$, $0.2941$ and $0.1340$ for $n=5$, $10$, $20$, $100$, against $1.3581/\sqrt n=0.6074$, $0.4295$, $0.3037$, $0.1358$. The modification $c\approx1.3581/\left(\sqrt n+0.12+0.11/\sqrt n\right)$ is accurate to three decimals for all $n\ge6$ (for $n=5$ it gives $0.5646$).
Rank Correlation and Tests of Independence
For paired observations $(X_1,Y_1),\dots,(X_n,Y_n)$ the Pearson correlation coefficient (§1.1) measures linear association and its standard test assumes bivariate normality. Rank correlations measure monotone association, are unchanged by any strictly increasing transformation of either variable, and give exactly distribution-free tests of independence.
Let $(x_i,y_i)$, $i=1,\dots,n$, have no ties in either coordinate. Let $r_i$ be the rank of $x_i$ among the $x$'s, $s_i$ the rank of $y_i$ among the $y$'s, and $d_i=r_i-s_i$.
- Spearman's rank correlation $r_s$ is the Pearson correlation coefficient of the pairs $(r_i,s_i)$.
- A pair of indices $\{i,j\}$ is concordant if $(x_i-x_j)(y_i-y_j)\gt0$ and discordant if $(x_i-x_j)(y_i-y_j)\lt0$. With $C$ concordant and $D$ discordant pairs, Kendall's tau is $\tau=\dfrac{C-D}{\binom n2}$.
For a random pair $(X,Y)$ with continuous marginal cdfs $F$ and $G$, and $(X_1,Y_1)$, $(X_2,Y_2)$, $(X_3,Y_3)$ independent copies, the population versions are Kendall's $\tau_{XY}=P(\text{conc})-P(\text{disc})$, the probability that $(X_1-X_2)(Y_1-Y_2)\gt0$ minus the probability that it is $\lt0$, and Spearman's $\rho_S=\operatorname{Corr}\big(F(X),G(Y)\big)$, which equals $12\,E[F(X)G(Y)]-3$. With ties one uses midranks (for $r_s$) and the tie-corrected $\tau_b$.
- $r_s=1-\dfrac{6\sum_{i=1}^{n}d_i^2}{n(n^2-1)}$.
- $-1\le r_s\le1$; $r_s=1$ iff $s_i=r_i$ for all $i$ (the $y$'s are an increasing function of the $x$'s on the data) and $r_s=-1$ iff $s_i=n+1-r_i$ for all $i$.
- If $X$ and $Y$ are independent and continuous, $r_s$ is distribution-free: it has the law of $r_s$ computed from $r_i=i$ and $s=\pi$, a uniformly random permutation. Under independence $E[r_s]=0$, $\operatorname{Var}(r_s)=\dfrac{1}{n-1}$, the law of $r_s$ is symmetric about $0$, and $\sqrt{n-1}\,r_s\xrightarrow{d}N(0,1)$.
Proof. (1) Both rank vectors are permutations of $\{1,\dots,n\}$, so $\sum r_i=\sum s_i=\frac{n(n+1)}2$, $\sum r_i^2=\sum s_i^2=\frac{n(n+1)(2n+1)}6$ and $\sum(r_i-\bar r)^2=\sum(s_i-\bar s)^2=\frac{n(n^2-1)}{12}$. From $\sum d_i^2=\sum r_i^2+\sum s_i^2-2\sum r_is_i$,
$$\sum(r_i-\bar r)(s_i-\bar s)=\sum r_is_i-n\left(\tfrac{n+1}{2}\right)^2=\frac{n(n^2-1)}{12}-\frac12\sum d_i^2,$$and dividing by $\frac{n(n^2-1)}{12}$ gives (1).
(2) A Pearson correlation lies in $[-1,1]$ (Cauchy–Schwarz, §1.1), with $\pm1$ iff $s_i=a+br_i$ for all $i$ with $b\gtrless0$. Since $r$ and $s$ are permutations of $1,\dots,n$, they have equal means and equal variances, so $b=\pm1$; $b=1$ forces $a=0$ and $b=-1$ forces $a=n+1$.
(3) Under independence the rank vectors of the $x$'s and of the $y$'s are independent and each uniform (Theorem 5.20). Relabel the pairs so that $r_i=i$; the $y$-ranks in this order form a permutation $\pi$, uniform and independent. With $a_i=i-\frac{n+1}2$ (so $\sum a_i=0$ and $\sum a_i^2=\frac{n(n^2-1)}{12}$), $r_s=\frac{12}{n(n^2-1)}\sum_ia_i\pi(i)$. Using Theorem 5.20(4) for the entries of $\pi$ ($\operatorname{Var}=\frac{n^2-1}{12}$, $\operatorname{Cov}=-\frac{n+1}{12}=-\frac{1}{n-1}\cdot\frac{n^2-1}{12}$),
$$\operatorname{Var}\Big(\sum a_i\pi(i)\Big)=\frac{n^2-1}{12}\Big(\sum a_i^2-\frac{1}{n-1}\sum_{i\ne j}a_ia_j\Big)=\frac{n^2-1}{12}\cdot\frac{n}{n-1}\sum a_i^2,$$since $\sum_{i\ne j}a_ia_j=(\sum a_i)^2-\sum a_i^2=-\sum a_i^2$. Substituting, $\operatorname{Var}(r_s)=\left(\frac{12}{n(n^2-1)}\right)^2\frac{n^2-1}{12}\cdot\frac{n}{n-1}\cdot\frac{n(n^2-1)}{12}=\frac1{n-1}$. The mean is $0$ because $E[\pi(i)]=\frac{n+1}2$ and $\sum a_i=0$. The reversed permutation $n+1-\pi$ is also uniform and changes $r_s$ to $-r_s$, giving symmetry. The normal limit is Hoeffding's combinatorial central limit theorem (statement only). ∎
- Without ties $C+D=\binom n2$, so $\tau=1-\dfrac{4D}{n(n-1)}$. If the pairs are listed in increasing order of $x$ and $\pi(1),\dots,\pi(n)$ are the corresponding $y$-ranks, $D$ is the number of inversions of $\pi$ (pairs $i\lt j$ with $\pi(i)\gt\pi(j)$).
- $-1\le\tau\le1$, with $\tau=1$ iff $\pi$ is the identity and $\tau=-1$ iff $\pi$ is the reversal.
- If $X$ and $Y$ are independent and continuous, then $D$ has the law of $J_1+J_2+\cdots+J_n$ with $J_k$ independent and uniform on $\{0,1,\dots,k-1\}$. Hence $$E\left[s^{D}\right]=\prod_{k=1}^{n}\frac{1+s+\cdots+s^{k-1}}{k},$$ $E[D]=\frac{n(n-1)}4$, $\operatorname{Var}(D)=\frac{n(n-1)(2n+5)}{72}$, so that $$E[\tau]=0,\qquad\operatorname{Var}(\tau)=\frac{2(2n+5)}{9n(n-1)};$$ $\tau$ is symmetric about $0$ and asymptotically normal.
Proof. (1) Every pair is concordant or discordant when there are no ties, so $C-D=\binom n2-2D$. After sorting by $x$, the pair $i\lt j$ is discordant exactly when the $y$-rank decreases, $\pi(i)\gt\pi(j)$. (2) $0\le D\le\binom n2$, with $D=0$ only for the identity and $D=\binom n2$ only for the reversal.
(3) As in Theorem 5.31, $\pi$ is a uniformly random permutation. Let $J_k=\#\{j\lt k:\pi(j)\gt\pi(k)\}$, the number of earlier entries larger than the $k$-th; then $D=\sum_kJ_k$. The value $J_k$ is determined by the relative rank of $\pi(k)$ among $\pi(1),\dots,\pi(k)$ ($J_k=k-$ that relative rank). The map sending the relative order of $\pi(1),\dots,\pi(k)$ to the pair (relative order of $\pi(1),\dots,\pi(k-1)$, relative rank of $\pi(k)$) is a bijection from a set of size $k!$ onto one of size $(k-1)!\cdot k$, and the relative order of the first $k$ entries of a uniform permutation is uniform. Hence the relative rank of $\pi(k)$ is uniform on $\{1,\dots,k\}$ and independent of the relative order of the first $k-1$ entries — which determines $J_1,\dots,J_{k-1}$. By induction $J_1,\dots,J_n$ are independent with $J_k$ uniform on $\{0,\dots,k-1\}$. This gives the pgf, $E[J_k]=\frac{k-1}2$ and $\operatorname{Var}(J_k)=\frac{k^2-1}{12}$, so
$$E[D]=\sum_{k=1}^{n}\frac{k-1}{2}=\frac{n(n-1)}4,\qquad\operatorname{Var}(D)=\sum_{k=1}^{n}\frac{k^2-1}{12}=\frac{n(n-1)(2n+5)}{72}.$$Then $E[\tau]=1-\frac{4}{n(n-1)}E[D]=0$ and $\operatorname{Var}(\tau)=\frac{16}{n^2(n-1)^2}\cdot\frac{n(n-1)(2n+5)}{72}=\frac{2(2n+5)}{9n(n-1)}$. Reversing $\pi$ turns $D$ into $\binom n2-D$ and $\tau$ into $-\tau$. Asymptotic normality follows from Lyapunov's theorem for the independent bounded $J_k$, as in Theorem 5.23. ∎
The numbers of permutations of $\{1,\dots,n\}$ with $D$ inversions (the Mahonian numbers, coefficients of the pgf times $n!$) give the exact null law of $\tau$: for $n=4$ they are $1,3,5,6,5,3,1$ for $D=0,\dots,6$.
Proof. Rank correlations are unchanged by increasing affine maps, so assume standard margins. First, Sheppard's orthant formula: if $(U,V)$ is bivariate normal with means $0$, variances $1$ and correlation $r$, then $P(U\gt0,V\gt0)=\frac14+\frac{\arcsin r}{2\pi}$. Indeed write $U=Z_1$, $V=rZ_1+\sqrt{1-r^2}\,Z_2$ with $Z_1,Z_2$ iid $N(0,1)$; the vector $(Z_1,Z_2)$ has a uniformly distributed direction, and $\{U\gt0,V\gt0\}$ is the intersection of two half-planes whose normals $(1,0)$ and $(r,\sqrt{1-r^2})$ make the angle $\arccos r$, a sector of angle $\pi-\arccos r$. So the probability is $\frac{\pi-\arccos r}{2\pi}=\frac14+\frac{\arcsin r}{2\pi}$.
For $\tau$: $(X_1-X_2,Y_1-Y_2)$ is bivariate normal with correlation $\rho$, so $P(\text{concordant})=2\left(\frac14+\frac{\arcsin\rho}{2\pi}\right)$ and $\tau=2P(\text{concordant})-1=\frac2\pi\arcsin\rho$.
For $\rho_S$: since $F(x)=P(X_2\lt x)$ and $G(y)=P(Y_3\lt y)$ for independent copies, $E[F(X_1)G(Y_1)]=P(X_2\lt X_1,\ Y_3\lt Y_1)$. Also, writing $A=\{X_2\lt X_1\}$ and $B=\{Y_3\lt Y_1\}$, the event $(X_1-X_2)(Y_1-Y_3)\gt0$ is $(A\cap B)\cup(A^c\cap B^c)$, so its probability is $$2P(A\cap B)+1-P(A)-P(B)=2E[F(X_1)G(Y_1)].$$ Now $(X_1-X_2,\ Y_1-Y_3)$ is bivariate normal with covariance $\rho$ and variances $2$, so its correlation is $\frac\rho2$ and the orthant formula gives $2E[FG]=2\left(\frac14+\frac{\arcsin(\rho/2)}{2\pi}\right)$. Hence $\rho_S=12E[FG]-3=\frac6\pi\arcsin\frac\rho2$. ∎
- State $H_0$: $X$ and $Y$ independent (continuous). Under $H_0$ the $y$-ranks, listed in $x$-order, form a uniform random permutation, so every rank statistic is distribution-free.
- Small $n$: exact $p$-values by counting permutations — Mahonian numbers for $\tau$, enumeration for $r_s$ (the check lab under Exercise card IV does this for $n\le9$).
- Large $n$: $z=\sqrt{n-1}\,r_s$ or $z=\tau\big/\sqrt{2(2n+5)/(9n(n-1))}$, compared with $N(0,1)$.
- Other tools: under bivariate normality, the Pearson test $t=r\sqrt{n-2}/\sqrt{1-r^2}\sim t_{n-2}$ (§7.2); for categorical data, the $\chi^2$ test of independence in a contingency table (§5.2).
- Remember: rank correlations detect monotone dependence only. A non-significant $r_s$ or $\tau$ never proves independence.
| problem | test | exact null law | large-sample form |
|---|---|---|---|
| one sample or pairs: median $=\theta_0$ | sign test, $S$ | $\operatorname{Bin}(n,\frac12)$ | $(S-\frac n2)/(\frac{\sqrt n}2)$ |
| one sample or pairs, symmetric law | signed rank, $T^+$ | subset sums of $\{1,\dots,n\}$ | mean $\frac{n(n+1)}4$, var $\frac{n(n+1)(2n+1)}{24}$ |
| two samples, shift in location | Mann–Whitney, $U$ or $W$ | arrangements, $c_{m,n}(u)$ | mean $\frac{mn}2$, var $\frac{mn(N+1)}{12}$ |
| two samples, quick and robust | median test, $A$ | hypergeometric | $\chi^2_1$ for the $2\times2$ table |
| randomness of a sequence | runs test, $R$ | Theorem 5.28 | mean $1+\frac{2mn}N$ |
| fit of a fully specified continuous $F_0$ | KS, $D_n$ | tables (distribution-free) | $\sqrt n\,D_n\to K$ |
| two samples, any difference | KS, $D_{m,n}$ | arrangements | $\sqrt{mn/N}\,D_{m,n}\to K$ |
| independence, monotone association | Spearman $r_s$, Kendall $\tau$ | permutations | $\sqrt{n-1}\,r_s$; $\operatorname{Var}\tau=\frac{2(2n+5)}{9n(n-1)}$ |
- The signed-rank test needs symmetry. For $Z=E-\log2$, $E\sim\operatorname{Exp}(1)$, the median is $0$ but $P(Z_1+Z_2\gt0)=0.597$, and the test rejects "median $0$" with probability tending to $1$ (Example 3(c)). The sign test needs no symmetry.
- Discreteness limits the level. With $n\le5$ no two-sided sign test at $5\%$ can reject; with $n=4$ the one-sided signed-rank test cannot reject at $5\%$ either ($P(T^+=10)=\frac1{16}$). "Exact" means exact size, not size $\alpha$.
- Mann–Whitney is not a test of equal medians, nor of equal spread. It reacts to $p=P(X\lt Y)\ne\frac12$. For $N(0,1)$ against $N(0,4)$, $p=\frac12$: equal medians, very different laws, and the power stays near $\alpha$ (about $6\%$ at $\alpha=5\%$ for large equal samples). Conversely two laws with equal medians can have $p\ne\frac12$, and Mann–Whitney will then reject.
- "Distribution-free" refers to the null distribution only. The power of every rank test depends on $F$ and $G$.
- KS with estimated parameters is not distribution-free. Testing normality with $\bar x$ and $s$ plugged into $F_0$ and using the KS table gives a far too conservative test (Example 6(c)).
- KS needs a continuous $F_0$. For a discrete $F_0$ (a Poisson model, say) the null law of $D_n$ is stochastically smaller and the usual table is conservative; use the $\chi^2$ test of §5.2.
- $D_n$ can never be small. $D_n\ge\frac1{2n}$ for every sample, with equality only when $U_{(i)}=\frac{2i-1}{2n}$.
- Too many runs is also evidence. The runs test is two-sided for randomness: $R$ far above $1+\frac{2mn}N$ means alternation (negative dependence). Only in the Wald–Wolfowitz two-sample test is the rejection region one-sided (small $R$).
- Zero rank correlation does not imply independence. $X\sim U(-1,1)$, $Y=X^2$ has $\tau=\rho_S=0$ (Example 7(b)); only for the bivariate normal do they characterise independence (Theorem 5.33).
- $r_s=1$ means monotone, not linear. $y=e^x$ on any data set of at least three distinct points gives $r_s=\tau=1$ while Pearson's $r\lt1$.
- Ties change null variances. With midranks the variance of $W$ or $T^+$ must be reduced by the tie correction; the exact null law must be recomputed conditionally on the tie pattern.
- Low efficiency is not low validity. The sign test is only $2/\pi$ as efficient as the $t$ test for normal data, but its size is exact for every continuous law — and for Laplace data it is twice as efficient as $t$.
Exercises
- 1 Of $15$ non-zero paired differences, $11$ are positive. Find the exact one-sided $p$-value of the sign test of "median difference $=0$" against "median difference $\gt0$", and its normal approximation with continuity correction.
- 2 What is the smallest $n$ for which a two-sided sign test at level $0.05$ can reject $H_0$? And a one-sided test?
- 3 For $n=20$, find the critical value $k$ of the one-sided sign test "reject if $S\ge k$" with size at most $0.05$, its exact size, and its power when $P(X\gt\theta_0)=0.75$.
- 4 For $n=10$ show that $[X_{(2)},X_{(9)}]$ is a confidence interval for the median with coverage $0.9785$, and that $[X_{(3)},X_{(8)}]$ has coverage below $0.95$.
- 5 Write down the complete null distribution of $T^+$ for $n=4$. Find $P(T^+\ge9)$ and check that the mean and variance agree with Theorem 5.23.
- 6 Nine paired differences are $0.8$, $-1.5$, $2.3$, $3.1$, $-0.4$, $1.9$, $2.7$, $4.2$, $1.2$. Compute $T^+$ and the exact one-sided $p$-value of the signed-rank test, and compare with the sign test.
- 7 Under the null hypothesis of Theorem 5.23, prove that $\operatorname{Cov}(S,T^+)=\frac{n(n+1)}8$ and that $\operatorname{Corr}(S,T^+)=\sqrt{\frac{3(n+1)}{2(2n+1)}}\to\frac{\sqrt3}{2}$.
- 8 For the data $1,3,4,10$ list the ten Walsh averages and find the Hodges–Lehmann estimate of the centre. Compare with the mean and the median.
- 9 Let $Z=E-\log2$ with $E\sim\operatorname{Exp}(1)$. Compute $E[T^+]$ for $n=20$ and explain why the signed-rank test is not a valid test of "median $=0$" without symmetry.
- 1 For $m=3$, $n=2$ list the $\binom52$ possible sets of $Y$-ranks and the null distribution of $W$. Verify $E[W]$ and $\operatorname{Var}(W)$ from Theorem 5.26.
- 2 Scores in group $A$ are $14,18,21,25,27,30$ and in group $B$ are $22,29,31,33,35,38$. Use the Mann–Whitney test (exact) to test $F_A=F_B$ against "$B$ tends to score higher".
- 3 With $m=20$, $n=25$ the rank sum of the $Y$'s is $W=640$. Find the approximate two-sided $p$-value.
- 4 Show that $U/(mn)$ is an unbiased estimator of $p=P(X\lt Y)$. Evaluate $p$ when $X\sim N(0,1)$, $Y\sim N(1,1)$, and when $X\sim\operatorname{Exp}(\text{mean }1)$, $Y\sim\operatorname{Exp}(\text{mean }2)$.
- 5 Use the recursion of Theorem 5.26 to find the null distribution of $U$ for $m=n=3$.
- 6 In a median test with $m=n=8$, six of the eight $Y$'s lie above the combined median. Find the exact one-sided $p$-value.
- 7 Give two continuous distributions $F\ne G$ with $P(X\lt Y)=\frac12$. What happens to the power of the Mann–Whitney test and of the two-sample KS test as $m=n\to\infty$?
- 8 (Ties) $X$: $2,3,3,5$; $Y$: $3,5,6,7$. Compute the midranks, $W$, the tie-corrected null variance of $W$ and the standardised statistic.
- 1 For $m=n=3$ list the distribution of the number of runs $R$ and check $E[R]$ and $\operatorname{Var}(R)$.
- 2 A student writes down a "random" sequence of $24$ coin tosses: HTHTHHTHTHTHTTHTHTHHTHTH. Apply the runs test.
- 3 Show that for $m=n$, $E[R]=n+1$ and $\operatorname{Var}(R)=\frac{n(n-1)}{2n-1}$.
- 4 Test whether $0.12,\ 0.31,\ 0.47,\ 0.83,\ 0.91$ come from $U(0,1)$: compute $D_5^+$, $D_5^-$ and $D_5$, and decide at $5\%$ (exact critical value $0.5633$).
- 5 For $n=1$ show that $P(D_1\le d)=2d-1$ for $\frac12\le d\le1$, and find the exact $5\%$ critical value.
- 6 Prove that $D_n\ge\frac1{2n}$ for every sample, with equality iff $U_{(i)}=\frac{2i-1}{2n}$ for all $i$.
- 7 Samples $X$: $1.1,2.4,3.0,3.8$ and $Y$: $2.9,4.1,4.6,5.2$. Compute $D_{4,4}$ and its exact $p$-value.
- 8 With $n=100$ and $D_{100}=0.15$, find the asymptotic $p$-value of the KS test and decide at $5\%$.
- 1 Listed in $x$-order, the $y$-ranks of six pairs are $3,1,2,6,4,5$. Compute $r_s$ and $\tau$.
- 2 Prove that $\sum d_i^2\le\frac{n(n^2-1)}{3}$, with equality iff $s_i=n+1-r_i$ for all $i$.
- 3 For $n=3$ list $r_s$ and $\tau$ for all six permutations, and verify $\operatorname{Var}(r_s)=\frac1{n-1}$ and $\operatorname{Var}(\tau)=\frac{2(2n+5)}{9n(n-1)}$.
- 4 For $n=30$ pairs, $r_s=0.42$ and $\tau=0.29$. Test independence (two-sided) with each statistic using the normal approximations.
- 5 For a bivariate normal pair with $\rho=0.5$, compute $\tau_{XY}$ and $\rho_S$.
- 6 Let $X$ be continuous and symmetric about $0$ and $Y=X^2$. Prove that $\tau_{XY}=\rho_S=0$.
- 7 Using the Mahonian numbers for $n=4$, find $P(\tau\ge\frac23)$ under independence, and the smallest $n$ for which a one-sided test based on $\tau$ can reject at $5\%$.
- 8 It is known that under independence $\operatorname{Corr}(r_s,\tau)=\frac{2(n+1)}{\sqrt{2n(2n+5)}}$. Verify this for $n=3$ from your table in part 3, and find its limit as $n\to\infty$.
- 9 Two examiners rank ten essays. In examiner A's order the ranks given by examiner B are $3,1,2,5,4,8,6,10,7,9$. Compute $r_s$ and $\tau$, and test independence against positive association (exactly — use the check lab — and approximately).
Type the paired values (commas or spaces). The lab ranks them (midranks if there are ties), computes $r_s$ and $\tau$, and for $n\le10$ without ties finds the exact one-sided $p$-values by running through all $n!$ permutations. Use it for Exercises IV.1, IV.9 and Example 7.
E1. CSIR Part B GATE ST Ten paired differences are all non-zero, and eight of them are positive. The exact $p$-value of the sign test of "median difference $=0$" against "median difference $\gt0$" is (A) $0.0107$ (B) $0.0547$ (C) $0.1094$ (D) $0.0439$.
E2. CSIR Part B Six letters $a$ and four letters $b$ are arranged in a row, all $\binom{10}{4}$ arrangements being equally likely. The expected number of runs is (A) $5$ (B) $5.8$ (C) $6$ (D) $4.8$.
E3. CSIR Part B GATE ST Two examiners rank five candidates. Listed in the first examiner's order, the second examiner's ranks are $2,1,3,5,4$. Kendall's $\tau$ and Spearman's $r_s$ are, respectively, (A) $0.6$ and $0.8$ (B) $0.8$ and $0.6$ (C) $0.6$ and $0.9$ (D) $0.7$ and $0.8$.
E4. CSIR Part C Let $Z_1,\dots,Z_n$ ($n\ge2$) be iid with a continuous distribution symmetric about $0$, let $S$ be the number of positive $Z_i$ and $T^+$ the Wilcoxon signed-rank statistic. Which of the following are true? (One or more options may be correct.) (A) $T^+$ and $\frac{n(n+1)}2-T^+$ have the same distribution. (B) $S$ and $T^+$ are independent. (C) $\operatorname{Var}(T^+)=\frac{n(n+1)(2n+1)}{24}$. (D) $P(T^+=1)=P(T^+=2)=2^{-n}$.
E5. CSIR Part C GATE ST Let $X_1,\dots,X_m$ iid $F$ and $Y_1,\dots,Y_n$ iid $G$ be independent with $F,G$ continuous, and $U=\#\{(i,j):X_i\lt Y_j\}$. Let $m,n\to\infty$ with $m/(m+n)\to\lambda\in(0,1)$. Which of the following are true? (A) If $F=G$, then $P(U=u)=P(U=mn-u)$ for every $u$. (B) If $F=G$, then $U/(mn)\to\frac12$ in probability. (C) If $F=N(0,1)$ and $G=N(0,4)$, the two-sided Mann–Whitney test at level $0.05$ has power tending to $1$. (D) For the same $F$ and $G$, the two-sample Kolmogorov–Smirnov test at level $0.05$ has power tending to $1$.
E6. CSIR Part C Let $X_1,\dots,X_n$ be iid $U(0,1)$ with empirical cdf $F_n$, and $D_n=\sup_x|F_n(x)-x|$. Which of the following are true? (A) $nF_n(\frac12)\sim\operatorname{Bin}(n,\frac12)$. (B) $D_n\ge\frac1{2n}$ with probability one. (C) If $Y_1,\dots,Y_n$ are iid $N(\mu,1)$ with $\mu$ unknown and $H_n$ is their empirical cdf, then $\sup_x|H_n(x)-\Phi(x-\bar Y)|$ has the same distribution as $D_n$. (D) $\sqrt n\,D_n$ converges in distribution to a normal law.
Suggested plan — 3 lectures × 60 min.
- Ranks, signs and one-sample tests. Theorem 5.20 (the permutation argument on the board — it is used for every later null distribution); the sign test (Theorems 5.21–5.22) with Example 1; the signed-rank statistic and Theorem 5.23, proving the representation $\sum kB_k$; Example 2. Project Interactive 1 in the sign and signed-rank modes with $n=4,5,6$ and ask the class when a $5\%$ test first becomes possible.
- Walsh averages, efficiency and two samples. Theorem 5.24 and Example 3 (the skewed counterexample is the key Part C trap); state Theorem 5.25 and discuss $3/\pi$. Then Definition 5.16, Theorem 5.26 with the full covariance count for $\operatorname{Var}(U)$, the median test, and Example 4. Use Interactive 1 in the Mann–Whitney mode to show the recursion's output and the approach to normality.
- Runs, KS and rank correlation. Theorem 5.28 by stars and bars (Example 5); the empirical cdf and Glivenko–Cantelli (Theorem 5.29); KS distribution-freeness via the probability integral transform (Theorem 5.30), Example 6 and Interactive 2 (first $H_0$ true, then the shift, then the spread alternative). Finish with Theorems 5.31–5.32 and Example 7, and Exam-corner E5–E6 done live.
Discussion questions. (1) The signed-rank test is "distribution-free", yet it can reject a true median with probability near $1$. Distribution-free over which family? (2) Why should the KS test be consistent against every alternative while Mann–Whitney is not — and why does that not make KS the better test? (3) If two judges' rankings have $r_s=0$, can we conclude they are using unrelated criteria?
Misconceptions to watch for. Treating the signed-rank test as valid without symmetry; reading "exact test" as "size exactly $\alpha$"; believing Mann–Whitney compares medians; plugging estimated parameters into the KS test; forgetting the initial run ($E[R]=1+\frac{2mn}N$, not $\frac{2mn}N$); confusing $\operatorname{Var}(r_s)=\frac1{n-1}$ with $\frac1n$; equating zero rank correlation with independence.
Suggested homework. I(1, 3, 6, 7, 9), II(2, 4, 6, 7, 8), III(2, 4, 6, 7), IV(2, 3, 6, 9); Exam corner E2, E4, E6.
Research question. A small clinical study records the change in a biomarker for $20$ patients. Should the analyst use the paired $t$ test, the sign test or the Wilcoxon signed-rank test — and how much does the answer depend on the shape of the distribution?
Why it matters. Regulatory guidelines in many countries ask trial statisticians to justify their choice of test, and biomarker changes are often heavy-tailed (a few patients respond dramatically). Pitman's efficiencies (Theorem 5.25) predict the answer for large samples; a simulation shows what happens at the sample sizes actually used.
What to do.
- Write a simulation (seeded) that draws $n=20$ observations from a distribution with centre $\theta$ and variance $1$: normal, Laplace, $t_3$ rescaled to variance $1$, and a contaminated normal ($95\%$ $N(0,1)$, $5\%$ $N(0,25)$, rescaled).
- For $\theta=0$ estimate the actual size of the three one-sided $5\%$ tests from $20\,000$ samples. Explain why the sign test's size is far below $5\%$ (look at the table after Theorem 5.23, or compute $P(\operatorname{Bin}(20,\frac12)\ge15)$).
- For $\theta=0.5$ estimate the power of each test, and compare the ratios with the efficiencies $2/\pi$, $3/\pi$, $2$, $1.5$, $1.62$, $1.90$ of Theorem 5.25.
- Repeat with a skewed population (for example a centred lognormal) at $\theta=0$ and record how often the signed-rank test rejects. Relate this to Example 3(c).
Tools: Python with numpy and scipy.stats (ttest_1samp, wilcoxon, binom), or R; Interactive 1 for the exact null distributions.
Hand in: A one-page table of sizes and powers with a recommendation for the trial, and a paragraph explaining the discrepancy between the small-sample results and the Pitman efficiencies.
Going further. Read about the Hodges–Lehmann bound $0.864$ and the density that attains it; look up normal-scores (van der Waerden) tests, whose efficiency relative to $t$ is never below $1$.
🧪 Self-check quiz
Q1. $X_1,\dots,X_n$ are iid continuous with median $\theta_0$, and $S=\#\{i:X_i\gt\theta_0\}$. The distribution of $S$ is
Q2. Under the null hypothesis, with $n=8$ non-zero differences, $E[T^+]$ for the Wilcoxon signed-rank statistic is
Q3. Against which alternative does the Mann–Whitney test have power close to its size even for very large samples?
Q4. Five pairs have rank differences with $\sum d_i^2=40$. Spearman's $r_s$ equals
Q5. The null distribution of the one-sample Kolmogorov–Smirnov statistic $D_n$ is the same for every hypothesised $F_0$ provided that