Abstract

Balanced sampling is looking for a vector x, with 0-1 entries, that meets the constraints Ax=b where A is matrix of constraints and b a predetermined vector of constraint totals. A sampling problem is said to be exactly balanced if all the solutions x, with entries in 0,1], of the system of equations Ax=b, can be expressed as convex combinations of solutions of Ax=b with 0-1 entries (or of vertices of the unit cube). An alternative definition is that a problem is exactly balanced if the flight phase of the cube algorithm always produces a vector with 0-1 entries so that a landing phase is not needed. Exact balance is possible when the matrix A has 0-1 entries and the vector b is integer valued. Such matrices A occur when the constraints involve several stratifications of the same population and in random network generation. Exact balance is independent of the sampling method used. It only depends on the geometry of the problem. A sufficient condition for a problem to be exactly balanced is that the matrix A be totally unimodular. We show, through several examples, that this condition is not necessary. Our results are an extension of a line of thought initiated by Jean-Claude Deville on the search for a necessary and sufficient condition for a balanced sampling problem to be exact, i.e. for there to be no rounding problem at the end of the flight phase of the cube algorithm.