[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)$