Exact Permutation Algorithm for Paired Observations: The Challenge of R. A. Fisher

Abstract

The major handicap of permutation test is the logical and computational requirement necessary to develop and implement the exact permutation scheme. This study provides an algorithm that systematically enumerates all the distinct permutations of the paired observations in an experiment without the possibility of repeating any of the permutations. The permutation algorithm presented completely breaks down the permutation problem for ease of implementation and analysis. The algorithm was illustratively implemented in Intel Visual Fortran to recreate Fisher’s manual compilation of 32,768 permutations of Charles Darwin’s data on heights of cross-fertilized and self-fertilized plants. The algorithm provides exact p-values for any experiment involving paired observations and exposes the danger in using asymptotic or parametric distributions such as the t-test to analyze small data sets when the exact functional form of the distribution is not explicitly known. This becomes more obvious especially when the experiment leads to a p-value close to the threshold level of significance. The exact distribution and the graphical presentation provided in this study give credence to the use of the permutation test.