Statistical Distance and Learning with Rounding

Given an integer $$b$$ modulo a prime $$q$$, one can define a `rounding’ function $$\lfloor b\rceil_p$$ for a prime $$p$$, $$p, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$ In the paper Pseudorandom Functions and Lattices, it is claimed that the statistical distance between the uniform distribution over $$\mathbb{Z}_p$$, $$U(\mathbb{Z}_p)$$, and the distribution obtained by sampling from the uniform distribution over $$\mathbb{Z}_q$$ and then rounding, $$\lfloor U(\mathbb{Z}_q)\rceil_p$$, is at most $$\frac{p}{q}$$. Why is this the maximum statistical distance?

The statistical distance between two probability distributions $$\mathbf{A}$$ and $$\mathbf{B}$$ with support $$S$$ is defined as $$\mathbf{SD}(\mathbf{A}, \mathbf{B}) = \frac{1}{2} \sum_{x \in S} |\mathbf{Pr}[\mathbf{A} = x] - \mathbf{Pr}[\mathbf{B} = x]|\,.$$

Applying this to the rounding function, with positive integers $$q\ge p\ge 2$$ as assumed in the paper, let $$d$$ and $$r$$ be the smallest integers such that $$q = d\cdot p + r$$ (i.e., $$d = \lfloor q/p \rfloor$$ and $$r = q \bmod p$$). Then we have $$r$$ elements of $$\mathbb{Z}_p$$ occurring with probability $$\frac{d+1}{q}$$ and $$p-r$$ elements with probability $$\frac{d}{q}$$.

Plugging this in the above formula we get

\begin{align*} \mathbf{SD}(\mathbf{U}(\mathbb{Z}_p), {\lfloor \mathbf{U}(\mathbb{Z}_q) \rceil}_p) &= \frac{1}{2}\left( \left|r\left(\frac{1}{p} - \frac{d+1}{q}\right)\right| + \left|(p-r)\left(\frac{1}{p} - \frac{d}{q}\right)\right| \right) \\ &= \frac{1}{2}\left( \left|\frac{r}{p} - \frac{r(d+1)}{q}\right| + \left|\frac{p-r}{p} - \frac{d(p-r)}{q}\right| \right) \\ &= \frac{1}{2}\left( \left|\frac{r}{p} - \frac{r(d+1)}{q}\right| + \left|\left( 1- \frac{r}{p}\right) - \left(1 - \frac{r(d+1)}{q}\right)\right| \right) \\ &= r\left(\frac{d+1}{q} - \frac{1}{p}\right)\,. \end{align*}

Since $$r = q \bmod p$$ we can upper bound $$r$$ by $$p$$, and thus we can simplify the above to $$\frac{p(q/p+1)}{q} - \frac{p}{p} = \frac{q+p}{q} - 1 = p/q$$.

This same reasoning also applies to the $${\lfloor \mathbf{U}(\mathbb{Z}_q) \rfloor}_p, {\lceil \mathbf{U}(\mathbb{Z}_q) \rceil}_p$$, and $$\mathbf{U}(\mathbb{Z}_q) \bmod p$$ functions.

• It’s worth noting that the whole argument goes through even when $p,q$ are not prime. E.g., if $p$ divides $q$ then $r=0$ and so the statistical distance is zero. Also, there’s implicitly an inequality (upper bound) when you replace $r$ with $p$, which might not be totally obvious to the reader. Aug 31, 2022 at 18:30