ON THE IMPOSSIBILITY OF AMPLIFYING THE INDEPENDENCE OF RANDOM-VARIABLES

In this paper we prove improved lower and upper bounds on the size of sample spaces which which are required to be independent on specified neighborhoods. Our new constructions yield sample spaces whose size is smaller than previous constructions due to Schulman. Our lower bounds generalize the known lower bounds of Alon et al. and Chor et al..In o btaining these bounds we examine the possibilities and limitations of amplifying limited independence by fixed functions. We show that in ge neral independence cannot be amplified from k-wise independence to (k + 1)-wise independence. Finally, we enumerate all possible logical con sequences of pairwise independence random bits, i.e., events whose pro babilities are a consequence of pairwise independence. (C) 1995 John W iley & Sons, Inc.