1
$\begingroup$

Let $\mathbb{G} = \mathbb{Z}/p\mathbb{Z}$ (where $p$ is a prime). Let $X,Y,Z$ be independent random variables in $\mathbb G$. For a small $\epsilon$ we have $\operatorname{dist}_{TV}(X+Y,Z+Y)<\epsilon$. Assuming $X$ and $Z$ are disjoint, I'd like to express $\operatorname{dist}_{TV}(Y,U)$ in terms of $\epsilon$, where $U$ is a variable distributed uniformly over $\mathbb G$ and TV is total variation distance, that is $$\operatorname{dist}_{TV}(A,B)=\max_D\left|\Pr(A\in D)-\Pr(B\in D) \right|$$

Something similar was done by Prof. Terrence Tao but with entropy-based distances: see Proposition 1.3 of https://arxiv.org/abs/2306.13403.

I wish to find, if possible, an upper bound for $\operatorname{dist}_{TV}(Y,U)$ that does not depend on $|\mathbb G|$ or the size of the support of $X,Y,Z.$

Thank you very much to anyone willing to help!

$\endgroup$
0

1 Answer 1

3
$\begingroup$

I do not think such a bound is possible. Let $p$ be large, $X$ be uniform on the set $A = \{0,2, 4, \ldots, p-3\}$, and $Z$ uniform on the set $A+1$. Moreover, let $Y = \{0, 1\}$ with equal probability.

Then $X + Y$ is uniform on the set $\{0, \ldots p-2\}$, and $Z+Y$ is uniform on $\{1, \ldots, p-1\}$. So $d_{TV}(X+Y, Z+Y) = O(1/p)$, but clearly $Y$ is very far from a uniform distribution.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Commented Apr 20 at 12:10
  • $\begingroup$ 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. $\endgroup$
    – alon
    Commented Apr 20 at 12:36
  • $\begingroup$ 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$. $\endgroup$ Commented Apr 20 at 12:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .