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

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.

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.

• Thanks for the explanation. This is the difference between math and engineering - to an engineer, this is close enough to uniform for our purposes. – Cubs Fan Ron Apr 18 at 15:51
• (I say that because $k \ll 2^{64}$, nominally 1000.) – Cubs Fan Ron Apr 18 at 15:52
• Is it better to say this is a bimodal distribution where $$f(y) = \left\{\begin{array}{@{}lr@{}} \left\lceil\frac{2^{64}}{k}\right\rceil, & 0\le y \lt (2^{64}\bmod {k),}\\ \left\lfloor\frac{2^{64}}{k}\right\rfloor, & (2^{64}\bmod k) \le y \lt k \end{array}\right\}$$ I'm questioning the word bimodal but I think the above function accurately describes the pdf. – Cubs Fan Ron Apr 18 at 17:01

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

• Good point on the $k = 2 ^ m$. – Cubs Fan Ron Apr 18 at 16:14