  The objective of goodness-of-fit testing is to assess whether a dataset of
observations is likely to have been drawn from a candidate probability
distribution. This paper presents a rank-based family of goodness-of-fit tests
that is specialized to discrete distributions on high-dimensional domains. The
test is readily implemented using a simulation-based, linear-time procedure.
The testing procedure can be customized by the practitioner using knowledge of
the underlying data domain. Unlike most existing test statistics, the proposed
test statistic is distribution-free and its exact (non-asymptotic) sampling
distribution is known in closed form. We establish consistency of the test
against all alternatives by showing that the test statistic is distributed as a
discrete uniform if and only if the samples were drawn from the candidate
distribution. We illustrate its efficacy for assessing the sample quality of
approximate sampling algorithms over combinatorially large spaces with
intractable probabilities, including random partitions in Dirichlet process
mixture models and random lattices in Ising models.
