Permutation distributions via generating functions with applications to sensitivity analysis of discrete data

Generating functions provide a simple and elegant way to describe probability or frequency distributions of discrete statistics and, in particular, permutation distributions. They are also a computational tool. Many efficient algorithms, including those described as fast Fourier transform methods, network methods, and multiple shift methods, are different implementations of the recursions needed to evaluate generating functions efficiently. Our goals here are twofold. First, we make the relationship between these efficient methods and generating functions explicit; this establishes a language for looking at other questions in randomization/exact inference and may help in finding more efficient implementations. Second, we propose methods to examine the sensitivity of results of exact analysis of discrete data to small perturbations in the data. Specifically, we consider two settings: how the analysis would change if one outcome changed, and how the analysis would change if one observation was added to the data set. Many of the computations needed to do a single exact analysis can be reused to study sensitivity; looking at this problem as one of computing generating functions makes the relationship explicit.