A Note on the Probability of Rectangles for Correlated Binary Strings
Or Ordentlich, Yury Polyanskiy, Ofer Shayevitz · IEEE Transactions on Information Theory · 2020
Consider two sequences of n independent and identically distributed fair coin tosses, X = (X1, . . . , Xn) and Y = (Y1, . . . , Yn), which are ρ-correlated for each j, i.e. P[Xj= Yj] = 1+ρ/2 .We study the question of how large (small) the probability P[X ∈ A, Y ∈ B] can be among all sets A, B ⊂ {0, 1}nof a given cardinality. For sets |A|, |B| = Θ(2n) it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of |A|, |B| = 2Θ(n). By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize P[X ∈ A, Y ∈ B] in the regime of p → 1. We also prove a similar tight lower bound, i.e. show that for p → 0 the pair of opposite Hamming balls approximately minimizes the probability P[X ∈ A, Y ∈ B].