Let $X_i$ be i.i.d. random variables on $\{1,\dots,d\},d\in \mathbb N$.

What is the best way to analytically treat

$$\left(\sum_{k=1}^{n} X_k \right ) \mod d$$

Is there a general recipe to get rid of the modulo $d$ condition?

For example, how would one calculate the weak limit of the above expression as $n\mapsto \infty$?


A tool to keep in mind when modulo are involved is discrete Fourier transform. Here, one considers $U=\{z\in\mathbb C\mid z^d=1\}$ the set of the $d$th roots of $1$, and the transform $g_X:U\to\mathbb C$ defined by $$g_X(z)=\mathbb E(z^X)=\sum\limits_{k=1}^d\mathbb P(X=k)z^k$$ Then, $g_X$ characterizes the distribution of $X$ since, for every $1\leqslant k\leqslant d$, $$ \mathbb P(X=k)=\frac1d\sum_{z\in U}z^{-k}g_X(z) $$ In a special case, things are even simpler, using the following result:

Factoid: For every independent $X$ and $Y$, if $X$ is uniformly distributed modulo $d$ then $X+Y$ is uniformly distributed modulo $d$ as well.

In your case, as soon as even only one random variable $X_m$ is uniformly distributed modulo $d$, every sum $\sum\limits_{k=1}^nX_k$ such that $n\geqslant m$, is uniformly distributed modulo $d$.

To prove the factoid above, the elementary approach works but one can also note that $X$ is uniformly distributed modulo $d$ if and only if $g_X(1)=1$ and $g_X(z)=0$ for every $z\ne1$ in $U$. Since $g_{X+Y}=g_X\cdot g_Y$ for independent $(X,Y)$ and $g_Y(1)=1$ for every $Y$, the same holds for $g_{X+Y}$, that is, $g_{X+Y}(1)=1$ and $g_{X+Y}(z)=0$ for every $z\ne1$ in $U$. Thus, $X+Y$ is uniformly distributed modulo $d$, QED.

In the general case, if $(X_k)$ is i.i.d. and distributed like $X$, one notes that $g_{X_1+\cdots+X_n}=(g_X)^n$. Thus $g_{X_1+\cdots+X_n}(1)=1$. For every $z$ in $U$, $|g_X(z)|\leqslant1$. Assume that $|g_X(z)|\lt1$ or every $z\ne1$ in $U$. Then $g_{X_1+\cdots+X_n}(z)\to0$ for every $z\ne1$ in $U$, that is, $g_{X_1+\cdots+X_n}\to g_Y$, where $Y$ is uniformly distributed modulo $d$, hence:

$X_1+\cdots+X_n$ converges in distribution to the distribution uniform modulo $d$.

The exception is when $|g_X(z)|=1$ for some $z\ne1$ in $U$. This implies that $z^X$ is almost surely constant, that is, that $jX$ is constant modulo $d$, for some $1\leqslant j\leqslant d-1$ (consider for example $d=6$ and $\mathbb P(X\in\{0,2,4\})=1$). But, if $\mathbb P(X=k)\ne0$ for every $1\leqslant k\leqslant d$, this cannot happen.


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.