Page 514 - Discrete Mathematics and Its Applications

7.4 Expected Value and Variance 493

28. What is the variance of the number of times a 6 appears 39. Suppose that the number of tin cans recycled in a day at
when a fair die is rolled 10 times? a recycling center is a random variable with an expected
29. Let X n be the random variable that equals the number value of 50,000 and a variance of 10,000.
of tails minus the number of heads when n fair coins are a) Use Markov’s inequality (Exercise 37) to find an up-
flipped. per bound on the probability that the center will recy-
a) What is the expected value of X n ? cle more than 55,000 cans on a particular day.
b) What is the variance of X n ?
b) Use Chebyshev’s inequality to provide a lower bound
30. Show that if X and Y are independent random on the probability that the center will recycle 40,000
2 2
variables, then V(XY) = E(X) V(Y) + E(Y) V(X) + to 60,000 cans on a certain day.
V(X)V(Y) ∗ 40. Suppose the probability that x is the ith element in a list
31. Let A(X) = E(|X − E(X)|), the expected value of the of n distinct integers is i/[n(n + 1)]. Find the average
absolute value of the deviation of X, where X is a number of comparisons used by the linear search algo-
random variable. Prove or disprove that A(X + Y) = rithm to find x or to determine that it is not in the list.
A(X) + A(Y) for all random variables X and Y.
∗
32. Provide an example that shows that the variance of the 41. In this exercise we derive an estimate of the average-case
sum of two random variables is not necessarily equal to complexity of the variant of the bubble sort algorithm
the sum of their variances when the random variables are that terminates once a pass has been made with no inter-
not independent. changes. Let X be the random variable on the set of per-
33. Suppose that X 1 and X 2 are independent Bernoulli mutations of a set of n distinct integers {a 1 ,a 2 ,...,a n }
with a 1 <a 2 < ··· <a n such that X(P) equals the num-
trials each with probability 1/2, and let X 3 =
(X 1 + X 2 ) mod 2. ber of comparisons used by the bubble sort to put these
integers into increasing order.
a) Show that X 1 , X 2 , and X 3 are pairwise independent,
but X 3 and X 1 + X 2 are not independent. a) Show that, under the assumption that the input is
equally likely to be any of the n! permutations of these
b) Show that V(X 1 + X 2 + X 3 ) = V(X 1 ) + V(X 2 ) +
V(X 3 ). integers, the average number of comparisons used by
c) Explain why a proof by mathematical induction of the bubble sort equals E(X).
Theorem 7 does not work by considering the random b) Use Example 5 in Section 3.3 to show that E(X) ≤
variables X 1 , X 2 , and X 3 . n(n − 1)/2.
∗ 34. Prove the general case of Theorem 7. That is, show that
c) Show that the sort makes at least one comparison for
if X 1 , X 2 ,...,X n are pairwise independent ran-
every inversion of two integers in the input.
dom variables on a sample space S, where n is
d) Let I(P) be the random variable that equals the num-
a positive integer, then V(X 1 + X 2 + ··· + X n ) =
V(X 1 ) + V(X 2 ) + ··· + V(X n ).[Hint: Generalize the ber of inversions in the permutation P. Show that
proof given in Theorem 7 for two random variables. Note E(X) ≥ E(I).
that a proof using mathematical induction does not work;
e) Let I j,k be the random variable with I j,k (P) = 1if a k
see Exercise 33.]
precedes a j in P and I j,k = 0 otherwise. Show that
35. Use Chebyshev’s inequality to find an upper bound on the I(P) = j<k j,k (P).
I
k
probability that the number of tails that come up when a

fair coin is tossed n times deviates from the mean by more f) Show that E(I) = k j<k E(I j,k ).
√
than 5 n.
g) Show that E(I j,k ) = 1/2. [Hint: Show that E(I j,k ) =
36. Use Chebyshev’s inequality to find an upper bound on the probability that a k precedes a j in a permutation P.
probability that the number of tails that come up when a Then show it is equally likely for a k to precede a j as
biased coin with probability of heads equal to 0.6 is tossed it is for a j to precede a k in a permutation.]
√
n times deviates from the mean by more than n.
h) Use parts (f) and (g) to show that E(I) = n(n − 1)/4.
37. Let X be a random variable on a sample space
S such that X(s) ≥ 0 for all s ∈ S. Show that i) Conclude from parts (b), (d), and (h) that the aver-
p(X(s) ≥ a) ≤ E(X)/a for every positive real num- age number of comparisons used to sort n integers is
2
ber a. This inequality is called Markov’s inequality. (n ).
38. Suppose that the number of cans of soda pop filled in a day ∗ 42. In this exercise we find the average-case complexity of
at a bottling plant is a random variable with an expected the quick sort algorithm, described in the preamble to Ex-
value of 10,000 and a variance of 1000. ercise 50 in Section 5.4, assuming a uniform distribution
a) Use Markov’s inequality (Exercise 37) to obtain an on the set of permutations.
upper bound on the probability that the plant will fill a) Let X be the number of comparisons used by the quick
more than 11,000 cans on a particular day. sort algorithm to sort a list of n distinct integers. Show
b) Use Chebyshev’s inequality to obtain a lower bound that the average number of comparisons used by the
on the probability that the plant will fill between 9000 quick sort algorithm is E(X) (where the sample space
and 11,000 cans on a particular day. is the set of all n! permutations of n integers).