Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
28,358 characters · 4 sections · 14 citation commands
R. A. Fisher's Exact Test Revisited
\def\spacingset#1{ {#1}} \spacingset{1}
\if11 \fi
\if01 {
} \fi
\spacingset{1.9}
A colleague of Ronald Aylmer Fisher asserts that they can distinguish tea poured into milk from milk poured into tea. To convince himself, Fisher prepares eight cups of tea, four with tea poured into milk (confidentially labelled $TM$) and four with milk poured into tea (confidentially labelled $MT$). He presents the cups in random order to his colleague, who is asked to taste and assign one of the labels $\{TM,MT\}$ to each cup. Before tasting, the colleague knows that there are four $TM$ cups and four $MT$ cups among the eight, but they do not know the specific order in which Fisher arranged the cups.\footnote{I am indebted to ritzwoller2024 for inspiring this short paper and introduction. This experiment is reported in Fisher1935, p.13-29.}
\paragraph{Fisher's null hypothesis} Distinguishing $TM$ cups from $MT$ cups is a rather surprising skill. Fisher considers the null hypothesis that all possible assignments of eight cups into two groups of four are equally probable answers. He disbelieves that his colleague can do better or worse than a fair coin toss prediction unless they provide some experimental evidence. Specifically, Fisher states
Without further assumption, experimental evidence can be understood as observing some event reflecting a “sufficiently large deviation” from what the uniform distribution over the set of all possible assignments would “typically predict”. Such an event may be {\em perfect distinction in the prediction sense}, which occurs if each time the experimenter presents $TM$ (resp. $MT$), the taster claims $TM$ (resp. $MT$). Another one is {\em perfect distinction in the weak information sense}, which occurs if each time the experimenter presents $TM$ (resp. $MT$), the taster claims $MT$ (resp. $TM$). Note that perfect distinction in the weak informative sense implies perfect distinction in the predictive sense up to applying the deterministic bijective transformation $g:\{TM,MT\}\to\{TM,MT\}$ defined as $g(TM)=MT$ and $g(MT)=TM$ to each claim. In other words, both extreme events equally suggest that the taster can “distinguish” by using some knowledge about $TM$ and $MT$ to recover the correct equivalence classes of cups invariant to relabeling.
\paragraph{Fisher's exact test} Let $Y_N=(Y_{1N},\ldots,Y_{NN})'$ denote the $N$ cup labels corresponding to the random ordering chosen by Fisher, among which $n$ are $TM$ and $N-n$ are $MT$. Let $X_N=(X_{1N},\ldots,X_{NN})'$ denote the (random) sequence of answers from his colleague. Fisher's null hypothesis is an assumption on the joint distribution $P_{(X_N,Y_N)}$. Specifically, it says that the conditional distribution $P_{X_N|Y_N}$ is the uniform distribution over the set $$\mathcal X_{N,n}:=\left\{x\in\{TM,MT\}^N:\sum_{j=1}^N1\{x_j=TM\}=n \right\}.$$ In Fisher's experiment, $N=8$, $n=4$, and $\vert\mathcal X_{8,4}\vert={8\choose 4}=70$ where for any finite set $A$, $\vert A \vert$ denotes the cardinality of $A$. Fisher randomly draws $Y_8\in\mathcal X_{8,4}$ and his colleague answers $X_8\in\mathcal X_{8,4}$. Under the null hypothesis, for any given $Y_8\in\mathcal X_{8,4}$, there is a 1/70 chance of observing only right answers, i.e., $X_8=Y_8$. Fisher rejects the null hypothesis if and only if $X_8=Y_8$. The test is exact at the significance level $5\%$ since the probability to reject under the null, i.e., to make a Type I error, is $1/70\approx0.014\leq5\%$. This probability does not depend on $Y_8$: it is the same both conditionally and unconditionally on $Y_8$.
\paragraph{A disconnect} Though Fisher does not specify an alternative hypothesis, he chooses a rejection region in favour of perfect distinction in the predictive sense. Why ignore the region in favour of perfect distinction in the weak information sense? Certainly not for significance-level considerations. Under the null, the event of observing no right answer, $\cap_{j=1}^8\{X_{j8}\neq Y_{j8}\}$, also occurs with probability 1/70 so that the exact test that rejects the null if and only if $\cap_{j=1}^8\{X_{j8}\neq Y_{j8}\} \cup \{X_8=Y_8\}$ is observed is at least as powerful against all alternatives, is more powerful against some alternatives, and enjoys the same significance level since $2/70\approx0.029\leq5\%$.
In this experiment, the colleague ends up making correct predictions for all cups, which implies that both tests reject the null at the significance level $5\%$ (the size of the more powerful test, however, is higher). Despite that running the more powerful test does not change the conclusion in this particular experiment, there is a priori no theoretical justification for preferring the original exact test. More concerning, the exact $5\%$-level test that rejects the null if and only if $\cap_{j=1}^8\{X_{j8}\neq Y_{j8}\}$ is observed, although equally legitimate, does not reject the null in this experiment.
Fisher is one of the most celebrated statisticians and it is of interest to investigate what could have motivated the disconnect between his null hypothesis and his proposed exact test. A natural justification is that Fisher has an alternative hypothesis in mind. Others have gathered around the table, and the only reason his colleague might challenge him is to demonstrate to the community that they can do “better” than a random guess in the commonly accepted sense, i.e., the prediction sense. Fisher is willing to reject only based on evidence pointing to that direction. This justification, however, is rather unsatisfactory for at least two reasons. First, Neyman1928 are credited for introducing the concept of alternative hypothesis after Fisher's first formulation of his methodology Fisher1925. Second, Fisher himself later opposed the use of an alternative hypothesis in the 1966 edition of his book Fisher1935.
The next section provides another rigorous justification taking the form of an explicit behavioural hypothesis on the taster that avoids explicitly invoking any particular alternative hypothesis. It amounts to formalizing a single crucially important sentence in the original text, though left over in the sequel and often overlooked in modern expositions:
Fisher implicitly assumes that he and the taster agree that the taster will use their discriminating ability, {\em if any} (that is {\em under any alternative}), to minimize misclassification. While this assumption is innocuous to stating the null hypothesis, it is central to justifying Fisher’s test rejection region, as it implies stochastic dominance relationships between distributions of success under different levels of probabilistic information. Theorem 3.1 clarifies this point by formalizing the minimization problem within a statistical decision and information-theoretic framework.
As emphasized in the previous section, a possible source of confusion regarding the mapping from Fisher's null hypothesis to his exact test is that the ability to distinguish has more to do with information than correct prediction. More than 70 years ago (and thus posterior to Fisher), Claude Shannon introduced the concept of {\em entropy} or {\em Shannon information}.\footnote{See Shannon1948.} The main contribution of this note is to employ this key concept from information theory to eliminate any disconnect by giving a mathematically precise, behaviourally sound and rigorous justification for Fisher1935's exact test in the {\em Lady Testing Tea} experiment.
\paragraph{Misclassification loss} Consider the classical binary misclassification loss $\ell$, popular in the statistical learning and decision literature: for all $x_N,y_N\in\mathcal X_{N,n}$, \[ \ell(x_N,y_N):=\sum_{j=1}^N1\{x_{jN}\neq y_{jN}\}. \] The theoretical expected predictive performance of the taster in terms of loss $\ell$ and distribution of answers $P_{X_N|Y_N}$ can be visualized as an arrow “indexing the joint distributions” from the left (systematically less correct than random with the extremity being “always wrong” if almost surely $\cap_{j=1}^8\{X_{j8}\neq Y_{j8}\}$ and thus $\ell(X_8,Y_8)=8$) through the centre (as correct as random) to the right (systematically more correct than random with the extremity being “always correct” if almost surely $X_8=Y_8$ and thus $\ell(X_8,Y_8)=0$). Clearly, observing $\cap_{j=1}^8\{X_{j8}\neq Y_{j8}\}$ provides evidence against the null {\em in the direction to the left} (previously called “information sense”) while observing $X_8=Y_8$ provides evidence against the null {\em in the direction to the right} (previously called “prediction sense”).
\paragraph{Misclassification minimization subject to an information constraint} For any distribution $P$ supported on a discrete set $\mathcal X$, define the probabilistic entropy, or Shannon information, as
Note that $H(X)\in[0,\log(\vert \mathcal X\vert )]$ is uniquely maximized at the uniform distribution $\overline P$ on $\mathcal X$, and minimized for Dirac distributions $\underline P\in \mathcal D(\mathcal X):=\{\delta_x:x\in\mathcal X\}$. These facts are useful to show the main result of the paper stated below.
Points (ref)-(ref) of Theorem (ref) say that if the taster chooses their answers ($P_{X_N|Y_N}^*(h)$) to minimize the expected misclassification error $\mathbb E_{P_{X_N|Y_N}}[\ell(X_N,Y_N)]$ given a maximum level of information $\overline h-h$, then i) the taster uses all available information, ii) the taster with full information ($h=0^+$) will almost surely give all answers right, and iii) Fisher's null hypothesis corresponds to a taster with no information ($h=\overline h$). Point (ref) is the most enlightening result since it justifies Fisher's exact test irrelevant of {\em any} alternative. Specifically, the more the taster deviates from the null hypothesis of no information ($h=\overline h$), the more their answers ($P_{X_N|Y_N}^*(h)$) generate a distribution of successes ($N-\ell(X_N,Y_N)$) that has a heavy right tail. Such a minimizing behaviour disciplines the taster's response as a function of their information and solves the previous inconsistency of “two-sided” testing with a one-sided test by selecting a unique direction. Corollary (ref) displays the main implications of this result for Fisher's exact test. Figure (ref) provides an illustration for binary and ternary outcome distributions. The optimal path as a function of $h$ can be traced out starting from the red dot (maximum entropy distribution) and minimizing the distance to the green dot (maximum payoff) along the level curves. Analogous results hold for a maximizing taster.
Corollary (ref) shows that only events related to “higher success than random” are more extreme under any violation of the null hypothesis than under the null.
\paragraph{Connection to the maximum entropy, entropic regularization, multinomial logit, and rational inattention literature} Theorem (ref) can be interpreted as a reverse of the Bayesian principle of maximum entropy, which dictates that among all prior distributions that incorporate precise knowledge about data, the one which represents the best the current knowledge is the one with maximal entropy. For instance, given knowledge of the mean, the exponential distribution is the distribution with the largest entropy. Given knowledge of mean and variance, the Gaussian distribution is the distribution with maximum entropy. In contrast, Theorem (ref) fixes the entropy and considers the optimizing behaviour of the taster: among all distributions with a given entropy, the taster chooses the one that minimizes their expected prediction loss. In that sense, it is closer to entropic regularization methods at the heart of the optimal transport and machine learning literature Wilson1969, Peyre2019. Its proof provides another illustration of the deep mathematical connection between entropy and the multinomial logit distribution (or the variational principle and Gibbs measure), as already shown in Jaynes1957 who reinterpreted statistical mechanics in physics using information theory and the maximum entropy principle, in Shannon1959 and Anas1983 in statistical estimation and engineering applications, or more recently in the rational inattention economic literature Matejka2015 where the decision maker's optimal information-processing strategy results in probabilistic choices that follow a logit model.
Suppose one proves another version of Theorem (ref) where the inequality constraint is replaced by an equality constraint. Then, using the fourth result of this new version, all results of the original Theorem (ref) are straightforward to obtain. Hence, the version with an equality constraint is proved below.
(ref). $H(P^*_{X_N|Y_N}(h))=h$. Under an equality constraint, this is an immediate consequence of the existence and uniqueness of $P^*_{X_N|Y_N}(h)$ established in Point (ref) below.
(ref). $P_{X_N|Y_N}^*(\overline h)={\rm Uniform}(\mathcal X_{N,n})$. It suffices to show that for any finite set $\mathcal W$, the collection of distributions $P$ on $\mathcal W$ such that $H(P)=\log(\vert\mathcal W\vert)$ is the singleton $\{{\rm Uniform}(\mathcal W)\}$. This is true since $H$ is uniquely maximized at ${\rm Uniform}(\mathcal W)$ over the collection of distributions $P$ on $\mathcal W$, with maximum value $H({\rm Uniform}(\mathcal W))=\log(\left\vert\mathcal W\right\vert)$. A proof of this well-known result from information theory is given for completeness. Label $\mathcal W=\{w_1,\ldots,w_{\left\vert\mathcal W\right\vert}\}$ and, for all $i\in\{1,\ldots,\left\vert\mathcal W\right\vert\}$, let $p_i=\Pr_{W\sim P}(W=w_i)$, leaving the dependence on $P$ implicit. Note that the mapping $\phi:x\mapsto x\log x$ is strictly convex on $[0,1]$ and the entropy writes $H(P)=-\sum_{i=1}^{\left\vert\mathcal W\right\vert}\phi(p_i)$. By Jensen's inequality, \[ \phi\left(\frac{\sum_{i=1}^{\left\vert\mathcal W\right\vert}p_i}{\left\vert\mathcal W\right\vert}\right)\leq \frac{\sum_{i=1}^{\left\vert\mathcal W\right\vert}\phi(p_i)}{\left\vert\mathcal W\right\vert}=-\frac{H(P)}{\left\vert\mathcal W\right\vert}. \] Hence, $H(P)\leq-\left\vert\mathcal W\right\vert\phi\left(\frac{\sum_{i=1}^{\left\vert\mathcal W\right\vert}p_i}{\left\vert\mathcal W\right\vert}\right)$. From $\sum_{i=1}^{\left\vert\mathcal W\right\vert}p_i=1$, deduce $H(P)\leq \log(\left\vert\mathcal W\right\vert)$. If $P={\rm Uniform}(\mathcal W)$, then $p_i=1/\left\vert\mathcal W\right\vert$ so that $H(P)=\log(\left\vert\mathcal W\right\vert)$. That the maximum of $H$ is uniquely attained at ${\rm Uniform}(\mathcal W)$ follows from the fact that the Hessian matrix of $H$ at $P$, denoted $\nabla_P^2 H$, takes value $$\nabla_P^2 H=
=
. $$ This matrix is negative definite, and hence $H$ is strictly concave.
(ref). {\em For all $h,h'\in(0,\overline h]$ such that $h\leq h'$, $\ell(X_N,Y_N)$ under $P_{X_N|Y_N}^*(h')$ first-order stochastically dominates $\ell(X_N,Y_N)$ under $P_{X_N|Y_N}^*(h)$.} Fix $y\in \mathcal X_{N,n}$ and let us characterize the interior solution of
To simplify notation, suppose w.l.o.g. that $2n=N$. Let $a_k={n\choose n-k+1}{n\choose k-1}$, $b_k=n-k+1$, $\boldsymbol a=(a_1,\ldots,a_{n+1})'$, and $\boldsymbol b=(b_1,\ldots,b_{n+1})'$. The number $a_k$ is the number of events associated with $b_k$ successes out of the first $n$ trials. Rewriting Problem (ref) as a maximization problem, it is equivalent to finding an interior solution $\boldsymbol p:=(p_1,\ldots, p_{n+1})'>\boldsymbol 0$ that maximizes $$(\boldsymbol a\odot\boldsymbol b)^\top\boldsymbol p=\sum_{k=1}^{n+1}(n-k+1)a_kp_k$$ subject to
where $\odot$ denotes the Hadamard product. The Lagrangian associated with this linear program with nonlinear constraints is \[ \mathcal L(\boldsymbol p,\lambda,\mu)=-(\boldsymbol a\odot\boldsymbol b)^\top\boldsymbol p+\lambda[1-\boldsymbol a^\top\boldsymbol p]+\mu[h+\boldsymbol a^\top(\boldsymbol p\odot\log(\boldsymbol p))]. \] For $h\in(0,\overline h)$, the Karush-Kuhn-Tucker conditions for an interior solution are
The first-order conditions displayed in Equation (ref) rewrite
Equation (ref) combined with the first-order condition (ref) implies the logit form
Conclude that $P^*_{X_N|Y_N=y}(h)(x)=\sum_{k=0}^n1\{\ell(x,y)=k\}p_{k+1}$ is unique. The desired first-order stochastic dominance result is equivalent to: for any non-decreasing mapping $u:\mathbb R\to\mathbb R$,
For $h=\overline h$ or $h=h'$ the result is trivial. Suppose $0< h< h'\leq \overline h$. First, taking the derivative of Equation (ref) yields
Second, let us show that ${\rm d} \mu/{\rm d} h>0$. First-order condition (ref) writes \[ \underbrace{\frac{1}{{\sum_{\ell=1}^{n+1}a_\ell\exp(b_\ell/\mu)}}\sum_{k=1}^{n+1}a_k\exp(b_k/\mu)\left[-b_k/\mu+\log\left(\sum_{\ell=1}^{n+1}a_\ell\exp(b_\ell/\mu)\right)\right]}_{=:f(\mu)}=h. \] Taking the derivative of $f$ yields
This expression can be reorganized as
This expression further simplifies to
Since $\mu>0$, the sign of $f'(\mu)$ is the same as the sign of \[ \underbrace{\Big[\sum_{k=1}^{n+1} a_kb_k^2\exp(b_k/\mu)\Big]\Big[\sum_{\ell=1}^{n+1}a_\ell \exp(b_\ell/\mu)\Big]}_{=:A(\mu)} -\underbrace{\Big[\sum_{\ell=1}^{n+1}a_\ell b_\ell\exp(b_\ell/\mu)\Big]^2}_{=:B(\mu)}. \] By developing products and using mathematical induction on $n\in\mathbb N$, it can be shown that, for all $\mu\in\mathbb R$,
Conclude \[ \frac{{\rm d} \mu}{{\rm d} h}=[f'(\mu)]^{-1}> 0. \] Next, because $b_1>b_2>\cdots>b_{n+1}$ and $\mathbb{E}_{x\sim P^*_{X_N|Y_N=y}(h)}[N-\ell(x,y)]\in(b_{n+1},b_1)$, Equation (ref) implies that there exists some $\bar k\in\{1,\ldots,n+1\}$ such that \[ \left\{
\right. \] Again, since $b_1>b_2>\cdots>b_{n+1}$ and $u$ is non-decreasing, the decomposition
completes the proof of (ref).
(ref). $\lim_{h\to0^+}\sup_{x\in\mathcal X_{N,n}}\left\vertP_{X_N|Y_N}^*(h)(x)-\delta_{Y_N}(x)\right\vert=0$. Since $\mu>0$ and $\frac{{\rm d} \mu}{{\rm d} h}> 0$, the result follows by taking $\lim_{\mu\to0^+} p_k(\mu)=1\{k=1\}/a_1=1\{k=1\}$ in Equation (ref).
The proof of Theorem (ref) is complete.