ISYE 6644 MIDTERM EXAM QUESTIONS AND
ANSWERS SET A+
✔✔Which property is not desirable for a good pseudo-random number generator? -
✔✔We must be able to look up the series of PRNs from a table.
Good pseudo-random number genator
- The numbers must appear to be Unif(0,1)
- The numbers are approximately independent
- We should we able to generate the PRNs very, very quickly
- We can reproduce any sequence of PRNs if called upon to do so
✔✔Which of the following PRNs generators aren't very good? - ✔✔- Generators
involving physical devices such as coin flips or at least significant digit readings from an
atomic clock
- Random number tables
- von Neumann's mid-square method
- Fibonacci and additive congruential generators
✔✔Consider the generator Xi = (5Xi-1 + 3)mod8, and suppose that the sequence is
initialized with X0= 3. Find X2. - ✔✔X1 = (5X0 + 3)mod8 = 18mod8 = 2
X2 = (5X1 +3)mod8 = 13mod8 = 5
✔✔Consider the generator Xi = (5Xi-1 + 3)mod8, and suppose that the sequence is
initialized with X0= 3. Find X8 - ✔✔We know that this is a full-period generator with a
cycle length of 8. Therefore, X0 = X8 = 3
✔✔True or False? (1 XOR 1) XOR 1 = 1 - ✔✔1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
Therefore, 0 XOR 1 = 1, True
, ✔✔Consider a Tausoworthe generator that produces the bits 1,1,0,1,1. Calculate the
resulting pesudo-random number obtained by transforming these 5 bits from base 2 to
base 10, ie, (11011)_^5, where (x)_2 denotes a number x in base 2. - ✔✔(1 1 0 1
1)_2
From right to left:
= 1*2^0 + 1*2^1 + 0*2^2 + 1*2^3 + 1*2^4
= 1 + 2 + 0 + 8 + 16
= 27
= (11011)_^5
= 27/32
✔✔True or False? There are good PRN generators out there having incredible cycle
lengths of over 2^100 - ✔✔True
In fact, the L'Ecuyer generator that we discussed has a period of around 2^191, and the
Mersenne Twister chimes in at 2^19937
✔✔True or False? RANDU is a pretty good generator - ✔✔False
RANDU has severe problems with hyperplanes.
✔✔True or False? a = P(Reject H0 | H0 is true) is the probability of a Type 1 error -
✔✔True
✔✔In the context of evaluating a PRN generator, which kinds of statistical tests are we
interested in? - ✔✔-Goodness-of-fit tests
- Independence tests
✔✔If the x^2 goodness-of-fit statistic, x^2_0, is much greater than the relevant quantile
x^2a,k-1, what do we do? - ✔✔Reject the goodness-of-fit test and declare that the
PRNs are probably not uniform
✔✔Consider the following sequence of PRNs.
0.15 0.85 0.23 0.36 0.42 0.49 0.66 0.70 0.80 0.89 0.97 0.85
How many runs "up and down" are there? - ✔✔Here is what the run results from the 12
PRNS look like:
+-+++++++++-
Thus, there are 4 runs.
ANSWERS SET A+
✔✔Which property is not desirable for a good pseudo-random number generator? -
✔✔We must be able to look up the series of PRNs from a table.
Good pseudo-random number genator
- The numbers must appear to be Unif(0,1)
- The numbers are approximately independent
- We should we able to generate the PRNs very, very quickly
- We can reproduce any sequence of PRNs if called upon to do so
✔✔Which of the following PRNs generators aren't very good? - ✔✔- Generators
involving physical devices such as coin flips or at least significant digit readings from an
atomic clock
- Random number tables
- von Neumann's mid-square method
- Fibonacci and additive congruential generators
✔✔Consider the generator Xi = (5Xi-1 + 3)mod8, and suppose that the sequence is
initialized with X0= 3. Find X2. - ✔✔X1 = (5X0 + 3)mod8 = 18mod8 = 2
X2 = (5X1 +3)mod8 = 13mod8 = 5
✔✔Consider the generator Xi = (5Xi-1 + 3)mod8, and suppose that the sequence is
initialized with X0= 3. Find X8 - ✔✔We know that this is a full-period generator with a
cycle length of 8. Therefore, X0 = X8 = 3
✔✔True or False? (1 XOR 1) XOR 1 = 1 - ✔✔1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
Therefore, 0 XOR 1 = 1, True
, ✔✔Consider a Tausoworthe generator that produces the bits 1,1,0,1,1. Calculate the
resulting pesudo-random number obtained by transforming these 5 bits from base 2 to
base 10, ie, (11011)_^5, where (x)_2 denotes a number x in base 2. - ✔✔(1 1 0 1
1)_2
From right to left:
= 1*2^0 + 1*2^1 + 0*2^2 + 1*2^3 + 1*2^4
= 1 + 2 + 0 + 8 + 16
= 27
= (11011)_^5
= 27/32
✔✔True or False? There are good PRN generators out there having incredible cycle
lengths of over 2^100 - ✔✔True
In fact, the L'Ecuyer generator that we discussed has a period of around 2^191, and the
Mersenne Twister chimes in at 2^19937
✔✔True or False? RANDU is a pretty good generator - ✔✔False
RANDU has severe problems with hyperplanes.
✔✔True or False? a = P(Reject H0 | H0 is true) is the probability of a Type 1 error -
✔✔True
✔✔In the context of evaluating a PRN generator, which kinds of statistical tests are we
interested in? - ✔✔-Goodness-of-fit tests
- Independence tests
✔✔If the x^2 goodness-of-fit statistic, x^2_0, is much greater than the relevant quantile
x^2a,k-1, what do we do? - ✔✔Reject the goodness-of-fit test and declare that the
PRNs are probably not uniform
✔✔Consider the following sequence of PRNs.
0.15 0.85 0.23 0.36 0.42 0.49 0.66 0.70 0.80 0.89 0.97 0.85
How many runs "up and down" are there? - ✔✔Here is what the run results from the 12
PRNS look like:
+-+++++++++-
Thus, there are 4 runs.
