[Algo] 5.4 Probabilistic analysis and further uses of indicator random variables (3)

5.4.3 Streaks

丟銅板 n 次，最多可以連續出現正面次數的期望值是多少？答案是 $\Theta(\lg n)$

這個證明分成兩個部份：首先先證明這個期望值是 $O(\lg n)$。

令 $A_{ik}$ 為在從第 i 次丟銅板開始連續出現正面的次數至少是 k 次以上的 event，也就是說第 $i, i+1, \ldots, i + k - 1$ 次都是出現正面，其中 $1 \leq k \leq n$，$1 \leq i \leq n - k + 1$。
每次丟出正面的機率為 $1/2$，所以 @{\textup{Pr}\{A_{ik}\} = 1/2^k}@，對 $k = 2\lceil \lg n\rceil$ 而言，@{\textup{Pr}\{A_{i, 2\lceil \lg n\rceil}\} = \frac{1}{2^{2\lceil \lg n\rceil}} \leq \frac{1}{2^{2 \lg n}} = \frac{1}{n^2}}@

對於至少連續出現 $2\lceil \lg n \rceil$ 次正面的事件，i 最大可以到 $n - 2\lceil \lg n \rceil + 1$，因此出現至少連續 $2\lceil \lg n \rceil$ 次正面的機率為：@{\textup{Pr}\{\bigcup_{i = 1}^{n - 2\lceil \lg n \rceil + 1} A_{i, 2\lceil \lg n\rceil}\} \leq \sum_{i = 1}^{n - 2\lceil \lg n \rceil + 1} \frac{1}{n^2} < \sum_{i = 1}^n \frac{1}{n^2} = \frac{1}{n}\qquad(1)}@

令 $L_j$ 為恰好連續出現 j 次正面的事件，其中 $j = 0, 1, \ldots, n$，令 $L$ 為最多可以連續出現正面的次數。因此根據期望值的定義，我們知道：@{E[L] = \sum_{j = 0}^n j\textup{Pr}\{L_j\}}@
@{\Rightarrow E[L] = \sum_{j = 0}^n j\textup{Pr}\{L_j\}}@
@{= \sum_{j = 0}^{2\lceil \lg n\rceil - 1} j\textup{Pr}\{L_j\} + \sum_{j = 2\lceil \lg n\rceil}^n j\textup{Pr}\{L_j\}}@
@{< \sum_{j = 0}^{2\lceil \lg n\rceil - 1} (2\lceil \lg n\rceil)\textup{Pr}\{L_j\} + \sum_{j = 2\lceil \lg n\rceil}^n n\textup{Pr}\{L_j\}}@
@{ = 2\lceil \lg n\rceil\sum_{j = 0}^{2\lceil \lg n\rceil - 1} \textup{Pr}\{L_j\} + n\sum_{j = 2\lceil \lg n\rceil}^n \textup{Pr}\{L_j\}}@
@{< 2\lceil \lg n\rceil \cdot 1 + n \cdot (\frac{1}{n}) \qquad \textup{By equation (1)}}@
$ = O(\lg n)$

證明了 upper bound 之後，我們要證明 lower bound 是 $\Omega(\lg n)$。為了要證明這件事，我們把全部 n 次的投擲分成 $n/s$ 組，每組都是 s 次的投擲。如果 $s = \lfloor (\lg n)/2 \rfloor$，我們可以導出最少有一組全部都是投出正面，所以可以得到連續出現正面的次數是 $s = \Omega(\lg n)$。

對 $k = \lfloor (\lg n)/2 \rfloor$ 而言，@{\textup{Pr}\{A_{i, \lfloor (\lg n)/2 \rfloor}\} = \frac{1}{2^{\lfloor (\lg n)/2 \rfloor}} \geq \frac{1}{\sqrt{n}}}@

那麼對至少連續出現 $\lfloor (\lg n)/2 \rfloor$ 次正面，但是卻不是從第 i 次投擲開始的機率最多是 $1 - 1/\sqrt{n}$。對每一組都不能有連續 $\lfloor (\lg n)/2 \rfloor$ 次正面的機率為：
$(1 - 1/\sqrt{n})^{\lfloor n/\lfloor (\lg n)/2 \rfloor \rfloor} \leq (1 - 1/\sqrt{n})^{n/\lfloor (\lg n)/2 \rfloor}$
$\leq (1 - 1/\sqrt{n})^{2n/ \lg n - 1} \leq e^{-(2n/ \lg n - 1) / \sqrt{n}}$
$= O(e^{-\lg n}) = O(1/n)$

其中$(2n/\lg n - 1) / \sqrt{n} \geq \lg n$ 這個式子在 n 很大的時候是成立的。舉例來說，當 $n \geq 2^{16}$ 時，$n \geq \sqrt{n}(\lg n)^2$，帶入原式顯然成立。

因此，連續正面次數超過$\lfloor (\lg n) / 2 \rfloor$的機率：
@{\sum_{j = \lfloor (\lg n) / 2 \rfloor + 1}^{n} \textup{Pr}\{L_j\} \geq 1 - O(1/n)}@
@{\Rightarrow E[L] = \sum_{j = 0}^n j\textup{Pr}\{L_j\}}@
@{ = \sum_{j = 0}^{\lfloor (\lg n) / 2 \rfloor} j\textup{Pr}\{L_j\} + \sum_{j = \lfloor (\lg n) / 2 \rfloor + 1}^n j\textup{Pr}\{L_j\}}@
@{\geq \sum_{j = 0}^{\lfloor (\lg n) / 2 \rfloor} 0\cdot\textup{Pr}\{L_j\} + \sum_{j = \lfloor (\lg n) / 2 \rfloor + 1}^n \lfloor (\lg n) / 2\rfloor \textup{Pr}\{L_j\}}@
@{ = 0 + \lfloor (\lg n) / 2\rfloor \sum_{j = \lfloor (\lg n) / 2\rfloor + 1}^n \textup{Pr}\{L_j\}}@
$ \geq \lfloor (\lg n) / 2\rfloor(1 - O(1/n)) = \Omega(\lg n)$

[Algo] 5.4 Probabilistic analysis and further uses of indicator random variables (2)

5.4.2  Balls and bins
假設現在有 b 個 bins $\{1, 2, \ldots, b\}$，然後我們開始隨機的投擲球到這些 bins 裡面，當然每次一定會丟擲到某個 bin 裡面，而且每個 bin 被球投擲進去的機率都是一模一樣的。這個 ball-tossing process 其實就是 Bernoulli trial，這個 model 在未來對我們分析 hashing 是非常有用的。


接下來我們來思考幾個問題：
(1) 如果我們丟 n 個球，對一個給定的 bin，會有幾顆球在裡面？
因為每個 bin 被球投進去的機率都是 $1/b$，所以期望值是 $n/b$。


(2) 對於某個給定的 bin，平均我們要丟到幾個球，這個 bin 才會有球被丟進去呢？
顯然答案當然是 b 個球。

(3) 平均我們要丟幾個球，才會讓每個 bin 裡面都至少會有一顆球？
對這個問題，我們把他切成 b 個 stage 來看，每個 stage  代表有一個球被投擲到某個空的 bin 裡面去，所以我們要分析的就是從第 (i-1) 個 stage 到第 i 個 stage 我們平均要丟幾個球？當現在是第 i 個 stage 的時候，會有 (b - i + 1) 個 empty bins，令 $n_i$ 為我們在第 i 個 stage 裡所投出的球數，而在第 i 個 stage 時丟到不是空的 bin 的機率是 $(b - i + 1)/b$，所以我們可以得知 $E[n_i] = \frac{b}{b - i + 1}$
令 $n = \sum_{i = 1}^b n_i$，則
 $$E[n] = \sum_{i = 1}^b E[n_i] = \sum_{i = 1}^b \frac{b}{b - i + 1} = b\sum_{i = 1}^b \frac{1}{i} = b(\ln b + O(1))$$

所以我們可以得知大概需要 $b \ln b$ 次投擲，才能讓每個 bin 都至少有一顆球在裡面。這個問題也被稱為 coupon collector's problem，有一個人要蒐集 b 種不同的 coupons，那平均下來他要拿到 $b \ln b$ 張 coupons，才能夠全部種類都蒐集到一張。

post source code

想在 blogger 上面貼 code，這個 blog 有一些相關的連結。
如果是想要簡單的把一些特殊符號替換掉，而不考慮 syntax highlight 的問題的話，
這個網站可以提供簡單的功能：
http://www.csie.ntu.edu.tw/~piaip/unihtml/

當然強大的編譯器 vim 就有提供這樣的功能，可以把他輸出成 html 的格式
http://www.surfchen.org/wiki.php/vim

[Algo] 5.4 Probabilistic analysis and further uses of indicator random variables (1)

5.4.1 The birthday paradox
How many people must there be in a room before there is a 50% chance that two of them were born on the same day of the year?

我們先定義幾個符號：
$k$ 為總人數
一年有 $n = 365$ 天（假設沒有閏年的影響）
$b_i$ 為第i個人的生日，$1 \leq b_i \leq n$

假設生日都是 uniformly distribute 的，所以我們可以得到 $\mbox{Pr}\{b_i = r\} = \frac{1}{n}$，其中 $i = 1, 2, \ldots k$，$r = 1, 2, \ldots n$，而且我們再假設彼此的生日都是獨立的，那麼我們可以推斷第i個人和第j個人他們的生日都是 $r$ 的機率是：
$\mbox{Pr}\{b_i = r$ and $b_j = r\} = \mbox{Pr}\{b_i = r\}\mbox{Pr}\{b_j = r\} = \frac{1}{n^2}$
所以， 第i個人和第j個人他們的生日是同一天的機率就是：
$\mbox{Pr}\{b_i = b_j\} = \sum_{r = 1}^n \mbox{Pr}\{b_i = r$ and $b_j = r\} = \sum_{r = 1}^n \frac{1}{n^2} = \frac{1}{n}$

接下來我們從反面來算，先算每個人的生日都不一樣的機率 $p$：
$p = \frac{P^n_k}{n^k} = \frac{n(n-1)(n-2) \cdots (n - k + 1)}{n^k}$
$ = 1 \cdot (\frac{n-1}{n}) \cdot (\frac{n-2}{n}) \cdots (\frac{n - k + 1}{n})$
$ = 1 \cdot (1 - \frac{1}{n})(1 - \frac{2}{n}) \cdots (1 - \frac{k - 1}{n})$
由不等式$1 + x \leq e^x$，我們可以整理如下：
$p \leq e^{-1/n}e^{-2/n} \cdots e^{-(k-1)/n} = e^{-k(k-1)/2n}$

所以回到問題來，我們希望 $1 - p \geq 1/2$， 顯然 $-k(k-1)/2n \leq \ln(1/2)$，解完這個二次不等式，我們可以得到 $k \geq (1 + \sqrt{1 + (8\ln 2)n})/2$，以 $n = 365$ 來說，$k \geq 23$
                                                                                                                                                                    
接下來，課本利用 indicator random variable 來幫助我們分析要有多少人在房間裡，才會恰好兩個人的生日是在同一天？
一樣假設有 $k$ 個人在房間裡面，我們定義 indicator random variable $X_{ij}$ 如下：
$X_{ij} =  \mbox{I}\{$ person i and person j have the same birthday $\}$
所以我們知道：$E[X_{ij}] = \mbox{Pr}\{$ person i and person j have the same birthday $\} = 1/n$
定義 random variable $X$ 為有多少人的生日為同一天，則 $X = \sum_{i = 1}^k \sum_{j = i+1}^k X_{ij}$
$E[X] = \sum_{i = 1}^k \sum_{j = i+1}^k E[X_{ij}] = C_{2}^{k} \frac{1}{n} = \frac{k(k-1)}{2n}$
當 $k(k-1) \geq 2n$ 時，生日在同一天的人數的期望值才至少會大於 1，以 $n = 365$ 來說，至少 $k = 28$ 人，我們才期望可以找到至少兩個人的生日是同一天。

[Algo] 5.3 Randomized algorithms

對於 hiring problem，如果我們預先把 candidate 的 rank 作一次亂數排列，那麼我們就可以合理的假設我們每次都是得到一個 average case 的 input，而且在上一節我們已經證明出對於 average case 的 cost 是 $\ln n$，於是我們就可以不必擔心即使是 worst case 的 input。

@{
\proc{Randomized-Hire-Assistant}(n)
\li \textup{randomly permute the list of candidates}
\li best = 0\;\textup{// candidate 0 is a least-qualified dummy candidate}
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{interview candidate}\;i
\li \;\;\;\;\If \;\textup{candidate}\;i\;\textup{is better than candidate}\;best
\li \;\;\;\;\;\;\;\;best = i
\li \;\;\;\;\;\;\;\;\textup{hire candidate}\;i
}@




Randomly permuting arrays
我們接下來要看關於 RANDOMIZED-HIRE-ASSISTANT 裡面的隨機打亂 candidate 的順序的方法。課本裡提供了兩個方法，一個是 PERMUTE-BY-SORTING，另一個則是 RANDOMIZE-IN-PLACE。

(1) PERMUTE-BY-SORTING
假設 A 是一個包涵了從 1 到 n 的 array，這個方法是根據每個 A[i]都給予一個 priority P[i]，當然 P[i] 是由亂數決定的，接著我們根據 P 把 A 作排序的動作，即可達成我們的目的。

@{
\proc{Permute-By-Sorting}(A)
\li n = \textup{length}[A]
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;P[i] = \proc{Random}(1, n^3)
\li \textup{sort}\;A, \;\textup{using}\;P\;\textup{as sort keys}
\li \Return A
}@




在第3行的地方我們從 1 到$n^3$之間取出一個亂數，取這個範圍的目的是為了讓 P 裡面的亂數不會有重複的現象發生，課本更指出不會重複的機率大於等於 $1 - \frac{1}{n}$，我們給個小小的證明：
$\frac{P^{n^3}_n}{{(n^3)}^n} = \frac{n^3(n^3 - 1)\cdots(n^3-n+1)}{n^{3n}}$
$ = (1-\frac{0}{n^3})(1-\frac{1}{n^3})(1 - \frac{2}{n^3})\cdots(1-\frac{n-1}{n^3}) \geq (1-\frac{n}{n^3})^n$
$\geq 1 - \frac{1}{n}$        (if $a\mbox{,}b \geq 0 \Rightarrow (1 - a)(1 - b) \geq 1 - (a+b)$)

當然，最耗時間的步驟還是在第4行的地方，我們需要花費$\Theta(n \mbox{lg} n)$的時間來作排序。最後剩下要證明部份就是這個 procedure 是可以產生 uniform random permutation 的，在這裡證明的部份就暫時省略之。

(2) RANDOMIZE-IN-PLACE
這個方法比上一個方法好，他可以在$O(n)$的時間內就可以完成。

@{
\proc{Randomize-In-Place}(A)
\li n = \textup{length}[A]
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{swap}\;A[i]\;\textup{and}\;A[\proc{Random}(i,n)]
}@


要注意的是第3行，我們只從i到n的範圍裡去取出亂數，這樣子才會產生 uniform random permutation，如果我們取的是從1到n裡面的亂數，則不會是 uniform 的。