5.4 Probabilistic analysis and further uses of indicator random variables

5.4-1

For each people, the probability that he doesn't have the same birthday as me is $\frac{n - 1}{n}$, for k people that all don't have the same birthday as me is $(\frac{n - 1}{n})^k$, thus the probability that at least one people that has the same birthday as me is $1 - (\frac{n - 1}{n})^k$. Let $1 - (\frac{n - 1}{n})^k \geq \frac{1}{2}$, and we have $k \geq 253$.

The probability that only one people has a birthday on July 4 is $k\frac{1}{n}(\frac{n - 1}{n})^{k - 1}$, and the probability that no one has a birthday on July 4 is $(\frac{n - 1}{n})^k$, thus the probability that at least two people have a birthday on July 4 is $1 - k\frac{1}{n}(\frac{n - 1}{n})^{k - 1} - (\frac{n - 1}{n})^k$, let $1 - k\frac{1}{n}(\frac{n - 1}{n})^{k - 1} - (\frac{n - 1}{n})^k \geq \frac{1}{2}$, we have $k \geq 613$.

5.4-2

The expected number of ball tosses is $1 + \sum_{k = 1}^{b} \frac{b!}{(b - k)!b^k}$, it's a birthday problem.

5.4-3

The equation shows that $E[X] = \sum_{i = 1}^{k}\sum_{j = i + 1}^{k}E[X_{ij}]$, so pairwise indenpendence is sufficient.

5.4-4

For each pair (i, j, r) of the k people in the room, we define the indicator random variable $X_{ijr}$, for $1 \leq i < j < r \leq k$, by:

$$ \begin{eqnarray} X_{ijr} &=& I\lbrace\text{person i, person j and person r have the same birthday}\rbrace \\ &=& \begin{cases} 1, & \text{if person i, person j and person r have the same birthday} \\ 0, & \text{otherwise} \end{cases} \end{eqnarray} $$

The probability that i's birthday, j's birthday and r's birthday all fall on day s is $Pr\lbrace b_i = s \text{ and } b_j = s \text{ and } b_r = s \rbrace = Pr\lbrace b_i = s \rbrace Pr\lbrace b_j = s \rbrace Pr\lbrace b_r = s \rbrace = \frac{1}{n^3}$.

Thus, the probability that they all fall on the same day is:

$$ \begin{eqnarray} Pr\lbrace b_i = b_j = b_r \rbrace &=& \sum_{s = 1}^{n}Pr\lbrace b_i = s \text{ and } b_j = s \text{ and } b_r = s \rbrace \\ &=& \sum_{s = 1}^{n}\frac{1}{n^3} \\ &=& \frac{1}{n^2} \end{eqnarray} $$

Thus, $E[X_{ijr}] = Pr\lbrace\text{person i, person j and person r have the same birthday}\rbrace = \frac{1}{n^2}$.

Letting X be the random variable that counts the number of pairs of inviduals having the same birthday, we have $X = \sum_{i = 1}^{k}\sum_{j = i + 1}^{k}\sum_{r = j + 1}^{k}X_{ijr}$.

Taking expectations of both sides and applying linearity of expectation, we obtain:

$$ \begin{eqnarray} E[X] &=& E[\sum_{i = 1}^{k}\sum_{j = i + 1}^{k}\sum_{r = j + 1}^{k}X_{ijr}] \\ &=& \sum_{i = 1}^{k}\sum_{j = i + 1}^{k}\sum_{r = j + 1}^{k}E[X_{ijr}] \\ &=& \binom{k}{3}\frac{1}{n^2} \\ &=& \frac{k(k - 1)(k - 2)}{6n^2} \end{eqnarray} $$

Let $\frac{k(k - 1)(k - 2)}{6n^2} \geq 1$, we have $k \geq 94$.

5.4-5

$P = \frac{A_n^k}{n^k}$.

It can be described by the birthday paradox that k people in the romm have unique birthday.

5.4-6

Let's define the indicator random variable $X_i$, for $1 \leq i \leq n$, by:

$$ \begin{eqnarray} X_i &=& I\lbrace\text{bin i is empty}\rbrace \\ &=& \begin{cases} 1, & \text{if bin i is empty} \\ 0, & \text{otherwise} \end{cases} \end{eqnarray} $$

We have $E[X_i] = Pr\lbrace \text{bin i is empty} \rbrace = (\frac{n - 1}{n})^n$ (toss n balls into n - 1 bins).

Let X be the random variable that counts the number of bins that are empty, we have $X = \sum_{i = 1}^{n}X_i$. So:

$$ \begin{eqnarray} E[X] &=& E[\sum_{i = 1}^{n}X_i] \\ &=& \sum_{i = 1}^{n}E[X_i] \\ &=& \sum_{i = 1}^{n}(\frac{n - 1}{n})^n \\ &=& n(\frac{n - 1}{n})^n \\ &=& n(1 - \frac{1}{n})^n \\ \end{eqnarray} $$

Then let's check another question. Let's define the indicator random variable $X_i$, for $1 \leq i \leq n$, by:

$$ \begin{eqnarray} X_i &=& I\lbrace\text{bin i has exactly one ball}\rbrace \\ &=& \begin{cases} 1, & \text{if bin i is has exactly one ball} \\ 0, & \text{otherwise} \end{cases} \end{eqnarray} $$

We have $E[X_i] = Pr\lbrace \text{bin i has exactly one ball} \rbrace = n\frac{1}{n}(\frac{n - 1}{n})^{n - 1} = (1 - \frac{1}{n})^{n - 1}$ (toss one ball into one bin, then toss n - 1 balls into n - 1 bins).