0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. This is the difference between math and engineering - to an engineer, this is close enough to uniform for our purposes. $\endgroup$ – Cubs Fan Ron Apr 18 at 15:51
  • $\begingroup$ (I say that because $k \ll 2^{64}$, nominally 1000.) $\endgroup$ – Cubs Fan Ron Apr 18 at 15:52
  • $\begingroup$ 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. $\endgroup$ – Cubs Fan Ron Apr 18 at 17:01
0
$\begingroup$

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

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

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.