5.2-1

In $\text{HIRE-ASSISTANT}$, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability you hire exactly $n$ times?

You will hire exactly one time if the best candidate is at first. There are $(n − 1)!$ orderings with the best candidate being at first, so the probability that you hire exactly one time is $\frac{(n - 1)!}{n!} = \frac{1}{n}$.

You will hire exactly $n$ times if the candidates are presented in increasing order. There is only an ordering for this situation, so the probability that you hire exactly $n$ times is $\frac{1}{n!}$.

5.2-2

In $\text{HIRE-ASSISTANT}$, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?

Since the first candidate is always hired, we need to compute the probability that that exactly one additional candidate is hired.

Since we view the candidate ranking as reading an random permutation, this is equivalent to the probability that a random permutation is a decreasing sequence followed by an increase, followed by another decreasing sequence.

The permutation can be thought as a partition of $[n]$ into 2 parts. One of size $k$ and the other of size $n − k$, where $1 \le k \le n − 1$. For each such partition, we obtain a permutation with a single increase by ordering the numbers each partition in decreasing order, then concatenating these sequences. The only thing that can go wrong is if the numbers $n$ through $n − k + 1$ are in the first partition. Thus there are $\binom{n}{k} - 1$ permutations which correspond to hiring the second and final person on step $k + 1$. Summing, we see that the probability you hire exactly twice is

$$\frac{\sum_{k = 1}^{n - 1}\binom{n}{k} - 1}{n!} = \frac{2^n - 2 - (n - 1)}{n!} = \frac{2^n - n - 1}{n!}.$$

5.2-3

Use indicator random variables to compute the expected value of the sum of $n$ dice.

Expectation of a single dice $X_i$ is

$$ \begin{aligned} \text E[X_k] & = \sum_{i = 1}^6 i \Pr\{X_k = i\} \\ & = \frac{1 + 2 + 3 + 4 + 5 + 6}{6} \\ & = \frac{21}{6} \\ & = 3.5. \end{aligned} $$

As for multiple dices,

$$ \begin{aligned} \text E[X] & = \text E\Bigg[\sum_{i = 1}^n X_i \Bigg] \\ & = \sum_{i = 1}^n \text E[X_i] \\ & = \sum_{i = 1}^n 3.5 \\ & = 3.5 \cdot n. \end{aligned} $$

5.2-4

Use indicator random variables to solve the following problem, which is known as the hat-check problem. Each of $n$ customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who get back their hat?

Let $X$ be the number of customers who get back their own hat and $X_i$ be the indicator random variable that customer $i$ gets his hat back. The probability that an individual gets his hat back is $\frac{1}{n}$. Thus we have

$$E[X] = E\Bigg[\sum_{i = 1}^n X_i\Bigg] = \sum_{i = 1}^n E[X_i] = \sum_{i = 1}^n \frac{1}{n} = 1.$$

5.2-5

Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$. (See Problem 2-4 for more on inversions.) Suppose that the elements of $A$ form a uniform random permutation of $\langle 1, 2, \ldots, n \rangle$. Use indicator random variables to compute the expected number of inversions.

Let $X_{i, j}$ for $i < j$ be the indicator of $A[i] > A[j]$. We have that the expected number of inversions

$$ \begin{aligned} \text E\Bigg[\sum_{i < j} X_{i, j}\Bigg] & = \sum_{i < j} E[X_{i, j}] \\ & = \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n \Pr\{A[i] > A[j]\} \\ & = \frac{1}{2} \sum_{i = 1}^{n - 1} n - i \\ & = \frac{n(n - 1)}{2} - \frac{n(n - 1)}{4} \\ & = \frac{n(n - 1)}{4}. \end{aligned} $$