Chapter 5 · Testing of Hypotheses

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.

📘 Definition 5.13 — Distribution-free statistics, ranks and antiranks

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).

📐 Theorem 5.20 — The rank vector of an iid continuous sample

Let $X_1,\dots,X_N$ be iid with a continuous cdf $F$. Then:

  1. $P(X_i=X_j\text{ for some }i\ne j)=0$;
  2. the rank vector $R$ is uniformly distributed over the $N!$ permutations of $\{1,\dots,N\}$;
  3. $R$ is independent of the vector of order statistics $(X_{(1)},\dots,X_{(N)})$;
  4. 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.

📘 Definition 5.14 — The sign test

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.

📐 Theorem 5.21 — Exact null distribution, power and consistency of the sign test

In the setting of Definition 5.14 let $p=P(X_1\gt\theta_0)$.

  1. $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.
  2. 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$).
  3. (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$.
  4. 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.

📐 Theorem 5.22 — A distribution-free confidence interval for the median
Let $X_1,\dots,X_n$ be iid with a continuous cdf $F$ and a median $m$ (so $F(m)=\frac12$), and let $1\le k\le n/2$. Then $$P\left(X_{(k)}\le m\le X_{(n-k+1)}\right)=1-2\sum_{j=0}^{k-1}\binom nj2^{-n}.$$ The interval $[X_{(k)},X_{(n-k+1)}]$ consists exactly of the values $\theta_0$ that the two-sided sign test with rejection region $\{S\le k-1\}\cup\{S\ge n-k+1\}$ does not reject.

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$. ∎

✏️ Example 1 — A sign test on paired data
Twelve participants follow a diet for eight weeks. Their weight losses $d_i$ (before minus after, in kg) are $$1.8,\ -0.4,\ 2.6,\ 0.9,\ 3.1,\ -1.2,\ 1.5,\ 0.7,\ 2.2,\ 0.0,\ 1.1,\ 4.0.$$ Use the sign test to test $H_0$: the median loss is $0$, against the alternative that it is positive. Give the exact $p$-value, its normal approximation, and the two-sided $p$-value.
Zeros One difference is exactly $0$; it carries no sign information and is discarded, leaving $n=11$.
Statistic Nine of the eleven differences are positive, so $S=9$. Under $H_0$, $S\sim\operatorname{Bin}(11,\frac12)$ (Theorem 5.21), whatever the shape of the distribution of weight losses.
Exact $p$-value $$P(S\ge9)=\frac{\binom{11}{9}+\binom{11}{10}+\binom{11}{11}}{2^{11}}=\frac{55+11+1}{2048}=\frac{67}{2048}=0.0327.$$ At the $5\%$ level the one-sided test rejects $H_0$.
Normal approximation $E[S]=5.5$, $\operatorname{sd}(S)=\sqrt{11}/2=1.6583$. With the continuity correction, $z=\frac{9-0.5-5.5}{1.6583}=1.809$ and $1-\Phi(1.809)=0.0352$ — close to the exact value even for $n=11$.
Two-sided Doubling gives $0.0654$: a two-sided test at $5\%$ would not reject. Whether the alternative is one- or two-sided must be decided before seeing the data.

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.

📘 Definition 5.15 — The Wilcoxon signed-rank statistic

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.

📐 Theorem 5.23 — Null distribution of the signed-rank statistic

Let $Z_1,\dots,Z_n$ be iid with a continuous distribution symmetric about $0$. Then:

  1. 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|)$;
  2. $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)$;
  3. $E[T^+]=\dfrac{n(n+1)}{4}$ and $\operatorname{Var}(T^+)=\dfrac{n(n+1)(2n+1)}{24}$;
  4. $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)$;
  5. $\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$5678910111215
sign: reject if $S\le c$000111223
attained size0.03130.01560.00780.03520.01950.01070.03270.01930.0176
signed rank: reject if $T^+\le c$0235810131730
attained size0.03130.04690.03910.03910.04880.04200.04150.04610.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.

📐 Theorem 5.24 — The Walsh-average representation of $T^+$

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.

✏️ Example 2 — Signed ranks on the diet data
Apply the Wilcoxon signed-rank test to the eleven non-zero weight losses of Example 1, against the alternative of a positive centre. Compute the exact $p$-value and its normal approximation, and compare with the sign test.
Ranks The absolute values in increasing order are $0.4^-,\ 0.7,\ 0.9,\ 1.1,\ 1.2^-,\ 1.5,\ 1.8,\ 2.2,\ 2.6,\ 3.1,\ 4.0$ (a minus marks a negative difference), with ranks $1$ to $11$. The negative differences have ranks $1$ and $5$, so $T^-=6$ and $T^+=66-6=60$.
Exact $p$-value By Theorem 5.23, $P(T^+\ge60)=P(T^-\le6)$, and $T^-$ has the null law of the subset sums of $\{1,\dots,11\}$. Subsets with sum $\le6$: sum $0$: $\varnothing$; $1$: $\{1\}$; $2$: $\{2\}$; $3$: $\{3\},\{1,2\}$; $4$: $\{4\},\{1,3\}$; $5$: $\{5\},\{1,4\},\{2,3\}$; $6$: $\{6\},\{1,5\},\{2,4\},\{1,2,3\}$ — $14$ subsets. So $p=14/2048=0.0068$.
Normal approximation $E[T^+]=\frac{11\cdot12}4=33$, $\operatorname{Var}(T^+)=\frac{11\cdot12\cdot23}{24}=126.5$, $\operatorname{sd}=11.247$. With continuity correction $z=\frac{60-0.5-33}{11.247}=2.356$, $p\approx0.0092$.
Comparison The signed-rank $p$-value ($0.0068$) is about five times smaller than the sign test's ($0.0327$): the two negative differences are small in size, and only the signed-rank test notices. The price is the extra assumption that weight losses are symmetric about their median; the two-sided signed-rank $p$-value $0.0137$ is significant at $5\%$, while the two-sided sign test was not.
✏️ Example 3 — Prove or disprove: what the one-sample tests can do
Decide whether each statement is true. (a) With $n=5$ observations, no two-sided sign test at level $0.05$ can ever reject $H_0$. (b) With $n=5$, the one-sided signed-rank test at level $0.05$ can reject $H_0$. (c) If $Z_1,\dots,Z_n$ are iid continuous with median $0$, then $E[T^+]=\frac{n(n+1)}{4}$. (d) If the $X_i$ are iid Cauchy with centre $\theta$, the signed-rank test of $\theta=0$ has exactly the size read from its null distribution, whereas the one-sample $t$ test does not.
(a) True The most extreme outcomes $S=0$ and $S=5$ give two-sided $p$-value $2\cdot2^{-5}=0.0625\gt0.05$. A test with $n\le5$ and two-sided level $5\%$ has empty rejection region.
(b) True $P(T^+=15)=P(\text{all signs positive})=2^{-5}=0.03125\le0.05$, so "reject iff $T^+=15$" is a level-$5\%$ test (the first entry of the table above).
(c) False By Theorem 5.24, $E[T^+]=np_1+\binom n2p_2$ with $p_1=\frac12$, but $p_2$ need not be $\frac12$ without symmetry. Take $Z=E-\log2$ with $E\sim\operatorname{Exp}(1)$: the median of $E$ is $\log2$, so $Z$ has median $0$. Then $E_1+E_2\sim\operatorname{Gamma}(2,1)$ and $$p_2=P(E_1+E_2\gt2\log2)=e^{-2\log2}(1+2\log2)=\tfrac{1+2\log2}{4}=0.5966.$$ For $n=20$, $E[T^+]=10+190(0.5966)=123.3$, not $105$. Since $\operatorname{sd}(T^+)$ grows like $n^{3/2}$ while this bias grows like $n^2$, the signed-rank test rejects this true median with probability tending to $1$.
(d) True The Cauchy law is continuous and symmetric about $\theta$, so under $\theta=0$ Theorem 5.23 applies exactly. The $t$ statistic, by contrast, does not have a $t_{n-1}$ distribution (the population is not normal, and has no mean), so the nominal $t$ critical values do not give the stated size.

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.

📐 Theorem 5.25 — Pitman efficiency of the sign and Wilcoxon tests

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.

📘 Definition 5.16 — Rank-sum and Mann–Whitney statistics

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)$.

📐 Theorem 5.26 — Properties and null distribution of the rank-sum statistic

Let $X_1,\dots,X_m$ iid $F$ and $Y_1,\dots,Y_n$ iid $G$ be independent, with $F,G$ continuous.

  1. $W=U+\dfrac{n(n+1)}{2}$ (with probability one).
  2. For any $F,G$: $E[U]=mn\,p$, where $p=P(X_1\lt Y_1)$.
  3. 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$.
  4. 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$.
  5. 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$345678
reject if $U\le c$01471115
attained size0.05000.02860.04760.04650.04870.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.

📘 Definition 5.17 — The median test
Let $M$ be the median of the combined sample of $N$ observations and let $t$ be the number of observations in the combined sample that exceed $M$ ($t=N/2$ when $N$ is even and there are no ties). The median test statistic is $A=\#\{j:Y_j\gt M\}$, the number of $Y$'s above the combined median. It rejects $F=G$ in favour of "the $Y$'s tend to be larger" when $A$ is large, and in the other direction when $A$ is small.
📐 Theorem 5.27 — Null distribution of the median test
Under $H_0:F=G$ with $F$ continuous, $A$ is hypergeometric: $$P(A=a)=\frac{\binom na\binom m{t-a}}{\binom Nt},\qquad \max(0,t-m)\le a\le\min(n,t),$$ with $E[A]=\dfrac{nt}{N}$ and $\operatorname{Var}(A)=\dfrac{mn\,t(N-t)}{N^2(N-1)}$. The test is Fisher's exact test (§5.2) applied to the $2\times2$ table (sample $\times$ above/below $M$), and for large samples it is the $\chi^2$ test of homogeneity of §5.2 with one degree of freedom.

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. ∎

✏️ Example 4 — Recovery times: Mann–Whitney versus the median test
Recovery times (days) after a standard treatment ($X$) and a new treatment ($Y$) are $$X:\ 8.2,\ 10.5,\ 9.1,\ 12.0,\ 11.3\qquad Y:\ 6.4,\ 7.9,\ 9.0,\ 5.8,\ 8.7.$$ Test $H_0:F=G$ against the alternative that recovery under the new treatment tends to be faster, (a) by the Mann–Whitney–Wilcoxon test (exact and normal approximation) and (b) by the median test.
Combined ordering $5.8_y,\ 6.4_y,\ 7.9_y,\ 8.2_x,\ 8.7_y,\ 9.0_y,\ 9.1_x,\ 10.5_x,\ 11.3_x,\ 12.0_x$. The $Y$'s have ranks $1,2,3,5,6$, so $W=17$. Counting $X$'s below each $Y$: $0,0,0,1,1$, so $U=2$; indeed $W=U+\frac{5\cdot6}2=17$.
(a) Exact $p$-value Small $U$ supports the alternative. By Theorem 5.26, $P(U\le2)=\frac{c_{5,5}(0)+c_{5,5}(1)+c_{5,5}(2)}{\binom{10}5}$. $U=0$: all $y$'s first ($1$ way); $U=1$: one $x$ before exactly one $y$ ($yyyyxyxxxx$, $1$ way); $U=2$: $yyyxyyxxxx$ or $yyyyxxyxxx$ ($2$ ways). So $p=\frac{4}{252}=0.0159$, significant at $5\%$ (compare the table: $U\le4$ is the $5\%$ region for $m=n=5$).
Normal approximation $E[W]=\frac{5\cdot11}2=27.5$, $\operatorname{Var}(W)=\frac{5\cdot5\cdot11}{12}=22.917$, $\operatorname{sd}=4.787$. With continuity correction $z=\frac{17+0.5-27.5}{4.787}=-2.089$, $p\approx\Phi(-2.089)=0.0184$.
(b) Median test The combined median is $M=\frac{8.7+9.0}2=8.85$, $t=5$, and only one $Y$ (namely $9.0$) exceeds it: $A=1$. Under $H_0$, $A$ is hypergeometric with $N=10$, $n=t=5$: $$P(A\le1)=\frac{\binom50\binom55+\binom51\binom54}{252}=\frac{1+25}{252}=0.1032.$$ The median test does not reject at $5\%$.
Lesson Both tests are exact and distribution-free, but the median test reduces each observation to one bit (above/below $M$) and so has much lower power; its Pitman efficiency relative to Mann–Whitney is $2/3$ for normal data.
Interactive 1 — Exact Null Distributions of Rank Statistics

Each bar is an exact null probability, obtained by counting equally likely signs, subsets, arrangements or permutations; the curve is the normal law with the exact null mean and variance. Red bars form the largest rejection region whose exact size does not exceed $\alpha$. Press Play to let $n$ grow and watch the histogram turn bell-shaped; for small $n$ notice how far the attained size can fall below $\alpha$, and that sometimes no region is possible at all.

85
null mean; variance—
rejection region—
exact size—
normal approx. of that size—
smallest possible p-value—

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.

📘 Definition 5.18 — Runs and the runs test

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.
📐 Theorem 5.28 — The distribution of the number of runs

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.

✏️ Example 5 — Is the production line random?
Twenty successive shafts from a lathe are measured and coded $a$ (diameter above the sample median) or $b$ (below): $$a\,a\,a\,a\ \ b\,b\,b\ \ a\,a\,a\ \ b\,b\,b\,b\,b\ \ a\,a\,a\ \ b\,b$$ Test the hypothesis of randomness by the runs test, exactly and by the normal approximation.
Count $m=n=10$ (coding about the median always splits the sample evenly) and the runs are $aaaa,\ bbb,\ aaa,\ bbbbb,\ aaa,\ bb$: $R=6$.
Exact tail $\binom{20}{10}=184756$. Theorem 5.28 with $m-1=n-1=9$: $R=2$: $2$; $R=3$: $2\binom91\binom90=18$; $R=4$: $2\binom91^2=162$; $R=5$: $2\binom92\binom91=648$; $R=6$: $2\binom92^2=2592$. So $$P(R\le6)=\frac{2+18+162+648+2592}{184756}=\frac{3422}{184756}=0.0185.$$ The two-sided $p$-value is $0.0370$: randomness is rejected at $5\%$.
Normal approximation $E[R]=1+\frac{2\cdot100}{20}=11$, $\operatorname{Var}(R)=\frac{2\cdot100\cdot180}{400\cdot19}=4.737$, $\operatorname{sd}=2.176$. With continuity correction $z=\frac{6+0.5-11}{2.176}=-2.068$, one-sided $p\approx0.0193$, two-sided $\approx0.039$.
Interpretation Too few runs: large and small diameters come in clusters, as they would if the tool drifts and is periodically reset. Too many runs would also be suspicious (systematic over-correction).

The tests above use ranks or signs. The Kolmogorov–Smirnov tests use the whole empirical distribution function, the natural nonparametric estimate of $F$.

📘 Definition 5.19 — Empirical distribution function and Kolmogorov–Smirnov statistics

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}$.

📐 Theorem 5.29 — The empirical distribution function and the Glivenko–Cantelli theorem

Let $X_1,\dots,X_n$ be iid with cdf $F$.

  1. 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)$.
  2. For $x\le y$, $\operatorname{Cov}(F_n(x),F_n(y))=\frac{F(x)(1-F(y))}{n}$.
  3. (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$. ∎

📐 Theorem 5.30 — Kolmogorov–Smirnov statistics are distribution-free

Let $F_0$ be continuous, let $X_1,\dots,X_n$ be iid $F_0$, and put $U_{(i)}=F_0(X_{(i)})$.

  1. $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$.
  2. 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^-)$.
  3. (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}$.
  4. 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.
  5. 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$).

✏️ Example 6 — Kolmogorov–Smirnov tests, one and two samples
(a) The times (minutes) between eight successive requests to a server are $0.3,\ 0.6,\ 1.1,\ 1.4,\ 2.0,\ 2.9,\ 4.4,\ 6.5$. Test $H_0$: the times are iid exponential with mean $1$ minute. (b) Apply the two-sample KS test to the recovery times of Example 4. (c) A colleague estimates the mean by $\bar x=2.4$ and tests $\operatorname{Exp}(\text{mean }2.4)$ with the same critical value. What is wrong?
(a) Transform $F_0(x)=1-e^{-x}$ gives $u_{(i)}=0.2592,\ 0.4512,\ 0.6671,\ 0.7534,\ 0.8647,\ 0.9450,\ 0.9877,\ 0.9985$.
Statistics $\frac i8-u_{(i)}$: $-0.134,\ -0.201,\ -0.292,\ -0.253,\ -0.240,\ -0.195,\ -0.113,\ 0.0015$, so $D_8^+=0.0015$. $u_{(i)}-\frac{i-1}8$: $0.259,\ 0.326,\ 0.417,\ 0.378,\ 0.365,\ 0.320,\ 0.238,\ 0.123$, so $D_8^-=0.4171$, attained just before $x=1.1$. Thus $D_8=0.4171$.
Decision The exact $5\%$ critical value for $n=8$ is $0.4543$, so $H_0$ is not rejected at $5\%$; the exact $p$-value is $0.0895$ (rejected at $10\%$). The modified asymptotic formula gives $(\sqrt8+0.12+0.11/\sqrt8)(0.4171)=1.246$ and $1-K(1.246)=0.0896$. The sign of the largest deviation ($F_0\gt F_8$) says the data are stochastically larger than $\operatorname{Exp}(1)$.
(b) Two samples With $F_5$ for $X$ and $G_5$ for $Y$ in the combined ordering of Example 4, $G_5-F_5$ takes the values $0.2,0.4,0.6,0.4,0.6,0.8,0.6,0.4,0.2,0$ after successive observations, so $D_{5,5}=0.8$ (after $9.0$). By Theorem 5.30(5) with $n=5$, $k=4$: $P(D_{5,5}\ge0.8)=\frac{2\binom{10}{1}}{252}=0.0794$. The KS test does not reject at $5\%$, although Mann–Whitney did ($p=0.0159$ one-sided, $0.0317$ two-sided): KS guards against every kind of difference and pays for it against pure shifts.
(c) Estimated parameters Theorem 5.30 requires $F_0$ to be fixed in advance. Fitting the mean makes $F_0$ follow the data, so $D_n$ is systematically smaller than under a fixed $F_0$; the usual critical values are then far too large and the test is very conservative. Corrected tables (Lilliefors-type, obtained by simulation) are needed.
Interactive 2 — The Kolmogorov–Smirnov Test at Work

A sample of size $n$ is drawn (seeded random numbers) from the chosen distribution and its empirical cdf (blue steps) is compared with $F_0=\Phi$, the standard normal cdf (black). The green band is $\Phi\pm c$, where $c$ is the $5\%$ critical value: $H_0$ is rejected exactly when the steps leave the band. The red segment marks $D_n$. Press Play to draw sample after sample and watch the rejection rate settle near $5\%$ when $H_0$ is true, and climb towards $100\%$ under the alternatives as $n$ grows.

30
Dₙ (where)—
5% critical value c—
p-value (approx.)—
rejections so far—

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.

📘 Definition 5.20 — Spearman's and Kendall's rank correlations

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$.

📐 Theorem 5.31 — Properties of Spearman's coefficient
  1. $r_s=1-\dfrac{6\sum_{i=1}^{n}d_i^2}{n(n^2-1)}$.
  2. $-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$.
  3. 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). ∎

📐 Theorem 5.32 — Properties of Kendall's tau
  1. 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)$).
  2. $-1\le\tau\le1$, with $\tau=1$ iff $\pi$ is the identity and $\tau=-1$ iff $\pi$ is the reversal.
  3. 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$.

📐 Theorem 5.33 — Rank correlations of the bivariate normal
If $(X,Y)$ is bivariate normal with correlation $\rho$, then $$\tau_{XY}=\frac2\pi\arcsin\rho,\qquad\rho_S=\frac6\pi\arcsin\frac\rho2.$$ In particular $\tau_{XY}=\rho_S=0$ iff $\rho=0$ iff $X$ and $Y$ are independent; for $\rho=0.5$, $\tau=\frac13$ and $\rho_S=0.4826$.

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$. ∎

🧭 Problem-solving strategy — testing independence
  1. 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.
  2. 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$).
  3. Large $n$: $z=\sqrt{n-1}\,r_s$ or $z=\tau\big/\sqrt{2(2n+5)/(9n(n-1))}$, compared with $N(0,1)$.
  4. 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).
  5. Remember: rank correlations detect monotone dependence only. A non-significant $r_s$ or $\tau$ never proves independence.
✏️ Example 7 — Two wine judges, and a dependent pair with zero rank correlation
(a) Two judges rank eight wines. Listing the wines in judge A's order $1,2,\dots,8$, judge B's ranks are $2,1,4,3,6,8,5,7$. Compute $r_s$ and $\tau$ and test independence against positive association, exactly and by the normal approximations. (b) Let $X\sim U(-1,1)$ and $Y=X^2$. Show that $\tau_{XY}=\rho_S=0$ although $Y$ is a function of $X$.
(a) Spearman $d=-1,1,-1,1,-1,-2,2,1$ and $\sum d_i^2=14$, so $r_s=1-\frac{6\cdot14}{8\cdot63}=1-\frac16=0.8333$.
(a) Kendall The inversions of $(2,1,4,3,6,8,5,7)$ are $(2,1),(4,3),(6,5),(8,5),(8,7)$: $D=5$, $C=28-5=23$, and $\tau=\frac{23-5}{28}=0.6429$.
(a) Exact $p$-values Of the $8!=40320$ permutations, $310$ have $\sum d_i^2\le14$, so $P(r_s\ge0.8333)=0.0077$. The Mahonian numbers for $n=8$ begin $1,7,27,76,174,343$, so $P(D\le5)=\frac{628}{40320}=0.0156$. Both tests reject independence at $5\%$.
(a) Normal approximations $\sqrt7\,r_s=2.205$, $p\approx0.0137$. $\operatorname{sd}(\tau)=\sqrt{\frac{2\cdot21}{9\cdot56}}=0.2887$, $z=2.227$, $p\approx0.0130$. At $n=8$ the approximation is rough for $r_s$; use exact values when you can.
(b) Kendall For independent copies, $(X_1-X_2)(Y_1-Y_2)=(X_1-X_2)^2(X_1+X_2)$, whose sign is that of $X_1+X_2$, a continuous variable symmetric about $0$. So concordance and discordance each have probability $\frac12$ and $\tau_{XY}=0$.
(b) Spearman $F(X)=\frac{X+1}2$, and $P(Y\le y)=P(|X|\le\sqrt y)=\sqrt y$, so $G(Y)=|X|$. Then $E[F(X)G(Y)]=E\left[\frac{(X+1)|X|}{2}\right]=\frac12E|X|=\frac14$ (as $E[X|X|]=0$), and $\rho_S=12\cdot\frac14-3=0$. Rank correlations measure monotone association; a U-shaped dependence is invisible to them.
🧭 Problem-solving strategy — which nonparametric test?
problemtestexact null lawlarge-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 lawsigned 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 locationMann–Whitney, $U$ or $W$arrangements, $c_{m,n}(u)$mean $\frac{mn}2$, var $\frac{mn(N+1)}{12}$
two samples, quick and robustmedian test, $A$hypergeometric$\chi^2_1$ for the $2\times2$ table
randomness of a sequenceruns test, $R$Theorem 5.28mean $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 differenceKS, $D_{m,n}$arrangements$\sqrt{mn/N}\,D_{m,n}\to K$
independence, monotone associationSpearman $r_s$, Kendall $\tau$permutations$\sqrt{n-1}\,r_s$; $\operatorname{Var}\tau=\frac{2(2n+5)}{9n(n-1)}$
⚠️ Counterexamples and pitfalls
  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.
  2. 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$.
  3. 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.
  4. "Distribution-free" refers to the null distribution only. The power of every rank test depends on $F$ and $G$.
  5. 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)).
  6. 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.
  7. $D_n$ can never be small. $D_n\ge\frac1{2n}$ for every sample, with equality only when $U_{(i)}=\frac{2i-1}{2n}$.
  8. 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$).
  9. 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).
  10. $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$.
  11. 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.
  12. 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

I
One-sample and paired tests: sign and signed-rank.
  • 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 $P(S\ge11)=\frac{\binom{15}{11}+\binom{15}{12}+\binom{15}{13}+\binom{15}{14}+\binom{15}{15}}{2^{15}}=\frac{1365+455+105+15+1}{32768}=\frac{1941}{32768}=0.0592$. Normal: $z=\frac{11-0.5-7.5}{\sqrt{3.75}}=1.549$, $p\approx0.0607$. Not significant at $5\%$.
2 The smallest two-sided $p$-value is $2\cdot2^{-n}$, which is $\le0.05$ iff $2^n\ge40$, i.e. $n\ge6$ ($2/64=0.031$). One-sided: $2^{-n}\le0.05$ iff $n\ge5$.
3 $P(\operatorname{Bin}(20,\frac12)\ge14)=0.0577\gt0.05$ and $P(\ge15)=0.0207$, so $k=15$ with exact size $0.0207$. Power: $P(\operatorname{Bin}(20,0.75)\ge15)=0.6172$.
4 By Theorem 5.22 the coverage is $1-2P(\operatorname{Bin}(10,\frac12)\le k-1)$: for $k=2$, $1-2\cdot\frac{11}{1024}=0.9785$; for $k=3$, $1-2\cdot\frac{56}{1024}=0.8906\lt0.95$.
5 Subset sums of $\{1,2,3,4\}$: for $t=0,1,\dots,10$ the counts are $1,1,1,2,2,2,2,2,1,1,1$ (out of $16$). $P(T^+\ge9)=\frac{2}{16}=0.125$. Mean $=\frac{1}{16}\sum t\,c(t)=5=\frac{4\cdot5}4$; $E[(T^+)^2]=\frac{520}{16}=32.5$, so the variance is $7.5=\frac{4\cdot5\cdot9}{24}$.
6 Absolute values in order: $0.4^-,0.8,1.2,1.5^-,1.9,2.3,2.7,3.1,4.2$. $T^-=1+4=5$, $T^+=45-5=40$. Subsets of $\{1,\dots,9\}$ with sum $\le5$: $1+1+1+2+2+3=10$, so $p=\frac{10}{512}=0.0195$: significant at $5\%$. Sign test: $S=7$, $P(S\ge7)=\frac{36+9+1}{512}=0.0898$: not significant.
7 In the representation of Theorem 5.23, $S=\sum B_k$ and $T^+=\sum kB_k$ (the same signs, listed by absolute rank). So $\operatorname{Cov}(S,T^+)=\sum_k k\operatorname{Var}(B_k)=\frac14\cdot\frac{n(n+1)}2=\frac{n(n+1)}8$. With $\operatorname{Var}(S)=\frac n4$ and $\operatorname{Var}(T^+)=\frac{n(n+1)(2n+1)}{24}$, $$\operatorname{Corr}=\frac{n(n+1)/8}{\sqrt{\frac n4\cdot\frac{n(n+1)(2n+1)}{24}}}=\sqrt{\frac{3(n+1)}{2(2n+1)}}\to\frac{\sqrt3}2.$$
8 Walsh averages: $1,3,4,10$ and $2,2.5,5.5,3.5,6.5,7$. Sorted: $1,2,2.5,3,3.5,4,5.5,6.5,7,10$; the median is $\frac{3.5+4}2=3.75$. The mean $4.5$ is pulled up by the outlier $10$; the median is $3.5$.
9 By Example 3(c), $p_1=\frac12$ and $p_2=\frac{1+2\log2}4=0.5966$, so $E[T^+]=20\cdot\frac12+190\cdot0.5966=123.3$ against the null value $105$. In general $E[T^+]-\frac{n(n+1)}4=\binom n2\left(p_2-\frac12\right)$ grows like $n^2$ while $\operatorname{sd}(T^+)$ grows like $n^{3/2}$, so the probability of rejecting the true median tends to $1$. The signed-rank test is a test of symmetry about $\theta_0$, and it is a location test only under the symmetry assumption.
II
Two-sample rank tests.
  • 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 The ten 2-subsets of $\{1,\dots,5\}$ have sums $3,4,5,5,6,6,7,7,8,9$, so $P(W=w)=\frac1{10},\frac1{10},\frac2{10},\frac2{10},\frac2{10},\frac1{10},\frac1{10}$ for $w=3,\dots,9$. $E[W]=6=\frac{2\cdot6}2$ and $E[W^2]=39$, so $\operatorname{Var}(W)=3=\frac{3\cdot2\cdot6}{12}$.
2 Combined ranks of $B$: $22\to4$, $29\to7$, $31\to9$, $33\to10$, $35\to11$, $38\to12$, so $W_B=53$. The number of pairs with a $B$ score below an $A$ score is $3+1=4$ ($22$ is below $25,27,30$; $29$ below $30$). Under $H_0$ this count has the law of $U$ for $m=n=6$, with counts $1,1,2,3,5$ for $u=0,\dots,4$: $p=\frac{12}{924}=0.0130$. Reject at $5\%$.
3 $E[W]=\frac{25\cdot46}2=575$, $\operatorname{Var}(W)=\frac{20\cdot25\cdot46}{12}=1916.7$, $\operatorname{sd}=43.78$. $z=\frac{640-0.5-575}{43.78}=1.473$, two-sided $p\approx0.141$. Not significant.
4 $E[U]=mn\,p$ by Theorem 5.26(2). For the normals, $Y-X\sim N(1,2)$ and $p=\Phi(1/\sqrt2)=0.7602$. For the exponentials with rates $1$ and $\frac12$, $p=P(X\lt Y)=\frac{1}{1+1/2}=\frac23$.
5 Building up from $c_{a,0}=c_{0,b}=[1]$ gives, for $u=0,\dots,9$, the counts $1,1,2,3,3,3,3,2,1,1$ (total $20=\binom63$). Mean $4.5$, variance $\frac{9\cdot7}{12}=5.25$.
6 $t=8$, $N=16$: $P(A\ge6)=\frac{\binom86\binom82+\binom87\binom81+\binom88\binom80}{\binom{16}8}=\frac{784+64+1}{12870}=0.0660$. Not significant at $5\%$.
7 $F=N(0,1)$, $G=N(0,4)$: $Y-X\sim N(0,5)$ is symmetric, so $p=\frac12$ (similarly $U(-1,1)$ against $U(-2,2)$). Mann–Whitney: $U/mn\to\frac12$, the statistic stays centred and its power converges to a constant below $1$ (about $0.06$ at $\alpha=0.05$ here) — not consistent. KS: $D_{m,n}\to\sup|F-G|\gt0$ while the critical values are of order $N^{-1/2}$, so its power tends to $1$.
8 Sorted: $2_x$ (rank $1$), $3_x,3_x,3_y$ (ranks $2$–$4$, midrank $3$), $5_x,5_y$ (midrank $5.5$), $6_y$ ($7$), $7_y$ ($8$). $W=3+5.5+7+8=23.5$, $E[W]=18$. Tie groups of sizes $3$ and $2$ give $\sum(t^3-t)=24+6=30$, so $\operatorname{Var}(W)=\frac{16}{12}\left(9-\frac{30}{56}\right)=11.286$ (instead of $12$), and $z=\frac{5.5}{3.359}=1.637$.
III
Runs and Kolmogorov–Smirnov.
  • 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 $\binom63=20$ arrangements; Theorem 5.28 gives $P(R=2,3,4,5,6)=\frac2{20},\frac4{20},\frac8{20},\frac4{20},\frac2{20}$. $E[R]=\frac{80}{20}=4=1+\frac{18}6$; $E[R^2]=17.2$, so $\operatorname{Var}(R)=1.2=\frac{2\cdot9\cdot12}{36\cdot5}$.
2 $13$ H, $11$ T, $R=21$ runs. $E[R]=1+\frac{2\cdot143}{24}=12.92$, $\operatorname{Var}(R)=\frac{286(286-24)}{576\cdot23}=5.656$, $\operatorname{sd}=2.378$. $z=\frac{21-0.5-12.92}{2.378}=3.19$; exactly, $P(R\ge21)=0.0004$, so the two-sided $p$-value is about $0.0008$. Randomness is rejected: the sequence alternates far too often, as human-made "random" sequences usually do.
3 With $m=n$, $N=2n$: $E[R]=1+\frac{2n^2}{2n}=n+1$ and $\operatorname{Var}(R)=\frac{2n^2(2n^2-2n)}{4n^2(2n-1)}=\frac{n(n-1)}{2n-1}$.
4 $\frac i5-u_{(i)}$: $0.08,0.09,0.13,-0.03,0.09$, so $D^+=0.13$. $u_{(i)}-\frac{i-1}5$: $0.12,0.11,0.07,0.23,0.11$, so $D^-=0.23$ and $D_5=0.23\lt0.5633$: do not reject.
5 With one observation $U$, $F_1$ jumps from $0$ to $1$ at $U$, so $D_1=\max(U,1-U)$. For $\frac12\le d\le1$, $P(D_1\le d)=P(1-d\le U\le d)=2d-1$. The $5\%$ point solves $2d-1=0.95$: $d=0.975$.
6 By Theorem 5.30(2), $D_n\ge\max\left(\frac in-U_{(i)},\ U_{(i)}-\frac{i-1}n\right)$ for each $i$, and the two terms add up to $\frac1n$, so the larger is $\ge\frac1{2n}$. Equality for $D_n$ requires both terms to equal $\frac1{2n}$ for every $i$, i.e. $U_{(i)}=\frac{2i-1}{2n}$; conversely these values give all terms $\frac1{2n}$.
7 Combined: $1.1_x,2.4_x,2.9_y,3.0_x,3.8_x,4.1_y,4.6_y,5.2_y$. $F_4-G_4$ after each: $\frac14,\frac24,\frac14,\frac24,\frac34,\frac24,\frac14,0$, so $D_{4,4}=\frac34$. By Theorem 5.30(5) with $k=3$: $P(D_{4,4}\ge\frac34)=\frac{2\binom81}{\binom84}=\frac{16}{70}=0.229$. Not significant.
8 $\sqrt{100}\cdot0.15=1.5$ and $1-K(1.5)=2(e^{-4.5}-e^{-18}+\cdots)=0.0222$. Reject at $5\%$ (the asymptotic critical value is $0.1358$; the exact one is $0.1340$ and the exact $p$-value $0.0198$).
IV
Rank correlation, independence and proofs.
  • 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).
Check lab: Spearman and Kendall with exact p-values

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.

n; Σd²; discordant pairs—
Spearman r_s; exact p; normal p—
Kendall τ; exact p; normal p—
1 $d=-2,1,1,-2,1,1$, $\sum d^2=12$, $r_s=1-\frac{72}{210}=0.6571$. Inversions: $(3,1),(3,2),(6,4),(6,5)$, $D=4$, $\tau=1-\frac{16}{30}=0.4667$.
2 By Theorem 5.31(1), $\sum d_i^2=\frac{n(n^2-1)}6(1-r_s)$, and $r_s\ge-1$ gives $\sum d_i^2\le\frac{n(n^2-1)}{3}$, with equality iff $r_s=-1$ iff $s_i=n+1-r_i$ (Theorem 5.31(2)).
3 $(1,2,3)$: $r_s=1$, $\tau=1$; $(1,3,2)$ and $(2,1,3)$: $\frac12$, $\frac13$; $(2,3,1)$ and $(3,1,2)$: $-\frac12$, $-\frac13$; $(3,2,1)$: $-1$, $-1$. Means $0$; $\operatorname{Var}(r_s)=\frac{1+4\cdot\frac14+1}{6}=\frac12=\frac1{n-1}$; $\operatorname{Var}(\tau)=\frac{2+4\cdot\frac19}{6}=\frac{11}{27}=\frac{2\cdot11}{9\cdot3\cdot2}$.
4 $z=0.42\sqrt{29}=2.262$, $p\approx0.024$. $\operatorname{sd}(\tau)=\sqrt{\frac{2\cdot65}{9\cdot30\cdot29}}=0.1289$, $z=2.251$, $p\approx0.024$. Both reject independence at $5\%$.
5 $\tau=\frac2\pi\arcsin\frac12=\frac2\pi\cdot\frac\pi6=\frac13$; $\rho_S=\frac6\pi\arcsin\frac14=0.4826$, slightly below $\rho=0.5$.
6 For independent copies, $(X_1-X_2)(X_1^2-X_2^2)=(X_1-X_2)^2(X_1+X_2)$ has the sign of $X_1+X_2$, which is continuous and symmetric about $0$; so $P(\text{conc})=P(\text{disc})=\frac12$ and $\tau=0$. For $\rho_S$: with $X'$ an independent copy of $X$, $G(Y)=h(|X|)$ where $h(t)=P(|X'|\le t)$; and $F(-x)=1-F(x)$ by symmetry. Since $X$ and $-X$ have the same law, $E[F(X)h(|X|)]=E[F(-X)h(|X|)]=E[h(|X|)]-E[F(X)h(|X|)]$, so $E[F(X)G(Y)]=\frac12E[G(Y)]=\frac14$ and $\rho_S=12\cdot\frac14-3=0$.
7 $\tau\ge\frac23$ iff $D\le1$: $P=\frac{1+3}{24}=0.1667$. A one-sided $5\%$ test needs the most extreme value to have probability $\frac1{n!}\le0.05$: $n=3$ gives $\frac16$, $n=4$ gives $\frac1{24}=0.042$. So $n=4$ (rejecting only when $\tau=1$).
8 From the table, $E[r_s\tau]=\frac{1+4\cdot\frac16+1}{6}=\frac49$, so $\operatorname{Corr}=\frac{4/9}{\sqrt{\frac12\cdot\frac{11}{27}}}=0.9847$, and the formula gives $\frac{8}{\sqrt{66}}=0.9847$. The limit is $\frac{2n}{\sqrt{4n^2}}=1$: for large $n$ the two tests are almost the same test (and have the same Pitman efficiency).
9 $d=-2,1,1,-1,1,-2,1,-2,2,1$, $\sum d^2=22$, $r_s=1-\frac{132}{990}=0.8667$. Inversions: $(3,1),(3,2),(5,4),(8,6),(8,7),(10,7),(10,9)$, $D=7$, $\tau=1-\frac{28}{90}=0.6889$. Exact one-sided $p$-values: $P(r_s\ge0.8667)=\frac{3943}{3628800}=0.0011$ and $P(D\le7)=0.0023$. Normal: $z_s=3(0.8667)=2.60$, $p\approx0.0047$; $z_\tau=\frac{0.6889}{0.2485}=2.77$, $p\approx0.0028$. Strong evidence of agreement.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

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$.

Idea Under $H_0$, $S\sim\operatorname{Bin}(10,\frac12)$; the $p$-value is $P(S\ge8)$.
Compute $\frac{\binom{10}8+\binom{10}9+\binom{10}{10}}{1024}=\frac{45+10+1}{1024}=\frac{56}{1024}=0.0547$. The distractors are $P(S\ge9)=\frac{11}{1024}$, the two-sided value $\frac{112}{1024}$ and $P(S=8)=\frac{45}{1024}$.
Answer (B).

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$.

Idea $R=1+$ (number of adjacent positions that differ), and each of the $9$ adjacent pairs differs with probability $\frac{2\cdot6\cdot4}{10\cdot9}$.
Compute $E[R]=1+\frac{2mn}{N}=1+\frac{48}{10}=5.8$. Option (D) forgets the initial run.
Answer (B).

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$.

Kendall The inversions are $(2,1)$ and $(5,4)$: $D=2$ of $\binom52=10$ pairs, $\tau=\frac{8-2}{10}=0.6$.
Spearman $d=-1,1,0,-1,1$, $\sum d^2=4$, $r_s=1-\frac{24}{120}=0.8$.
Answer (A).

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}$.

(A) True $\frac{n(n+1)}2-T^+=T^-$, and $T^-$ has the law of $T^+$ (flip all signs; Theorem 5.23(4)).
(B) False $S=\sum B_k$, $T^+=\sum kB_k$ give $\operatorname{Cov}(S,T^+)=\frac{n(n+1)}8\gt0$ (Exercise I.7). Concretely, $P(S=0)=2^{-n}$ but $P(S=0\mid T^+=0)=1$.
(C) True $\operatorname{Var}\left(\sum kB_k\right)=\frac14\sum k^2$.
(D) True $T^+=1$ only for the positive set $\{1\}$ and $T^+=2$ only for $\{2\}$ (as $n\ge2$); each sign pattern has probability $2^{-n}$.
Answer (A), (C) and (D).

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$.

(A) True Reversing the combined arrangement is a bijection of equally likely arrangements that maps $U$ to $mn-U$ (Theorem 5.26(4)).
(B) True $E[U/mn]=\frac12$ and $\operatorname{Var}(U/mn)=\frac{m+n+1}{12mn}\to0$; apply Chebyshev's inequality.
(C) False $Y-X\sim N(0,5)$, so $P(X\lt Y)=\frac12$: $U/mn\to\frac12$ under this alternative too, and the power converges to a limit below $1$ (about $0.06$ when $m=n$), not to $1$ (Theorem 5.26(5)).
(D) True $D_{m,n}\to\sup_x|\Phi(x)-\Phi(x/2)|\gt0$ almost surely, while the critical values are $O(N^{-1/2})$ (Theorem 5.30).
Answer (A), (B) and (D).

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.

(A) True $nF_n(\frac12)$ counts the $X_i\le\frac12$, each independently with probability $\frac12$ (Theorem 5.29(1)).
(B) True The two terms $\frac in-U_{(i)}$ and $U_{(i)}-\frac{i-1}n$ add up to $\frac1n$ (Exercise III.6).
(C) False Estimating $\mu$ destroys distribution-freeness. Already for $n=1$: $Y_1-\bar Y=0$, so the statistic is $\sup_x|\mathbf 1\{x\ge0\}-\Phi(x)|=\frac12$ always, whereas $D_1=\max(U,1-U)$ is uniform on $[\frac12,1]$.
(D) False The limit is Kolmogorov's law $K(x)=1-2\sum(-1)^{k-1}e^{-2k^2x^2}$, concentrated on $(0,\infty)$ — not normal ($\sqrt n\,D_n\ge0$ always).
Answer (A) and (B).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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).
  2. 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)$).
  3. 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.
  4. 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$.

Instructor note: with $n=20$ and $20\,000$ replications one finds approximately: sizes $t\approx0.05$, Wilcoxon $\approx0.05$, sign $\approx0.021$ (the attained size of the exact test). Powers at $\theta=0.5$: normal — $t\ 0.69$, Wilcoxon $0.69$, sign $0.38$; Laplace — $t\ 0.72$, Wilcoxon $0.78$, sign $0.63$; $t_3$ — $t\ 0.78$, Wilcoxon $0.87$, sign $0.72$. The sign test looks worse than its efficiency suggests mainly because its attained size is only $2\%$; a randomised version recovers much of the gap.

🧪 Self-check quiz

0/5 correct

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