Page 505 - Discrete Mathematics and Its Applications

484 7 / Discrete Probability

We let X i be the random variable equal to the number of comparisons used to insert a i into
the proper position after the first i − 1 elements a 1 ,a 2 ,...,a i−1 have been sorted. Because

X = X 2 + X 3 + ··· + X n ,

we can use the linearity of expectations to conclude that

E(X) = E(X 2 + X 3 + ··· + X n ) = E(X 2 ) + E(X 3 ) + ··· + E(X n ).

To find E(X i ) for i = 2, 3,...,n, let p j (k) denote the probability that the largest of the
first j elements in the list occurs at the kth position, that is, that max(a 1 ,a 2 ,...,a j ) = a k ,
where 1 ≤ k ≤ j. Because the elements of the list are randomly distributed, it is equally likely
for the largest element among the first j elements to occur at any position. Consequently,
p j (k) = 1/j.If X i (k) equals the number of comparisons used by the insertion sort if a i is
inserted into the kth position in the list once a 1 ,a 2 ,...,a i−1 have been sorted, it follows
that X i (k) = k. Because it is possible that a i is inserted in any of the first i positions, we
find that

i i i
1 1 1 i(i + 1) i + 1
E(X i ) = p i (k) · X i (k) = · k = · k = · = .
i i i 2 2
k=1 k=1 k=1
It follows that

n n n+1
i + 1 1
E(X) = E(X i ) = = j
2 2
i=2 i=2 j=3
2
1 (n + 1)(n + 2) 1 n + 3n − 4
= − (1 + 2) = .
2 2 2 4
To obtain the third of these equalities we shifted the index of summation, setting j = i + 1.
m
To obtain the fourth equality, we used the formula k = m(m + 1)/2 (from Table 2 in
k=1
Section 2.4) with m = n + 1, subtracting off the missing terms with j = 1 and j = 2. We
conclude that the average number of comparisons used by the insertion sort to sort n elements
2
2
equals (n + 3n − 4)/4, which is (n ). ▲

The Geometric Distribution

We now turn our attention to a random variable with infinitely many possible outcomes.
EXAMPLE 10 Suppose that the probability that a coin comes up tails is p. This coin is flipped repeatedly until
it comes up tails. What is the expected number of flips until this coin comes up tails?

Solution: We first note that the sample space consists of all sequences that begin with any
number of heads, denoted by H, followed by a tail, denoted by T . Therefore, the sam-
ple space is the set {T, HT, HHT, HHHT, HHHHT,...}. Note that this is an infinite sample
space. We can determine the probability of an element of the sample space by noting that
the coin flips are independent and that the probability of a head is 1 − p. Therefore, p(T ) = p,
2
p(HT ) = (1 − p)p, p(HHT)= (1 − p) p, and in general the probability that the coin is flipped
ntimesbeforeatailcomesup,thatis,thatn − 1headscomeupfollowedbyatail,is(1 − p) n−1 p.
(Exercise 14 asks for a verification that the sum of the probabilities of the points in the sample
space is 1.)