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

摘要

An ∈-biased random source is a sequence X= (X_1, X_2, ..., X_n) of 0, 1 -valued random variables such that the conditional probability Pr[X_i = 1 | X_1, X_2, ..., X_(i-1)] is always between 1/2 + ∈ and 1/2 + ∈. Given a family S is contained in { 0, 1 }~n of binary strings of length n, its ∈-enhanced prob- ability Pr_∈(S) is defined as the maximum of Pr_x(S) over all ∈-biased random sources X. In this paper we establish a tight lower bound on Pr_∈(S ) as a function of |S|, n and ∈.