Timeline for Entropy and total variation distance
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17, 2018 at 20:25 | history | edited | Algernon | CC BY-SA 4.0 |
Iosif Pinelis's example: the inequality is sharp
|
| Sep 17, 2018 at 19:22 | comment | added | usul | Very nice answer, and I agree with Iosif that the example is tight for all $N$. I calculate $H(Y) = H(B) + H(Y|B)$, where $B$ is the indicator for $Y=1$. We have $H(B) = H(\epsilon)$ and $H(Y|B) = (1-\epsilon)(0) + \epsilon H(U)$ where $U$ is uniform on $\{2,\dots,N\}$. This gives $H(Y) = H(\epsilon) + \epsilon \log(N-1)$. | |
| Sep 17, 2018 at 17:34 | comment | added | Iosif Pinelis | @Algernon : The bound $H(\varepsilon) + \varepsilon\ln(N-1)$ is actually optimal for all $N$ and $\varepsilon$: Take $p_1=1$, $q_1=1-\varepsilon$, $q_2=\cdots=q_N=\varepsilon/(N-1)$. | |
| Sep 17, 2018 at 17:19 | history | edited | Algernon | CC BY-SA 4.0 |
Added a sharper bound suggested by Iosif Pinelis
|
| Sep 17, 2018 at 16:25 | comment | added | Algernon | @IosifPinelis : You are right! We can get $H(\varepsilon)+\varepsilon\ln(N-1)$ with a small refinement. I will update my answer. | |
| Sep 17, 2018 at 14:39 | comment | added | Iosif Pinelis | @Algernon : I think the exact bound is $H(\varepsilon) + \varepsilon \ln(N-1)$. Can your reasoning be modified to get that? | |
| Sep 17, 2018 at 14:13 | comment | added | H A Helfgott | (Well, for $N\leq 2$, $|H(X)-H(Y)|\leq \epsilon \log(N/\epsilon)$would be false , as the example of $X\sim \text{Bern}(\epsilon)$, $Y\sim \text{Bern}(0)$ shows. Still\dots) | |
| Sep 17, 2018 at 14:07 | comment | added | H A Helfgott | (PS. I'm preparing lecture notes - message me so that I can put you in the acknowledgements.) | |
| Sep 17, 2018 at 14:05 | comment | added | H A Helfgott | I wonder, though, whether this inequality is optimal. It implies $|H(X)-H(Y)|\leq 2\epsilon \log \epsilon + \epsilon \log N$, but would $|H(X)-H(Y)|\leq \epsilon \log(N/\epsilon)$ (say) be false? | |
| Sep 17, 2018 at 14:03 | comment | added | H A Helfgott | No, you are right - I just didn't remember it was that easy (it is). | |
| Sep 17, 2018 at 13:27 | comment | added | Algernon | Yes, I could have explicitly given the distributions of $Z$ and $(\tilde{X},\tilde{Y})$ and then a high school student would have been able to verify that $X$ and $Y$ have the right distributions. The "standard construction" remark was to communicate with a fellow mathematician that there is a standard way to find such a representation. | |
| Sep 17, 2018 at 7:31 | comment | added | H A Helfgott | Never mind - it is in section 4.2 of Levin-Peres-Wilmer. Yes, it is elementary. | |
| Sep 17, 2018 at 6:11 | comment | added | H A Helfgott | Well, sure. I meant something that can be explained quickly to non-probabilists. In particular, may I have a reference to the "standard construction"? | |
| Sep 17, 2018 at 3:02 | comment | added | Algernon | I am not sure what you call elementary. To me, this answer is completely elementary, since it uses only elementary concepts from probability theory and entropy. | |
| Sep 16, 2018 at 22:37 | comment | added | H A Helfgott | Thanks! This is in general shaper than the above solution. I wonder whether a completely elementary proof (such as the one above) is useful? | |
| Sep 16, 2018 at 16:41 | history | answered | Algernon | CC BY-SA 4.0 |