On the impossibility of amplifying the independence of random variables
Jin‐Yi Cai, Suresh T. Chari · Random Structures and Algorithms · 1995
Abstract 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 obtaining these bounds we examine the possibilities and limitations of amplifying limited independence by fixed functions. We show that in general independence cannot be amplified from k‐wise independence to (k + 1)‐wise independence. Finally, we enumerate all possible logical consequences of pairwise independence random bits, i.e., events whose probabilities are a consequence of pairwise independence.