在 第一講 中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 Θ ( ln n ln ( ln n ) ) \mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)}) Θ ( l n ( l n n ) l n n ) H \mathcal{H} H h h h E [ , max num of elements in any slots , ] \mathbb{E}[, \text{max num of elements in any slots} , ] E [ , max num of elements in any slots , ]
Chernoff Bound
n n n
Let X 1 , X 2 , ⋯ , X n X_1, X_2, \cdots, X_n X 1 , X 2 , ⋯ , X n E [ X i ] = p i \mathbb{E}[X_i] = p_i E [ X i ] = p i
X = ∑ i X i X = \sum_i X_i X = ∑ i X i ; μ = E [ X ] = ∑ i p i ; \mu = \mathbb{E}[X] = \sum_i p_i ; μ = E [ X ] = ∑ i p i
Pr [ X ≥ e μ ] ≤ e − μ
\boxed{\Pr[X \geq e \mu] \leq e^{- \mu}}
Pr [ X ≥ e μ ] ≤ e − μ
Power of 2 choices
Throw n n n n n n
Let B k = ∣ ; { i , ∣ , b i ≥ k } ; ∣ B_k = | ;\lbrace i , | ,b_i \geq k \rbrace;| B k = ∣ ; { i , ∣ , b i ≥ k } ; ∣ ≥ k \geq k ≥ k
β k \beta_k β k B k B_k B k E k \quad \mathcal{E}_k E k β k > B k \beta_k > B_k β k > B k B k ≤ β k B_k \leq \beta_k B k ≤ β k E k \mathcal{E}_k E k β k + 1 \beta \scriptstyle k+1 β k + 1
For any balls j j j j j j r e d \color{red}{red} r e d ≤ k \leq k ≤ k
Pr [ , j , is red , ] ≤ ( β k n ) 2 \Pr[ , j , \text{is red} ,] \leq (\frac{\beta_k}{n})^2 Pr [ , j , is red , ] ≤ ( n β k ) 2 ≥ k \geq k ≥ k
E [ B k + 1 , ∣ E k ] ≤ E [ num of red balls , ∣ E k ] ≤ n ⋅ ( β k n ) 2 \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 E [ B k + 1 , ∣ E k ] ≤ E [ num of red balls , ∣ E k ] ≤ n ⋅ ( n β k ) 2 ≥ \geq ≥ k + 1 k+1 k + 1
Using Chernoff Bound \color{blue}{\text{Chernoff Bound}} Chernoff Bound Pr [ B k + 1 ≥ e β k 2 n ∣ E k ] ≤ exp ( − β k 2 n ) \Pr[B \scriptstyle k+1 \normalsize \geq e \frac{\beta_k^2}{n} | \mathcal{E}_k] \leq \exp(-\frac{\beta_k^2}{n}) Pr [ B k + 1 ≥ e n β k 2 ∣ E k ] ≤ exp ( − n β k 2 ) exp ( − β k 2 n ) ≤ 1 n 2 \exp(-\frac{\beta_k^2}{n}) \leq \frac{1}{n^2} exp ( − n β k 2 ) ≤ n 2 1 β k + 1 = e , β k 2 n \beta \scriptstyle k+1 \normalsize = e , \frac{\beta_k^2}{n} β k + 1 = e , n β k 2
$$ \boxed{\frac{\beta_{k+m}}{n} = \frac{1}{e} \, (\frac{e \beta_k}{n})^{2^m}} $$
接下來要選定初始值 k k k β \beta β β 6 ≤ ⌊ n 6 ⌋ ≤ n 2 e \beta_6 \leq \lfloor \frac{n}{6} \rfloor \leq \frac{n}{2e} β 6 ≤ ⌊ 6 n ⌋ ≤ 2 e n
$$ \frac{\beta_{6+m}}{n} \leq \frac{1}{e} \, \frac{1}{2^{2^m}} $$
當 m = O ( ln ln n ) m = \mathcal{O}(\ln \ln n) m = O ( ln ln n ) β 6 + m < 1 \beta \scriptstyle 6+m \normalsize < 1 β 6 + m < 1 O ( 1 ) + ln ln n \mathcal{O}(1) + \ln \ln n O ( 1 ) + ln ln n
這裡只的機率很小是指 Pr [ ¬ , E m ] \Pr[\neg , \mathcal{E}_m] Pr [ ¬ , 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} $$
⇒ Pr [ ¬ , E k ] ≤ 1 n \Rightarrow \Pr[\neg , \mathcal{E} \scriptstyle k \normalsize] \leq \frac{1}{n} \quad ⇒ Pr [ ¬ , E k ] ≤ n 1 Pr [ ¬ , E 6 ] = 0 \Pr[\neg , \mathcal{E}_6 ] = 0 Pr [ ¬ , E 6 ] = 0
More Discussion
l l l 第 2 步變為 Pr [ , j , is red , ] ≤ ( β k n ) l \Pr[ , j , \text{is red} ,] \leq (\frac{\beta_k}{n})^l Pr [ , j , is red , ] ≤ ( n β k ) l l l l ≥ k \geq k ≥ k
$$ \boxed{\frac{\beta_{k+m}}{n} = \frac{1}{e} \, (\frac{e \beta_k}{n})^{l^m}} $$
當 m = O ( ln ln n ln l ) m = \mathcal{O}(\frac{\ln \ln n}{\ln l}) m = O ( l n l l n l n n ) β 6 + m < 1 \beta \scriptstyle 6+m \normalsize < 1 β 6 + m < 1
What if β k \beta_k β k
That is, 第 4 步的 bound 並不足夠小，也就是隨著 β k \beta_k β k exp ( − β k 2 n ) \exp(-\frac{\beta_k^2}{n}) exp ( − n β k 2 ) > 1 n 2 > \frac{1}{n^2} > n 2 1 ⇒ β k < 2 n ln n \Rightarrow \beta_k < \sqrt{2n \ln n} ⇒ β k < 2 n ln n k ⋆ k^\star k ⋆ k ⋆ = ln ln n ln 2 + O ( 1 ) k^\star = \frac{\ln \ln n}{\ln 2} + \mathcal{O}(1) k ⋆ = l n 2 l n l n n + O ( 1 )
可以證明有 bin 超過 k ⋆ + 2 k^\star + 2 k ⋆ + 2
Please enable JavaScript to view the comments powered by Disqus.
