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$ Commented Apr 20, 2024 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$ Commented Apr 20, 2024 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, 2024 at 12:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.