5.2 Indicator random variables

5.2-1

We hire exactly one time when the first candidate is the best. So the first candidate has a probability of $\frac{1}{n}$ of being better qualified than other n - 1 candidates. Thus the probability of hiring exactly one time is $\frac{1}{n}$.

We hire n times when each candidate is better than the previous candidate. In each turn, the candidate i has a probability of $\frac{1}{i}$ of being better than the previous i - 1 candidates. Thus the probability is $1 * \frac{1}{2} * \frac{1}{3} * \ldots * \frac{1}{n} = \frac{1}{n!}$.

5.2-2

We hire exactly twice when the first candidate is not the best candidate, and the best candidate comes before all the candidates who are better than the first candidate.

Let's assume the first candidate has a rank k among the candidates (k < n, bigger is better). So there are n - k candidates that are better than the first candidate, including the best candidate. So the best candidate could only appear through position 2 to k + 1, which are k + 1 - 2 + 1 = k positions. And the best candidate has a probability of $\frac{1}{k}$ to apppear in those k positions.

Because each candidate has a probability of $\frac{1}{n}$ to appear in the first position, thus the probability of hiring twice is $\frac{1}{n}\frac{1}{1} + \frac{1}{n}\frac{1}{2} + \frac{1}{n}\frac{1}{3} \ldots \frac{1}{n}\frac{1}{n - 1} = \frac{1}{n}\sum_{k = 1}^{n - 1}\frac{1}{k} = \frac{\ln{(n - 1)} + O(1)}{n}$.

5.2-3

Let's define $X_i$ be the indicator random variable indicates the value of ith dice. Thus,

$$ \begin{eqnarray} X_i &=& I\lbrace\text{the number of dice is k}\rbrace \\ &=& \begin{cases} 1, & \text{if k = 1} \\ 2, & \text{if k = 2} \\ 3, & \text{if k = 3} \\ 4, & \text{if k = 4} \\ 5, & \text{if k = 5} \\ 6, & \text{if k = 6} \\ \end{cases} \end{eqnarray} $$

and $X = X_1 + X_2 + \ldots + X_n$.

Thus the expected value in one dice is:

$$ \begin{eqnarray} E[X_i] &=& E[I\lbrace \text{the number of dice is k} \rbrace] \\ &=& \sum_{k = 1}^6 kPr\lbrace X_i = k \rbrace \\ &=& \frac{1}{6}(1 + 2 + 3 + 4 + 5 + 6) \\ &=& 3.5 \end{eqnarray} $$

Thus, the expected value of the sum of n dice is:

$$ \begin{eqnarray} E[X] &=& E\big[\sum_{i = 1}^n X_i\big] \\ &=& \sum_{i = 1}^nE\big[X_i\big] \\ &=& \sum_{i = 1}^n 3.5 \\ &=& 3.5n \end{eqnarray} $$

5.2-4

Each person gets his own hat with probability $\frac{1}{n}$. Let's define $X_i$ be the indicator random variable associated with the event in which the ith customer gets his own hat. Thus,

$$ \begin{eqnarray} X_i &=& I\lbrace\text{customer i gets his own hat}\rbrace \\ &=& \begin{cases} 1, & \text{if customer i gets his own hat} \\ 0, & \text{if customer i doesn't get his own hat} \end{cases} \end{eqnarray} $$

and $X = X_1 + X_2 + \ldots + X_n$.

Thus the expected number of customers who get back their own hat is:

$$ \begin{eqnarray} E[X] &=& E\big[\sum_{i = 1}^n X_i\big] \\ &=& \sum_{i = 1}^nE\big[X_i\big] \\ &=& \sum_{i = 1}^n \frac{1}{n} * 1 \\ &=& 1 \end{eqnarray} $$

5.2-5

Let's define $X_{ij}$ be the the indicator random variable associated with the event that if i < j, then A[i] > A[j]. Thus,

$$ \begin{eqnarray} X_{ij} &=& I\lbrace A[i] > A[j]\rbrace \\ &=& \begin{cases} 1, & A[i] > A[j] \\ 0, & A[i] \leq A[j] \end{cases} \end{eqnarray} $$

and $Pr\lbrace A[i] > A[j] \rbrace = Pr\lbrace A[i] \leq A[j] \rbrace = \frac{1}{2}$.

Thus the expected number of inversions is:

$$ \begin{eqnarray} E[X] &=& E\big[\sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n X_{ij}\big] \\ &=& \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n E\big[X_{ij}\big] \\ &=& \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n (\frac{1}{2} * 1 + 0) \\ &=& \frac{1}{2}\sum_{i = 1}^{n - 1} (n - i) \\ &=& \frac{1}{2}\sum_{i = 1}^{n - 1} i \\ &=& \frac{1}{2}\frac{(1 + n - 1)(n - 1)}{2} \\ &=& \frac{n(n - 1)}{4} \end{eqnarray} $$