[Algo] Exercise 5.4

Exercise 5.4-1
How many people must there be in a room before the probability that someone has the same birthday as you do is at least 1/2? How many people must there be before the probability that at least two people have a birthday on July 4 is greater than 1/2?

(1)
$1 - (364/365)^{n-1} \geq 1/2 \Rightarrow 1/2 \geq (364/365)^{n-1}$
$\Rightarrow \ln 1/2 \geq (n-1) \ln(364/365) \Rightarrow n-1 \leq \frac{\ln 1/2}{\ln 364/365}$
$n-1 \leq 252.6519\ldots \Rightarrow n \leq 253$
Thus there must be 252 other people such that the probability that someone has the same birthday is at least 1/2.

(2)
用 1 減掉("都沒有人的生日是7/4的機率" + "只有一個人的生日是7/4的機率")就是我們所求：
$1 - (364/365)^n - C^n_1(1/365)(364/365)^{n-1} \geq 1/2$
We can use computer to solve this equation, and while $n \geq 613$ this inequality holds.

Exercise 5.4-2
Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?

By pigeon's rule, we can conclude that at most b + 1 tosses there must be a bin containing two balls. Thus, we can obtain the expected number of ball tosses by the definition:
$E[X] = \sum_{i = 2}^{b + 1}i\mbox{p}(i)$
where i is the number of ball tosses.
We can obtain that $$\mbox{p}(i) = \frac{P^b_{i-1}(i-1)}{b^{i}}$$, and the expected number of ball tosses is
$\sum_{i=2}^{b+1}\frac{P^b_{i-1}\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}\frac{b(b-1)(b-2)\cdots(b-i)\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}(\frac{b}{b})\cdot(\frac{b-1}{b})\cdots(\frac{b-i}{b})\cdot i(i-1)$

Exercise 5.4-3
For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.

The birthday paradox holds even when the birthdays are only pairwise independent. (當裡面有雙胞胎的時候，這時候生日可能就不是獨立事件了) 在分析 birthday paradox 的時候，我們會用到獨立這個條件的只有這個地方：
$\mbox{Pr}\{b_i=b_j\}=\sum_{r=1}^n\mbox{Pr}\{b_i=r\quad\mbox{and}\quad b_j=r\}$
Obviously, it involves only two variables $b_i$ and $b_j$. Thus, pairwise independence is sufficient.

Exercise 5.4-4
How many people should be invited to a party in order to make it likely that there are three people with the same birthday?

Suppose that there are k people invited, and all years have n( = 365) days.
$$\mbox{Pr\{there are exactly 3 people with the same birthday\}} = \frac{n \cdot C^{n-1}_{k-3} \cdot \frac{k!}{3!}}{n^k}$$
$$\mbox{Pr\{there are at least 3 people with the same birthday\}} = 1 - \frac{P^n_k}{n^k} - \frac{n \cdot C^{n-1}_{k-2} \cdot \frac{k!}{2!}}{n^k}$$

Exercise 5.4-5
What is the probability that a k-string over a set of size n is actually a k-permutation? How does this question relate to the birthday paradox?

(1) $$\frac{P^n_k}{n^k} = 1\cdot(\frac{n-1}{n})\cdot(\frac{n-1}{n})\cdots(\frac{n-k+1}{n})$$
(2) n is the days all year have, k is how many people are invited to the party, and k-permutation denotes all people have distinct birthdays, no one has the same birthday as the other's.

Exercise 5.4-6
Suppose that n balls are tossed into n bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?

(1) Let $X$ be the random variable of empty bins. By the linearity property of expected number, we can obtain that$\mbox{E}[X] = \mbox{E}[X_1 + X_2 + \cdots X_n]$, where $X_i$ is the indicator random variable.
$X_i$ = I{bin i is empty}
$\mbox{E}[X_i] = \mbox{Pr}\{$bin i is empty$\} = (\frac{n-1}{n})^n$
$$\Rightarrow\mbox{E}[X]=n\cdot(\frac{n-1}{n})^n=\frac{(n-1)^n}{n^{n-1}}$$
(2) Same as the above, let $X$ be the random variable of bins with exactly one ball, and $X_i$ is the indicator random variable.
$X_i$ = I{bin i contains exactly one ball}

$\mbox{E}[X_i]=\mbox{Pr}\{$ bin i contains exactly one ball $\}=\frac{(n-1)^{n-1}\cdot n}{n^n}$

$$\Rightarrow\mbox{E}[X]=n\cdot\frac{(n-1)^{n-1}\cdot n}{n^n}=\frac{(n-1)^{n-1}}{n^{n-2}}$$

Exercise 5.4-7
Sharpen the lower bound on streak length by showing that in n flips of a pair coin, the probability is less than $1/n$ that no streak longer than $\lg n - 2\lg\lg n$ consecutive heads occurs.