0
$\begingroup$

Suppose i have a uniform random number generator which generates integers uniformly over some range [x,y]

The output obtained z, can be binned into p buckets via: z mod p

if p were prime, are the number of elements in each bucket expected to be the same? what if p were not prime?

i expect that the number of elements in each bucket should be the same if p is prime or now. since each remainder should be equally probable?

$\endgroup$
  • 1
    $\begingroup$ consider $p=2$ with $x=1, y=3$. $\endgroup$ – Thomas Andrews Dec 11 '14 at 18:34
3
$\begingroup$

Prime doesn't matter to this question. You will have $y-x+1$ successive numbers. If $p$ divides $y-x+1$ you will have the same number in each bucket. Otherwise you will have some buckets with one more than other buckets. The number of larger buckets will be $y-x+1 \pmod p$

$\endgroup$
0
$\begingroup$

Primality of $p$ does not really matter.

In your range, you have $y-x+1$ consecutive integers (I assume that $x,y$ are integers).

If $p$ divides $y-x+1$, it is not hard to see that each remainder modulo $p$ occurs exactly $(y-x+1)/p$ times, so probability will be uniform.

Otherwise, some of them will occur slightly more or less often (less than one more or one less), and the probability will be slightly different (but by a very, very small margin if $y-x$ is much larger than $p$).

$\endgroup$

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.