Premium
MOD p ‐tests, almost independence and small probability spaces
Author(s) -
BertramKretzberg Claudia,
Lefmann Hanno
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200007)16:4<293::aid-rsa1>3.0.co;2-f
Subject(s) - mathematics , joint probability distribution , probability distribution , independence (probability theory) , discrete mathematics , random variable , combinatorics , sample space , simple (philosophy) , regular conditional probability , convolution of probability distributions , space (punctuation) , probability measure , probability mass function , statistics , computer science , philosophy , epistemology , operating system
In this paper, we consider approximations to probability distributions over Z p n . 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 1 , X 2 ,…, 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