Existence and applications of finite-population samples that are exactly balanced

Samples selected from finite populations can rarely be exactly balanced, as sample selection is an integer problem and the balancing equations are strict equalities. Selecting a balanced sample is not a problem limited to survey sampling. It also applies to design of experiments, clinical trials, causality, exact inference, graph theory and network analysis. Building on Jean-Claude Deville’s foundational work, we explore conditions under which exact solutions are achievable. We show that, if the constraint matrix is totally unimodular, then all solutions are exact. This condition is not necessary: exact solutions arise when the constraint matrix is not totally unimodular. An interesting example of exact balancing is when two stratifications overlap, of which the unbiased controlled rounding problem is a special case. With three stratifications, the problem is no longer exact. It is sometimes possible to make a problem exact by adding constraints. We establish a connection with the problem of selecting a sample uniformly among all possible exact samples, a question of interest for the generation of random graphs and for exact inference in logistic regression. Moreover, we establish a link with the theory of experimental designs by showing that the construction of balanced incomplete block designs is also a balanced sampling problem. The question of exact balance therefore has a wide range of practical applications and provides a link between very different fields.