在 第一講中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 $\mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)})$ ，而這一講想討論的是，如果今天我們手上有兩個 hash function (from same $\mathcal{H}$)可以選，每次我們就看哪一個 $h$ 回傳的 slot 中元素比較少，就將 element hash 到 slot，那麼現在 $\mathbb{E}[, \text{max num of elements in any slots} , ]$ ?
Chernoff Bound
$n$ 個 identical R.V. 的相加，想 measure 其偏離平均值的機率
Let $X_1, X_2, \cdots, X_n$ be independent binary R.V with $\mathbb{E}[X_i] = p_i$
$X = \sum_i X_i$, $; \mu = \mathbb{E}[X] = \sum_i p_i$
Power of 2 choices
Throw $n$ balls into $n$ bins, \
For every ball, we pick 2 bins uniformly at random, throw the ball into the bin with less load
Let $B_k = | ;\lbrace i , | ,b_i \geq k \rbrace;|$ (有 $\geq k$ 顆球的 bin 數)\
$\beta_k$ 為 $B_k$ 的 upper bound ; $ \quad \mathcal{E}_k$ 為 $\beta_k > B_k$ (上限符合要求) 的 event
\
假定我們已經有了 $B_k \leq \beta_k$ 這個條件 ($\mathcal{E}_k$ 成立)，該如何 inductively 去找 $\beta \scriptstyle k+1$ ?
-
For any balls $j$, we say $j$ is $\color{red}{red}$ if the number of balls below it $\leq k$
-
$\Pr[ , j , \text{is red} ,] \leq (\frac{\beta_k}{n})^2$ (兩個 bin 球數都要 $\geq k$)
-
$\mathbb{E}[B\scriptstyle k+1 \normalsize , | \mathcal{E}_k] \leq \mathbb{E}[\text{num of red balls} , | \mathcal{E}_k] \leq n \cdot (\frac{\beta_k}{n})^2$ \
(第一個等號因為有紅色球的 bin 一定有 $\geq$ $k+1$ 個球，後面那個等號是因為 Union Bound) -
Using $\color{blue}{\text{Chernoff Bound}}$， $\Pr[B \scriptstyle k+1 \normalsize \geq e \frac{\beta_k^2}{n} | \mathcal{E}_k] \leq \exp(-\frac{\beta_k^2}{n})$ \
\
(如果 $\exp(-\frac{\beta_k^2}{n}) \leq \frac{1}{n^2}$) ， 則我們可以選 $\beta \scriptstyle k+1 \normalsize = e , \frac{\beta_k^2}{n}$\
整理一下此遞迴式，我們有了以下關係式
$$ \boxed{\frac{\beta_{k+m}}{n} = \frac{1}{e} \, (\frac{e \beta_k}{n})^{2^m}} $$
接下來要選定初始值 $k$，就可以確定 $\beta$ 的值了，\
注意到 $\beta_6 \leq \lfloor \frac{n}{6} \rfloor \leq \frac{n}{2e}$ (顯然會超過 6 顆球
的bin數 一定會小於均分的 case)\
代回上式，可得
$$ \frac{\beta_{6+m}}{n} \leq \frac{1}{e} \, \frac{1}{2^{2^m}} $$
當 $m = \mathcal{O}(\ln \ln n)$， we can find that $\beta \scriptstyle 6+m \normalsize < 1$ \
(亦即超過 $\mathcal{O}(1) + \ln \ln n $ 顆球的 bin 出現的機率極小)
這裡只的機率很小是指 $\Pr[\neg , \mathcal{E}_m]$ 很小，根據上方的遞迴式，我們可以給出一個明確的上界
Fact
$$ \boxed{\Pr[ \neg \, \mathcal{E}_{k+1}] \leq \Pr[\neg \, \mathcal{E}_{k+1} \,| \, \mathcal{E}_k] \cdot \Pr[\mathcal{E}_k] + \Pr[\neg \, \mathcal{E}_k]} $$
proof.
$$ \begin{align} \text{RHS} \, &= \, \Pr[\neg \, \mathcal{E}_{k+1} \,| \, \mathcal{E}_k] \cdot \Pr[\mathcal{E}_k] + \Pr[\neg \, \mathcal{E}_k] \\ & = \Pr[\neg \, \mathcal{E}_{k+1} \, \land \, \mathcal{E}_k] + \Pr[\neg \, \mathcal{E}_k]\\ & = \underbrace{\Pr[\neg \, \mathcal{E}_{k+1} \, \land \, \mathcal{E}_k] + \Pr[\neg \, \mathcal{E}_k \, \land \, \neg \, \mathcal{E}_{k+1}]}_{\Pr[\neg \, \mathcal{E}_{k+1}]} + \Pr[\neg \, \mathcal{E}_k \, \land \, \mathcal{E}_{k+1}] \\ & \geq \text{LHS} \end{align} $$
$\Rightarrow \Pr[\neg , \mathcal{E} \scriptstyle k \normalsize] \leq \frac{1}{n} \quad$ (利用 $\Pr[\neg , \mathcal{E}_6 ] = 0$，遞迴求出)
More Discussion
$l$-choice
第 2 步變為 $\Pr[ , j , \text{is red} ,] \leq (\frac{\beta_k}{n})^l$ ($l$ 個 bin 球數都要 $\geq k$)
$$ \boxed{\frac{\beta_{k+m}}{n} = \frac{1}{e} \, (\frac{e \beta_k}{n})^{l^m}} $$
當 $m = \mathcal{O}(\frac{\ln \ln n}{\ln l})$， we can find that $\beta \scriptstyle 6+m \normalsize < 1$ ，但其實還是在同個 order
What if $\beta_k$ is so small
That is, 第 4 步的 bound 並不足夠小，也就是隨著 $\beta_k$ 的 decay， $\exp(-\frac{\beta_k^2}{n})$ 終會 $ > \frac{1}{n^2}$ $\Rightarrow \beta_k < \sqrt{2n \ln n}$ \
Pick 使得此式成立的 min. $k^\star$， $k^\star = \frac{\ln \ln n}{\ln 2} + \mathcal{O}(1)$
可以證明有 bin 超過 $k^\star + 2$ 的機率足夠小 (但證明我沒看懂QQ)
comments powered by Disqus