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} \]

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用