Page 520 - Discrete Mathematics and Its Applications

Supplementary Exercises 499

∗ 36. The following method can be used to generate a ran- of the resulting sequence with its r(n − j + 1)st term,
dom permutation of a sequence of n terms. First, in- where r(n − j + 1) is a randomly selected integer with
terchange the nth term and the r(n)th term where r(n) 1 ≤ r(n − j + 1) ≤ n − j + 1. Show that when this
is a randomly selected integer with 1 ≤ r(n) ≤ n. method is followed, each of the n! different permutations
Next, interchange the (n − 1)st term of the result- of the terms of the sequence is equally likely to be gen-
ing sequence with its r(n − 1)st term where r(n − 1) erated. [Hint: Use mathematical induction, assuming that
is a randomly selected integer with 1 ≤ r(n − 1) ≤ the probability that each of the permutations of n − 1
n − 1. Continue this process until j = n, where at terms produced by this procedure for a sequence of n − 1
the jth step you interchange the (n − j + 1)st term terms is 1/(n − 1)!.]

Computer Projects

Write programs with these input and output.

1. Given a real number p with 0 ≤ p ≤ 1, generate random whenapasshasbeenmadewithnointerchanges,counting
numbers taken from a Bernoulli distribution with proba- the number of comparisons used. Determine the average
bility p. number of comparisons used over all m permutations.
2. Given a positive integer n, generate a random permuta- 7. Givenapositiveintegerm,simulatethecollectionofcards
tion of the set {1, 2, 3,...,n}. (See Exercise 36 in the that come with the purchase of products to find the num-
Supplementary Exercises.) ber of products that must be purchased to obtain a full
3. Given positive integers m and n, generate m random per- set of m different collector cards. (See Supplementary
mutations of the first n positive integers. Find the number Exercise 33.)
of inversions in each permutation and determine the av- 8. Given positive integers m and n, simulate the placement
erage number of these inversions. of n keys, where a record with key k is placed at location
4. Given a positive integer n, simulate n repeated flips of h(k) = k mod m and determine whether there is at least
a biased coin with probability p of heads and determine one collision.
the number of heads that come up. Display the cumulative 9. Given a positive integer n, find the probability of select-
results. ing the six integers from the set {1, 2,...,n} that were
5. Given positive integers n and m, generate m random per- mechanically selected in a lottery.
mutations of the first n positive integers. Sort each per- 10. Simulate repeated trials of the Monty Hall Three-Door
mutation using the insertion sort, counting the number problem(Example10inSection7.1)tocalculatetheprob-
of comparisons used. Determine the average number of ability of winning with each strategy.
comparisons used over all m permutations. 11. Given a list of words and the empirical probabilities they
6. Given positive integers n and m, generate m random per- occur in spam e-mails and in e-mails that are not spam,
mutations of the first n positive integers. Sort each permu- determine the probability that a new e-mail message is
tation using the version of the bubble sort that terminates spam.

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. Find the probabilities of each type of hand in five-card 3. Estimate the probability that two integers selected at ran-
poker and rank the types of hands by their probability. dom are relatively prime by testing a large number of
randomly selected pairs of integers. Look up the theorem
2. Find some conditions such that the expected value of buy-
ing a $1 lottery ticket in the New Jersey Pick-6 lottery has that gives this probability and compare your results with
an expected value of more than $1. To win you have to se- the correct probability.
lect the six numbers drawn, where order does not matter,
from the positive integers 1 to 49, inclusive. The winnings 4. Determine the number of people needed to ensure that the
are split evenly among holders of winning tickets. Be sure probability at least two of them have the same day of the
to consider the total size of the pot going into the drawing year as their birthday is at least 70%, at least 80%, at least
and the number of people buying tickets. 90%, at least 95%, at least 98%, and at least 99%.