Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
