# Sum modulo of two random variables with one uniformly distributed

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?

• The setup seems slightly off: do you have 0 mod m = m mod m = 0? Or do you mean that they are distributed on $\{ 0,\dots,m-1 \}$, or $\{ 1,\dots,m \}$?
– Ian
Mar 4 '16 at 17:55
• If $B$ is a constant rv that takes value $1$ and $A$ has uniform distribution over $\{0,1,\dots,m\}$ then $P(C=1\text{ mod }m)=P(A=0)+P(A=m)=\frac2{m+1}$ and $P(C=i\text{ mod }m=\frac1{m+1}$ for $i\neq1$. So no uniform distribution for $C$. Mar 4 '16 at 18:30

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$$.
$$P(A+B=k\text{ mod }m)=\sum_{i=0}^{m}P(A+i=k\text{ mod }m)P(B=i)$$
If for each $i$ we have $P(A+i=k\text{ mod }m)=c$ where $c$ is a constant then the RHS equals $c$.
If is in bold because I have doubts about the setup of your question. I would expect $A$ and $B$ to take values in $\{0,\dots,m-1\}$ or in $\{1,\dots,m\}$. See my comment on that.