We formulate the notion of a "good approximation" to a probability distribu
tion over a finite abelian group G. The quality of the approximating distri
bution is characterized by a. parameter epsilon which is a bound on the dif
ference between corresponding Fourier coefficients of the two distributions
. It is also required that the sample space of the approximating distributi
on be of size polynomial in log \G\ and 1/epsilon. Such approximations are
useful in reducing or eliminating the use of randomness in certain randomiz
ed algorithms.
We demonstrate the existence of such good approximations to arbitrary distr
ibutions. In the case of n random variables distributed uniformly and indep
endently over the range {0,...,d-1}, we provide an efficient construction o
f a good approximation. The approximation constructed has the property that
any linear combination of the random variables (modulo d) has essentially
the same behavior under the approximating distribution as it does under the
uniform distribution over {0,...,d-1}. Our analysis is based on Well's cha
racter sum estimates. We apply this result to the construction of a non-bin
ary linear code where the alphabet symbols appear almost uniformly in each
non-zero code-word.