Consider two sequences of $n$ independent and identically distributed fair coin tosses, $X=(X_1,ldots,X_n)$ and $Y=(Y_1,ldots,Y_n)$, which are $rho$-correlated for each $j$, i.e. $mathbb{P}[X_j=Y_j] = {1+rhoover 2}$. We study the question of how large (small) the probability $mathbb{P}[X in A, Yin B]$ can be among all sets $A,Bsubset{0,1}^n$ of a given cardinality. For sets $|A|,|B| = Theta(2^n)$ 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^{Theta(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 $mathbb{P}[X in A, Yin B]$ in the regime of $rho to 1$. We also prove a similar tight lower bound, i.e. show that for $rhoto 0$ the pair of opposite Hamming balls approximately minimizes the probability $mathbb{P}[X in A, Yin B]$.
Download