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?

  • 1
    $\begingroup$ 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 \}$? $\endgroup$
    – Ian
    Commented Mar 4, 2016 at 17:55
  • $\begingroup$ 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$. $\endgroup$
    – drhab
    Commented Mar 4, 2016 at 18:30

2 Answers 2


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$.


A constant probability mass function stands for uniformity. By independence we find:

$$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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .