2
$\begingroup$

I have two questions regarding to statistical distance in distributions.

1: If $Z$ is uniform random variable over $N$ consecutive integers and $m < N$ then $Z$ mod $m$ has statistical distance at most $m/N$ from the uniform distribution over $[m]$ ($[m] = {0,1,2,...m-1}$). How this statement is true based on the definition of statistical distance

2: For independent random variables $X_1, X_2, Y_1, Y_2$ the distance between the joint distributions $(X_1, X_2)$ and $(Y_1, Y_2)$ is at most the sum of statistical distances of $X_1$ from $Y_1$ and $X_2$ from $Y_2$. Similarly, if these variables are group elements in $G$, the statistical distance between $X_1$ ·$X_2$ and $Y_1$ ·$Y_2$ is no greater than the sum of statistical distances of $X_1$ from $Y_1$ and $X_2$ from $Y_2$. How can we prove this statement?

These questions are a part of the RSA accumulator paper by Dan Boneh et al. Thank you for your help.

$\endgroup$
3
$\begingroup$

If $m$ divides $N$, then you get the uniform distribution over $[m].$

Let $k=N-\lfloor N/m \rfloor m.$ Note that $k\geq 0,$ with $k>0,$ if $m$ does not divide $N.$ When you reduce $Z$ modulo $m$, due to wraparound, the smallest $k$ values $0,1,\ldots,k-1$ are "hit" an extra time, as $Z$ varies from $0$ to $N-1.$ Thus the probability distribution of $W=Z \pmod m$ is:

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor +1)\quad w\leq k-1,$

and

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor)\quad k\leq w\leq N-1.$

Now sum these values absolute difference with $1/(N/m)$ which is the value of the uniform distribution at each point.

For part 2, group via row or column for each marginal distribution and apply a similar technique, to get the individual distances. Now look at the joint taking care to scale correctly when you sum over the whole array for the statistical distance of the joint from the uniform.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.