2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Since you are reducing $65536$ possibilities to $401$ possibilities, if we simply try to do it by scaling and translating, we won't get a uniform distribution. There will be some values whose probability will be $\frac{164}{163}$ more likely than the others. This is because $163\cdot401\lt65536\lt164\cdot401$. Instead what can be done is to discard all the random numbers above $65362$ and for those from $0$ to $65362$, divide them by $163$, then add $125$ to the integer part of the quotient. (The key here is that $65363=163\cdot401$.) $\endgroup$ – robjohn Aug 27 '15 at 15:19
  • $\begingroup$ I like the idea of reformulating the question in order to gain an accurate solution. $\endgroup$ – Manumit Aug 27 '15 at 17:49
  • $\begingroup$ @robjohn if you could put your comment as answer I'd like to approve it as it furthered my understanding the most. $\endgroup$ – Manumit Aug 27 '15 at 19:10
  • $\begingroup$ I was actually writing that up and then got drawn away for a business lunch. I have expanded on my comment in an answer. $\endgroup$ – robjohn Aug 27 '15 at 20:16
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ One last thing, Rob. How can we explain the move from 65363 to 65362? It's obvious that 65363/163 +125 = 526, but why then does 163*401 give us that extra digit and not 65362? $\endgroup$ – Manumit Aug 28 '15 at 16:56
  • $\begingroup$ There are $65363=401\cdot163$ integers from $0$ to $65362$. That means we can evenly divide the integers from $0$ to $65362$ into $401$ equal groups, just right to match the $401$ values from $125$ to $525$. $\endgroup$ – robjohn Aug 28 '15 at 17:01
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hi, James. I'm a freshman with little to no training in mathematical symbols so your educational rhetoric's need simplification :) $\endgroup$ – Manumit Aug 27 '15 at 14:58
  • $\begingroup$ @Manumit, is that better? $\endgroup$ – jameselmore Aug 27 '15 at 15:02
  • $\begingroup$ perfect! I'm going through it now, will update. $\endgroup$ – Manumit Aug 27 '15 at 15:08
  • $\begingroup$ 5 000 000 000/65536 = 76294 isn't that an illegal value? i have to will look further into this tonight $\endgroup$ – Manumit Aug 27 '15 at 15:32
  • $\begingroup$ Really, really confused on where this $5$ billion number came from. Remember that $X$ cannot exceed $b_1$ (or 525 in your case) $\endgroup$ – jameselmore Aug 27 '15 at 17:07
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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