I'm in process of learning 'gap test' for random numbers in discrete event system simulation. I happened to have the fourth edition of this book by Jerry Banks. Unfortunately , this edition doesn't have any info about this test. I'm trying to learn more of it from the net but details are very scarce. So, can anyone please explain me this test in detail.
[Math] gap test for random numbers
random
Related Solutions
So if I interpret your question correctly, you've got an uniformly distributed random natural number in the range $[0,256)$ and want to obtain an uniformly random number in the range $[0,200)$.
As you've observed, just taking the number modulo $200$ doesn't work, since the numbers below $56$ will be obtained twice as often that way.
The simplest way to do it is to simply throw away anything $\ge 200$ and try again. If you consider that too wasteful, you can also store the excess value and use it for the next try. So a less wasteful algorithm would be (where drawn numbers are always single-byte numbers):
- First, you draw a random number $r_1$.
- If $r_1 < 200$, you just return it.
- Otherwise you draw a second number $r_2$ and calculate $s = 256*(r_1 - 200) + r_2$. Now $s$ is uniformly distributed in the integers of the range $[0,14336)$.
- If $s < 14200$, you return $s \bmod 200$. Otherwise, you start over.
As you see, the probability of not succeeding after the second draw is extremely low. You could, of course, repeat this process instead of starting over (the remainder here is in the range $[0,136)$ so the chance in the third try is even larger).
Also, when returning a number from the second step, you're wasting the quotient part (in the range $[0,72)$; you might want to save that for later trials.
If my calculations are correct, the normalizing constant is $c \left( \varepsilon_{\max}, \bar{E} \right) = \bar{E} \arctan \left( \frac{\varepsilon_{\max}}{\bar{E}} \right)$, the CDF is $F \left( \varepsilon_s \right) = \frac{\arctan \left( \frac{\varepsilon_s}{\bar{E}} \right)}{\arctan \left( \frac{\varepsilon_{\max}}{\bar{E}} \right)}$ and thus the inverse CDF is $$ \varepsilon_s = F^{- 1} \left( u \right) = \bar{E} \tan \left( \arctan \left( \frac{\varepsilon_{\max}}{\bar{E}} \right) u \right) $$ Thus draw a uniform number on $[0,1]$, set it to $u$ and compute the random draw $\varepsilon_s$ from it using the function $F^{-1}$.
Best Answer
Try section 5.3 Gap Test, which contains a worked example, and also Section 3. for an alternate description.
I would still recommend getting your hands on Knuth - The Art of Computer Programming. Vol. 2: Seminumerical Algorithms.
Also, I would recommend looking into DIEHARDERs and TestU01s implementations of these tests since both provide actual working code (and there are certainly other variants out there, but those two are heavily used).
Regards