A Note on the Probability of Rectangles for Correlated Binary Strings

Or Ordentlich, Yury Polyanskiy, Ofer Shayevitz

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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}] = {\frac{1+\rho }{ 2}}$. We study the question of how large (small) the probability $\mathbb {P}[{X} \in {A}, {Y}\in {B}]$ can be among all sets ${A},{B}\subset \{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}, {Y}\in {B}]$ in the regime of $\rho \to 1$. We also prove a similar tight lower bound, i.e. show that for $\rho \to 0$ the pair of opposite Hamming balls approximately minimizes the probability $\mathbb {P}[{X} \in {A}, {Y}\in {B}]$.

שפה מקוריתאנגלית אמריקאית
מספר המאמר9171899
עמודים (מ-עד)7878-7886
מספר עמודים9
כתב עתIEEE Transactions on Information Theory
כרך66
מספר גיליון12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - דצמ׳ 2020

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.1700.1706???
  • ???subjectarea.asjc.3300.3309???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A Note on the Probability of Rectangles for Correlated Binary Strings'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי