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
    Mar 4 '16 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
    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$.


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.


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.