Page 503 - Discrete Mathematics and Its Applications

482 7 / Discrete Probability

By the linearity of expectations (Theorem 3), it follows that

E(X) = E(X 1 ) + E(X 2 ) + ··· + E(X n ) = n · 1/n = 1.
Consequently, the average number of people who receive the correct hat is exactly 1. Note
that this answer is independent of the number of people who have checked their hats!
(We will find an explicit formula for the probability that no one receives the correct hat in
Example 4 of Section 8.6.) ▲

EXAMPLE 7 Expected Number of Inversions in a Permutation The ordered pair (i, j) is called an
inversion in a permutation of the first n positive integers if i< j but j precedes i in the
permutation. For instance, there are six inversions in the permutation 3, 5, 1, 4, 2; these
inversions are

(1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5).

Let I i,j be the random variable on the set of all permutations of the first n positive integers with
I i,j = 1if (i, j) is an inversion of the permutation and I i,j = 0 otherwise. It follows that if X
is the random variable equal to the number of inversions in the permutation, then

X = I i,j .
1 ≤ i< j ≤ n

Note that it is equally likely for i to precede j in a randomly chosen permutation as it is for j to
precede i. (To see this, note that there are an equal number of permutations with each of these
properties.) Consequently, for all pairs i and j we have

E(I i,j ) = 1 · p(I i,j = 1) + 0 · p(I i,j = 0) = 1 · 1/2 + 0 = 1/2.

n

Because there are pairs i and j with 1 ≤ i< j ≤ n and by the linearity of expectations
2
(Theorem 3), we have

n 1 n(n − 1)
E(X) = E(I i,j ) = · = .
2 2 4
1 ≤ i< j ≤ n
It follows that there are an average of n(n − 1)/4 inversions in a permutation of the first n
positive integers. ▲

Average-Case Computational Complexity

Computing the average-case computational complexity of an algorithm can be interpreted as
computing the expected value of a random variable. Let the sample space of an experiment be
the set of possible inputs a j , j = 1, 2,...,n, and let X be the random variable that assigns
to a j the number of operations used by the algorithm when given a j as input. Based on our
knowledge of the input, we assign a probability p(a j ) to each possible input value a j . Then,
the average-case complexity of the algorithm is

n

E(X) = p(a j )X(a j ).
j=1

This is the expected value of X.