Random number function (counting)

Question

I have task I can't get my head around, even with a suggested answer.

You have a function the generates a random integer between $0 - 65535$. Your task is to generate random integers $125-525$ with this function, these numbers must be generated with equal prevalence.

A friend said his solution was $\frac{x}{65536} * 401 + 125$ but I don't understand how he got there nor the answer in general.

---

EDIT: NB: If you have a solution for the number 65535, please provide, what we have here is a reformulation of the question to 65363 integers (65362 for even 401 divide).

$a_1 = 0$
$b_1 = 65362$
$X = b_1-a_1$
$Y=\frac{X}{163}+125$

if x = 65362 the output is 525  
if x = 0 the output is 125

This looks like a solution to me.

Answer 1

I will expand on my comment.

If we simply try scaling the random number from $0$-$65535$ into the range $125$-$525$, then the resulting distribution will not be uniform. For example, $\left\lfloor\frac{401n}{65536}\right\rfloor+125$ would be the closest one can get to scaling the distribution evenly. However, $$ \begin{array}{rlr} [0,163]&\mapsto&125&\frac{164}{65536}\\ [164,326]&\mapsto&126&\frac{163}{65536}\\ [327,490]&\mapsto&127&\frac{164}{65536}\\ [491,653]&\mapsto&128&\frac{163}{65536}\\ [654,817]&\mapsto&129&\frac{163}{65536}\\ &\vdots \end{array} $$ Thus, we see that $125$ with a probability of $\frac{164}{65536}$ is more likely than $126$ with a probability of $\frac{163}{65536}$, etc.

To get a truly uniform distribution by scaling, we need to draw our initial random numbers from a pool that is distributed over a range that is a multiple of the range we want. Since we have random numbers that are from $0$-$65535$, we can use those to get a uniform distribution from $0$-$65362$ by discarding anything greater than $65362$. This only happens with probability $$ \frac{65536-65362}{65536}=\frac{174}{65536}\doteq0.002655 $$ that is, not very frequently. Now if we take the numbers from $0$-$65362$ and put them through the function $$ \left\lfloor\frac{n}{163}\right\rfloor+125 $$ we will get a uniform distribution on $125$-$525$ since $163\cdot401=65363$. That is, $$ \begin{array}{rlr} [0,162]&\mapsto&125&\frac{163}{65363}=\frac1{401}\\ [163,325]&\mapsto&126&\frac{163}{65363}=\frac1{401}\\ [326,488]&\mapsto&127&\frac{163}{65363}=\frac1{401}\\ [489,651]&\mapsto&128&\frac{163}{65363}=\frac1{401}\\ [652,814]&\mapsto&129&\frac{163}{65363}=\frac1{401}\\ &\vdots \end{array} $$

Answer 2

Hint:
Let $X$ be a random number which is uniformly (evenly) distributed between $a_1$ and $b_1$. Now, let's define $Y = \frac{X-a_1}{b_1 - a_1}$, what can we infer about the distribution of $Y$?
(What is smallest possible value of $Y$? What is largest possible value of $Y$? Why?)

What if I'm interested in another variable $Z$ (possibly a function of $X$ or $Y$) being between some other numbers $\left[a_2, b_2\right]$? How might we change the process above?

Answer 3

One way you can think about this question is as follows. You need to generate the integers between $125$ and $525$, that is $401$ numbers, with equal prevalence. Parition the interval $[0,65535]$ into $401$ equally spaced bins. The $i$th bin is $[x_i, x_{i+1})$ for $i = 0,\ldots,400$ where $x_i = i\Delta x$ for $i = 0,\ldots,401$ and $\Delta x = 65536/401$ is the spacing of each bin. Note that I use $65536$ as the right endpoint of the last bin so that every bin is open on the right. Using equal bin spacing there is very nearly the same number of integers in each bin. Note that there will be a small amount of bias since $401$ does not divide $65536$ evenly. Now if $x$ is a uniformly distributed random number between $0$ and $65535$, then it belongs to one of these bins. That is $x_i \leq x < x_{i+1}$ for some $0 \leq i \leq 400$. Using the formula for $x_i$ you should be able to calculate the exact value of $i$. Once you know $i$ you should select the $i$th integer between $125$ and $525$, that is, the integer $125 + i$.

Answer 4

If your generator is fast and you do not need many random numbers, you could just generate random numbers between 0 and 65535 and keep only the ones that are in the range you want.