Timeline for Small total variation distance between sums of random variables in finite Abelian group implies close to uniform?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20 at 12:40 | comment | added | Jarosław Błasiok | Well, you could just as well take $Y$ to be a uniform on an arthmetic progression $\{0, 2, \ldots, 2q\}$ where $q$ is some number around $p/4$ and $X = 0$ deterministically, $Z=2$ deterministically. So really the right thing to look at are arithmetic progressions in $G$, as opposed to subgroups of $G$ --- and there is quite a bit more of the former than latter for $\mathbb{Z}/\mathbb{Z}p$. | |
| Apr 20 at 12:36 | vote | accept | alon | ||
| Apr 20 at 12:36 | comment | added | alon | Very interesting. Though, the Y you gave is 0.5-indistinguishable to uniform on subgroup {0} For a small enough epsilon, I'd like to get such a 0.5 bound for either {0} or G. | |
| Apr 20 at 12:10 | comment | added | kodlu | I was about to write the same. In general Pinsker (reverse Pinsker?) style inequalities can be used to try and achieve the best possible but will have penalty terms. | |
| Apr 20 at 12:01 | history | answered | Jarosław Błasiok | CC BY-SA 4.0 |