On the tensorization of the variational distance
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912054901735424 |
|---|---|
| author | Kontorovich, Aryeh |
| author_facet | Kontorovich, Aryeh |
| contents | If one seeks to estimate the total variation between two product measures $||P^\otimes_{1:n}-Q^\otimes_{1:n}||$ in terms of their marginal TV sequence $δ=(||P_1-Q_1||,||P_2-Q_2||,\ldots,||P_n-Q_n||)$, then trivial upper and lower bounds are provided by$ ||δ||_\infty \le ||P^\otimes_{1:n}-Q^\otimes_{1:n}||\le||δ||_1$. We improve the lower bound to $||δ||_2\lesssim||P^\otimes_{1:n}-Q^\otimes_{1:n}||$, thereby reducing the gap between the upper and lower bounds from $\sim n$ to $\sim\sqrt $. Furthermore, we show that {\em any} estimate on $||P^\otimes_{1:n}-Q^\otimes_{1:n}||$ expressed in terms of $δ$ must necessarily exhibit a gap of $\sim\sqrt n$ between the upper and lower bounds in the worst case, establishing a sense in which our estimate is optimal. Finally, we identify a natural class of distributions for which $||δ||_2$ approximates the TV distance up to absolute multiplicative constants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10368 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the tensorization of the variational distance Kontorovich, Aryeh Probability If one seeks to estimate the total variation between two product measures $||P^\otimes_{1:n}-Q^\otimes_{1:n}||$ in terms of their marginal TV sequence $δ=(||P_1-Q_1||,||P_2-Q_2||,\ldots,||P_n-Q_n||)$, then trivial upper and lower bounds are provided by$ ||δ||_\infty \le ||P^\otimes_{1:n}-Q^\otimes_{1:n}||\le||δ||_1$. We improve the lower bound to $||δ||_2\lesssim||P^\otimes_{1:n}-Q^\otimes_{1:n}||$, thereby reducing the gap between the upper and lower bounds from $\sim n$ to $\sim\sqrt $. Furthermore, we show that {\em any} estimate on $||P^\otimes_{1:n}-Q^\otimes_{1:n}||$ expressed in terms of $δ$ must necessarily exhibit a gap of $\sim\sqrt n$ between the upper and lower bounds in the worst case, establishing a sense in which our estimate is optimal. Finally, we identify a natural class of distributions for which $||δ||_2$ approximates the TV distance up to absolute multiplicative constants. |
| title | On the tensorization of the variational distance |
| topic | Probability |
| url | https://arxiv.org/abs/2409.10368 |