Skip to content

5.2 Indicator random variables

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?

Note that

  • Candidate $1$ is always hired
  • The best candidate (candidate whose rank is $n$) is always hired
  • If the best candidate is candidate $1$, then that's the only candidate hired.

In order for $\text{HIRE-ASSISTANT}$ to hire exactly twice, candidate $1$ should have rank $i$, where $1 \le i \le n - 1$, and all candidates whose ranks are $i + 1, i + 2, \dots, n - 1$ should be interviewed after the candidate whose rank is $n$ (the best candidate).

Let $E_i$ be the event in which candidate $1$ have rank $i$, so we have $P(E_i) = 1 / n$ for $1 \le i \le n$.

Our goal is to find for $1 \le i \le n - 1$, given $E_i$ occurs, i.e., candidate $1$ has rank $i$, the candidate whose rank is $n$ (the best candidate) is the first one interviewed out of the $n - i$ candidates whose ranks are $i + 1, i + 2, \dots, n$.

So,

$$\sum_{i = 1}^{n - 1} P(E_i) \cdot \frac{1}{n - i} = \sum_{i = 1}^{n - 1} \frac{1}{n} \cdot \frac{1}{n - i}.$$

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} $$