MODp‐tests,almost independence and small probability spaces

In this paper, we consider approximations to probability distributions over Z . We present an approach to estimate the quality of approximations to probability distributions towards the construction of small probability spaces. These small spaces are used to derandomize algorithms. In contrast to results by Even, Goldreich, Luby, Nisan, and Veličković EGLNV], the methods which are used here are simple, and we get smaller sample spaces. Our investigations are motivated by recent work of Azar, Motwani, and Naor AMN]. They considered the problem to construct in time respective space polynomial in n a good approximation to the joint probability distribution of the mutually independent random variables X₁, X₂,…,X_n. Each X_i has values in {0, 1} and satisfies X_i=0 with probability q and X_i=1 with probability 1−q where q∈0, 1] is arbitrary. Our considerations improve on results in EGLNV] and AMN] for q=1/p and p a prime. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 293–313, 2000