A Note on the Probability of Rectangles for Correlated Binary Strings
© 1963-2012 IEEE. 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 ques...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Rannpháirtithe: | |
| Formáid: | Alt |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Rochtain ar líne: | https://hdl.handle.net/1721.1/134030 |
| _version_ | 1826204875454676992 |
|---|---|
| author | Ordentlich, Or Polyanskiy, Yury Shayevitz, Ofer |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ordentlich, Or Polyanskiy, Yury Shayevitz, Ofer |
| author_sort | Ordentlich, Or |
| collection | MIT |
| description | © 1963-2012 IEEE. 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}]$. |
| first_indexed | 2024-09-23T13:02:46Z |
| format | Article |
| id | mit-1721.1/134030 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:02:46Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1340302023-02-23T20:45:27Z A Note on the Probability of Rectangles for Correlated Binary Strings Ordentlich, Or Polyanskiy, Yury Shayevitz, Ofer Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 1963-2012 IEEE. 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}]$. 2021-10-27T19:57:42Z 2021-10-27T19:57:42Z 2020 2021-03-09T20:01:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134030 en 10.1109/TIT.2020.3018232 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Ordentlich, Or Polyanskiy, Yury Shayevitz, Ofer A Note on the Probability of Rectangles for Correlated Binary Strings |
| title | A Note on the Probability of Rectangles for Correlated Binary Strings |
| title_full | A Note on the Probability of Rectangles for Correlated Binary Strings |
| title_fullStr | A Note on the Probability of Rectangles for Correlated Binary Strings |
| title_full_unstemmed | A Note on the Probability of Rectangles for Correlated Binary Strings |
| title_short | A Note on the Probability of Rectangles for Correlated Binary Strings |
| title_sort | note on the probability of rectangles for correlated binary strings |
| url | https://hdl.handle.net/1721.1/134030 |
| work_keys_str_mv | AT ordentlichor anoteontheprobabilityofrectanglesforcorrelatedbinarystrings AT polyanskiyyury anoteontheprobabilityofrectanglesforcorrelatedbinarystrings AT shayevitzofer anoteontheprobabilityofrectanglesforcorrelatedbinarystrings AT ordentlichor noteontheprobabilityofrectanglesforcorrelatedbinarystrings AT polyanskiyyury noteontheprobabilityofrectanglesforcorrelatedbinarystrings AT shayevitzofer noteontheprobabilityofrectanglesforcorrelatedbinarystrings |