Randomization - Data Structures and Problem Solving Using Java - page 416

drawn from the range M - 1. It then generates a random integer in the
range 1 to M . If the random integer is not already in the permutation
we add it; otherwise, we add M .
a. Prove that this algorithm does not add duplicates.

b. Prove that each permutation is equally likely.

c. Give a recursive implementation of the algorithm.

d. Give an iterative implementation of the algorithm.

A random walk in two dimensions is the following game played on
the x-y coordinate system. Starting at the origin (0, 0), each itera-
tion consists of a random step either 1 unit left, up, right, or down.
The walk terminates when the walker returns to the origin. (The
probability of this happening is 1 in two dimensions but less than 1
in three dimensions.) Write a program that performs 100 indepen-
dent random walks and computes the average number of steps taken
in each direction.

9.15

A simple and effective statistical test is the chi-square test . Suppose
that you generate N positive numbers that can assume one of M val-
ues (for example, we could generate numbers between 1 and M ,
inclusive). The number of occurrences of each number is a random
variable with mean . For the test to work, you should have
. Let be the number of times i is generated. Then compute
the chi-square value . The result should be close
to M . If the result is consistently more than away from M (i.e.,
more than once in 10 tries), then the generator has failed the test.
Implement the chi-square test and run it on your implementation of
the nextInt method (with low = 1 and high = 100).

9.16

μ = N ⁄ M

μ > 10 f i

V =

∑

( f i - μ ) ⁄ μ

2

2 M

In class Random48 , the low b bits of state cycle with period 2 b .
a.

9.17

What is the period of zero-parameter nextInt ?

Show that one-parameter nextInt will then cycle with a length 2 16 N
if is invoked with N that is a power of 2.

b.

Modify nextInt to detect if N is a power of 2 and if so, use the high
order bits of state , rather than the low order bits.

c.

In class Random48 , suppose one-parameter nextInt invokes zero-parameter
nextInt instead of nextLong (and cleans up the corner case concerning
Math.abs(Integer.MIN_VALUE) ).
a.

9.18

Show that in that case, if N is very large then some remainders are
significantly more likely to occur than others. Consider, for instance
N = 2 30 + 1.

b. Suggest a remedy to the above problem.

c. Does the same situation occur when we invoke nextLong ?