The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. Such distributions are often only required to obey a certain limited set of constraints of the form Pr(Event) = pi. We show that the problem of deciding whether there exists any distribution satisfying a given set of constraints is NP-hard. However, if the constraints are consistent, then there exists a distribution satisfying them which is supported by a ``small'' sample space (one whose cardinality is equal to the number of constraints). For the important case of independence constraints, where the constraints have a certain form and are consistent with a joint distribution of independent random variables, a small sample space can be constructed in polynomial time. This last result can be used to derandomize algorithms; we demonstrate this by an application to the problem of finding large independent sets in sparse hypergraphs.