Chapter 5.2

Hire exact one time: The best candidate appears first, the probability is \(\frac{1}{n}\).

Hire n times: The candidates appears in decrease order, the probability is \(\frac{1}{n!}\).

We should always hire the first candidate and the best candidate, let the first candidate to be \(A[1]\), and the best candidate to be \(A[k]\), there should be \(A[1] = best(A[1..k-1])\) to hire exactly two candidates, i.e., choose the best of \(k-1\) candidates, the total probability is \(\frac{1}{n}\sum_{k=2}^{n-1}\frac{1}{k-1}\).

The expected value of k-th dice is

\begin{align*} E[X_k] &=\sum_{x=1}^{6}x\Pr\{X_k=x\}\\ &=\sum_{x=1}^{6}\frac{x}{6}\\ &=\frac{7}{2} \end{align*}

The expected value of the sum of n dice is

\begin{align*} E[X] &=E\Bigg[\sum_{i=1}^{n}X_i\Bigg]\\ &=\sum_{i=1}^{n}E[X_i]\\ &=\sum_{i=1}^{n}\frac{7}{2}\\ &=\frac{7n}{2} \end{align*}

Each customer has \(\frac{1}{n}\) probability to get back their own hat, the expected value is \(E[X_k] = \frac{1}{n}\).

The total expected number of customers who get back their own hat is \(E[X] = \sum_{i=1}^{n}E[X_i] = 1\).

The probability that a pair is an inversion is exactly \(\frac{1}{2}\), the expected value is \(E[X_{ij}] = \frac{1}{2}\).

The total expected number of inversions is

\begin{align*} E[X] &=\sum_{i=1}^{n-1}\sum_{j=i}^{n}E[X_{ij}]\\ &=\frac{n(n-1)}{4} \end{align*}