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

Suppose that you have a biased coin that comes up heads with
probability p and tails with probability 1 - p . Show how to design
an algorithm that uses the coin to generate a 0 or 1 with equal
probability.

9.7

IN PRACTICE
9.8

Write a program that calls nextInt (that returns an int in the specified
interval) 100,000 times to generate numbers between 1 and 1,000.
Does it meet the stronger statistical tests given in Section 9.2?

Run the Poisson generator shown in Figure 9.5 1,000,000 times,
using an expected value of 2. Does the distribution agree with
Figure 9.4?

9.9

Consider a two-candidate election in which the winner received a frac-
tion p of the vote. If the votes are counted sequentially, what is the
probability that the winner was ahead (or tied) at every stage of the
election? This problem is the so-called ballot problem . Write a pro-
gram that verifies the answer, , assuming that and that large
numbers of votes are the case. ( Hint : Simulate an election of 10,000
voters. Generate random arrays of 10,000 p ones and 10,000(1 - p )
zeros. Then verify in a sequential scan that the difference between 1s
and 0s is never negative.)

9.10

---

1
---

-

2 p >

In the one-parameter Random constructor in Figure 9.2, why do we not
simply write initialValue+=(M+1); ?

9.11

In class Random48 , prove that nextLong does not return all possible long
values.

9.12

PROGRAMMING PROJECTS
9.13

An alternative permutation algorithm is to fill the array a from a[0]
to a[n-1] , as follows. To fill a[i] , generate random numbers until
you get one that has not been used previously. Use an array of Bool-
eans to perform that test. Give an analysis of the expected running
time (this is tricky) and then write a program that compares this run-
ning time with both your analysis and the routine shown in
Figure 9.7.

Suppose that you want to generate a random permutation of N distinct
items drawn from the range 1, 2, ..., M . (The case M = N , of course,
has already been discussed.) Floyd's algorithm does the following.
First, it recursively generates a permutation of N - 1 distinct items

9.14