What is the distribution of the modulo of a uniformly-distributed random variable

Question

This feels like something that's easy to answer, but maybe not. (For the record, this isn't homework from school, it's to settle an argument I'm having with a colleague.)

I have a random variable $X$ that's a value in $K = [0, 2^{64})$. Given that $X$ is uniformly distributed over $K$ (that is, the probability density function of $X$ is $f(x) = \frac{1}{2^{64}}$), what is the distribution of $Y = X \bmod k$?

My gut says it's uniformly distributed over $M = [0, k)$ (i.e., the pdf of $Y$ is $f(y)=\frac{1}{k}$) but I can't quite sort the math to get me there.

Answer 1

Your gut is right in the limit of $n \to \infty$ in $K = [0,2^n)$ but slightly wrong for finite $n$ (which is $64$ as posed in the question). (Which is why you are having trouble proving the uniform distribution -- it is not quite true.)

The point is that up and not including to $\left \lfloor \frac{2^{64}}k \right\rfloor$ there are an equal number of instances of each value of $Y$. But in the interval $\left \lfloor \frac{2^{64}}k \right\rfloor \leq k < 2^{64}$ there is one instance of each number $n : 0 \leq n < 2^{64} - \left \lfloor \frac{2^{64}}k \right\rfloor$ and no instances equal to or greater than $ 2^{64} - \left \lfloor \frac{2^{64}}k \right\rfloor$.

So the distribution looks almost uniform; it is flat up to $2^{64} -\left \lfloor \frac{2^{64}}k \right\rfloor$ then takes a tiny step downward and remains flat thereafter. But that is not a uniform distribution.

Answer 2

It is not uniform unless $k$ is power of $2$. For example, if you replace $64$ with $2$ and take $k = 3$, you get $P(Y \in [0, 1)) = \frac{1}{2}$, but $P(Y \in [1, 2)) = P(Y = [2, 3)) = \frac{1}{4}$.

If $k$ is power of $2$ let $n = \frac{2^{64}}{k}$. We have $P(Y \in [0, x)) = P(X \in [0, x)) + P(X \in [k, k + x)) + \ldots + P(X \in [(n - 1)k, (n - 1)k + x))$.

Each term is equal to $\frac{x}{2^{64}}$, and there are total of $n$ of them, so sum is $\frac{x}{k}$.