# Modulo bias: How to compute statistical distance?

Assume we have two uniform distributions $$X=U(\mathbb{Z}_m)$$ and $$Y=U(\mathbb{Z}_n) \bmod m$$, for $$m,n \in \mathbb{N}$$.

The statistical distance is defined as: $$\Delta(X, Y) = \frac{1}{2} \sum_{a \in \mathbb{Z}_m} | \Pr[X = a] - \Pr[Y = a] | \enspace.$$

Question: What is the statistical distance between $$X$$ and $$Y$$ expressed as a function of $$m$$ and $$n$$?

$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\abs}[1]{\left|#1\right|}$$

The statistical distance between $$X=U(\Z_m)$$ and $$Y=U(\Z_n) \bmod m$$ is $$\Delta(X, Y) = \abs{ \frac{(n \bmod m)^2}{mn} - \frac{n \bmod m}{n} } \enspace .$$

## Proof

Writing out the definition, we have

$$\Delta(X, Y) = \frac{1}{2} \sum_{a \in \Z_m} \abs{\Pr[X=a] - \Pr[Y=a]} \enspace.$$

For $$a \in \Z_m$$, we have $$\Pr[X=a] = 1/m$$ and $$\Pr[Y=a] = \frac{n- (n \bmod m)}{nm} \text{ , if a\geq n \bmod m ,} \\ \Pr[Y=a] = \frac{n- (n \bmod m) + m}{nm} \text{ , if a < n \bmod m .}$$

Denote $$r = (n \bmod m)$$. It follows that $$\Delta(X, Y) = \frac{1}{2} \left( \left( \sum_{a \in \Z_m: a < r} \abs{\frac{1}{m} - \frac{n - r + m}{nm}} \right) + \left( \sum_{a \in \Z_m: a \ge r} \abs{\frac{1}{m} - \frac{n- r}{nm}} \right) \right) = \frac{1}{2} \left( r \abs{\frac{1}{m} - \frac{n- r + m}{nm}} + (m - r) \abs{\frac{1}{m} - \frac{n- r}{nm}} \right) = \abs{ \frac{r^2-rm}{nm} } \enspace.$$