Convergence rate of the convolution of almost uniform measures on $\mathbb{Z}_p$

Question

Statement Given a finite abelian group $G$ and two independent random variables $X,Y$ taking values in $G$ and satisfying $d_{TV}(X,U_G)\leqslant \delta$ and $d_{TV}(Y,U_G)\leqslant \delta$ (where $U_G$ denotes a uniformly distributed over $G$ and $d_{TV}$ is the total variation distance), we ask how close is $X+Y$ to $U$? One can show that

$$ d_{TV}(U_G,X+Y) \leqslant 2 \cdot d_{TV}(X,U_G)d_{TV}(Y,U_G) $$

the proof is elementary yet a little bit complex, it goes by reduction to the problem of finding the winning probability in a certain game. The constant $2$ is optimal over $G=\mathbb{Z}_2$.

Question Do you have any ideas what theory could be applied here, to obtain an alternative proof and a better constant for certain group (like $G=\mathbb{Z}_p$)?

We assume only that the variation distance are small, cannot impose any restrictions about eigen values, second norms etc. Fourier Analysis seems to be not a good choice here, as the characters for $\mathbb{Z}_p$ are not compatible with $\{-1,1\}$-valued functions that computes the variation distance (this is not the case of $G=\mathbb{Z}_2^{n}$ though). I was thinking also about applying Markov Chain Theory, e.g. minorizing condition but given that conditions it is not satisfied in general for any measure.

Edit In applications I am thinking of $\delta >> \frac{1}{|G|}$

Answer 1

I think in general you can't expect anything better than $2$ regardless of the group.

Saying $d_{TV}(X, U_G) \leq \delta$ is equivalent to saying we can write the measure corresponding to $X$ as $$\mu_X=\mu_U + (\mu_1 - \mu_2),$$ where $\mu_U$ is the uniform measure, and $\mu_1$ and $\mu_2$ are positive measures having equal total mass at most $\delta$. Similarly, we can write $$\mu_Y=\mu_U + (\mu_3 - \mu_4).$$ Since $\mu_1$ and $\mu_2$ have the same total mass, $\mu_U * (\mu_1-\mu_2)$ is $0$. Similarly, $\mu_U * (\mu_3-\mu_4)=0$. So when we expand out the convolutions, we get \begin{eqnarray*} \mu_X * \mu_Y &=& \mu_U + (\mu_1-\mu_2) * (\mu_3 - \mu_4) \\ &=&\mu_U + (\mu_1 * \mu_3 + \mu_2 * \mu_4) - (\mu_1 * \mu_4 + \mu_2 * \mu_3) \end{eqnarray*} Both of the parenthesized terms have total mass $2 d_{TV}(X, U_G) d_{TV}(Y,U_G)$, so we have that bound on the total variation distance.

Equality holds if the two parenthesized terms have disjoint support. This can happen in any group if $\delta$ is sufficiently small -- for example, we can take $\mu_1$ and $\mu_3$ to be point masses on $0$, and $\mu_2$ and $\mu_4$ to be point masses on some nonzero $g$ (corresponding to $$P(X=0)=P(Y=0)=1/|G|+\delta, P(X=g)=P(Y=g)=1/|G|-\delta,$$ and elsewhere uniform).

In general maximizing the distance of $X+Y$ from uniform corresponds to minimizing the overlap between the two sums of convolutions.

Answer 2

Summing up, we have reduced the problem to the following, related to additive combinatoric

Determine an upper bound on

$$ \frac{1}{2}\left\| \delta_{0}-\frac{\mathbb{1}_{A}}{|A|} - \frac{\mathbb{1}_{B}}{|B|} + \frac{\mathbb{1}_A}{|A|} * \frac{\mathbb{1}_B}{|B|} \right\|_{\ell_1(G)} = \left\| \delta_{0}-\frac{\mathbb{1}_{A}}{|A|} - \frac{\mathbb{1}_{B}}{|B|} + \frac{\mathbb{1}_A}{|A|} * \frac{\mathbb{1}_B}{|B|} \right\|_{TV} \quad (\star)$$

where $A,B$ are aribrary sets of cardinality $\delta\cdot |G|$ and $\delta_0$ is a point mass concentrated in $0$.

The problem seems to be in fact the question about concentration of the convolution $\mathbb{1}_{A}*\mathbb{1}_{B}$. But I guess that the general results are rather negative in this case...?

Let's start with the following simple approach. Suppose that $\delta>\frac{1}{2}$. Then for any abeliean group we have $A+B = G$. Moreover, we have $\mathbb{1}_{A}*\mathbb{1}_{B}(x) = r_{A,B}(x) \geqslant |A|+|B|-|G| = (2\delta-1)|G|$. This way for every point $x \in A \cup B$, calculating the total variation we have additional positive contribution of $\frac{(2\delta-1)|G|}{|A||B|}$ that cancels the negative contribution of $\mathbb{1}_A$ or $\mathbb{1}_{B}$. This way the total variation norm is decreased by $\max(|A|,|B|)\cdot \frac{(2\delta-1)|G|}{|A||B|} = \frac{2\delta-1}{\delta}$ and we have at most $2-\frac{2\delta-1}{\delta}$ in $(\star)$.

Note that this is substantially better if $\delta > \frac{1}{2}$. At least it proves that the distance cannot increase (which is almost obvious by a Markov-Chain-like argument).

What could be a problem here, is a hypothetical situation, where $\mathbb{1}_{A}*\mathbb{1}_{B}$ attains its biggest values on a very small sets and is almost uniform on the rest of its support $A+B$. But fortunatelly from Pollard Theorem we can conclude that the values of $\mathbb{1}_{A}*\mathbb{1}_{B}$ cannot be "badly" distributed. The details are in the topic Anticoncentration of the convolution of two characteristic functions.

Edit Before I claimed that it seems that Pollard Theorem does not help. Fortunatelly I was wrong, it does. Thanks to Seva for pointing this!