I have to use the following proposition, but since I'm not that into statistics, I don't know how to prove it formally.
If there are two independent random variables $A$ and $B$ over $\{0,1,…,m-1\}$, with $A$ uniformly distributed, the random variable $C = A + B \text{ mod }m$ is also uniformly distributed (the distribution of $B$ is arbitrary).
I think you can argue that if $B$ has a certain value $b$, then $A + b \text{ mod }m$ is uniformly distributed. Can anyone help me to write this down correctly?
Best Answer
Let us do all calculation with elements of $\{0,...,m-1\}$ modulo $m$. So, for example $-b = m-b$ for such $b$. Notice that $a+b=c$ if and only if $a=c-b$. So, we have $$ \Pr[A+B=c] = \sum_{b=0}^{m-1} \Pr[A=c-b\land B=b] = \sum_{b=0}^{m-1} \Pr[A=c-b] \cdot \Pr[B=b] = $$ $$ \sum_{b=0}^{m-1} \frac{1}{m} \cdot \Pr[B=b] = \frac{1}{m} \sum_{b=0}^{m-1}\Pr[B=b] = \frac{1}{m}~. $$ The second equality follows from independence of $A$ abd $B$. Third equality follows from uniformity of $A$.