5.2 Indicator random variables¶

5.2-1¶

In 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 that you hire exactly $n$ times?

the probability that you hire exactly one time is $\frac{(n-1)!}{n!}=\frac{1}{n}$

the probability that you hire exactly $n$ times is $\frac{1}{n!}=\frac{1}{n}$

5.2-2¶

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

Let $B_{i}$ be the event that the best candidate is the $i$th candidate be interviewed. Then $Pr(B_{i})=\frac{1}{n}$ for $i=1,2,...,n$.

The probability that the first candidate is the best of the first $i-1$ candidates is $\frac{1}{i-1}$

$$ \begin{aligned} P & = \sum_{i=2}^{n}\frac{1}{n}\cdot \frac{1}{i-1}\cr & =\sum_{i=1}^{n-1}\frac{1}{n}\cdot \frac{1}{i}\cr & =\frac{\lg(n)+O(1)}{n} \end{aligned} $$

5.2-3¶

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

for a dice: $X_{j}=i$ if the result of dice is $i$, for $i=1,2,3,4,5,6$.

$S=\sum_{j=1}^{n}X_{j}$

$$ \begin{aligned} E[S] & = E\left[\sum_{j=1}^{n}X_{j}\right]\cr & = \sum_{j=1}^{n} E[X_{j}]\cr & = \sum_{j=1}^{n}\sum_{i=1}^{6}i\cdot PR(X_{j}=i)\cr & = \sum_{j=1}^{n}\sum_{i=1}^{6}i\cdot \frac{1}{6}\cr & = \frac{7n}{2}\cr \end{aligned} $$

5.2-4¶

This exercise asks you to (partly) verify that linearity of expectation holds even if the random variables are not independent. Consider two 6-sided dice that are rolled independently. What is the expected value of the sum? Now consider the case where the first die is rolled normally and then the second die is set equal to the value shown on the first die. What is the expected value of the sum? Now consider the case where the first die is rolled normally and the second die is set equal to 7 minus the value of the first die. What is the expected value of the sum?

$E[sum] = E[X_{1}+X_{2}]=E[X_{1}]+E[X_{2}]=7/2+7/2=7$
$E[sum] = E[2X_{1}]=2E[X_{1}]=7$
$E[sum] = E[X_{1}+7-X_{1}]=E[7]=7$

5.2-5¶

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 own hat?

$$ \begin{aligned} X_{i} & = \begin{cases} 1 & \text{the ith customers get back his own hat}\cr 0 & \text{else}\cr \end{cases}\cr E[S] & = E\left[\sum_{i=1}^{n}X_{i}\right]\cr & = \sum_{i=1}^{n}E[X_{i}]\cr & = \sum_{i=1}^{n}\frac{1}{n}\cr & = 1\cr \end{aligned} $$

5.2-6¶

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

$$\begin{aligned} X_{i,j} & = \begin{cases} 1 & \text{if } (i,j) \text{ is an inversion}\cr 0 & \text{else}\cr \end{cases}\cr E[S] & = E\left[\sum_{1\leq 1 \leq j\leq n}X_{i,j}\right]\cr & = \sum_{1\leq 1 \leq j\leq n}E[X_{i,j}]\cr & = \sum_{1\leq 1 \leq j\leq n}\frac{1}{2}\cr & = \frac{n(n-1)}{4}\cr \end{aligned} $$