A Note on the Influence of anε-Biased Random Source

摘要

Anε-biased random source is a sequenceX=(X1, X2, …, Xn) of 0, 1-valued random variables such that the conditional probability Pr[Xi=1 | X1, X2, …, Xi−1] is always between 12−εand 12+ε. Given a familyS⊆{0, 1}nof binary strings of lengthn, itsε-enhanced probability Prε(S) is defined as the maximum of PrX(S) over allε-biased random sourcesX. In this paper we establish a tight lower bound on Prε(S) as a function of |S|,nandε.