Lower Bounds on Same-Set Inner Product in Correlated Spaces
Jan Hązła, Thomas Holenstein, Elchanan Mossel · DSpace@MIT (Massachusetts Institute of Technology) · 2015
Let Ρ be a probability distribution over a finite alphabet Ωℓ with all ℓ marginals equal. Let X(1), . . . , X(ℓ), X(j) = (X(j)1 , . . . , X(j)n ) be random vectors such that for every coordinate i ϵ [n] the tuples (X(i)1 , . . . , X(ℓ)i ) are i.i.d. according to Ρ. The question we address is: does there exist a function cΡ() independent of n such that for every f :Ωn → [0, 1] with E[f(X(1))] = μ > 0: E Φ Yj=1 f(X(j)) # ≥ cΡ(μ) > 0 ? We settle the question for ℓ = 2 and when ℓ > 2 and P has bounded correlation ρ(P) < 1.