Compare Classifiers on the Same Test Cases: The Exact McNemar Test, a Proof That Pairing Shrinks Variance by the Error Correlation, and Connor's Sample-Size Formula Checked on 16,281 Census Records

Two classifiers scored on the same test set make correlated errors, yet their accuracies are often compared as if they came from independent samples. I prove three results. Conditional on the number of discordant cases, the count of cases that only the first model gets wrong is binomial with probability one half under the null of equal error, which gives an exact test of guaranteed size. The variance of the paired difference in error rates is the unpaired variance minus twice the covariance of the error indicators, so pairing helps whenever errors are positively correlated. A normal approximation to the power of the McNemar statistic gives Connor's 1987 sample-size formula. On the official UCI Adult split (32,561 training and 16,281 test records), logistic regression, a random forest and gradient boosting have test errors of 0.1470, 0.1361 and 0.1266. The error indicators are strongly correlated, between 0.755 and 0.834, so the unpaired variance is 4.1 to 6.0 times the paired variance. For the forest against boosting the unpaired z-test gives p = 0.011 while the exact McNemar test gives p = 4.9e-10. To detect the observed gaps with 80 percent power at the 5 percent level, Connor's formula asks for 1,101 to 3,485 test cases, against 4,453 to 19,757 for the unpaired formula. Resampling the test set shows empirical power of 0.762 to 0.781 at Connor's sizes, slightly below the target because the exact test is conservative: its size under a symmetrised null is 0.037.