m identical balls uniform independant put into n identical bins
相当于是找到一个 h: [m]->[n] 的映射
求每个桶至多一个球的概率（类生日重复问题）
$Pr = 1∗\frac{n-1}{n} ∗…∗\frac{n-m+1}{n} = \prod_{i=0}^{m-1}(1-i/n) \approx \prod_{i=0}^{m-1}e^{-i/n} = exp(-\frac{m(m-1)}{2n})$
求每个桶都有球的概率
这相当于是找一个 h : [m] -> [n]满射的概率。
也可以将模型转化成以前做过的扔骰子直到6面都出现的问题。
解决扔骰子问题
用E[i]表示扔出i-1个不同的面之后扔出第i个不同的面需要次数的数学期望，那么扔出i-1个不同的面，剩余的面数量就是7-i个，因为每一次扔骰子都是满足独立随机均匀分布的，那么Pr[new side at time i for one try] = 1-(i-1)/6，那么E[i] = 1/(1-(i-1)/6) = 6/(7-i)
E[diff 6 sides] = E[1] + E[2] + E[3] + E[4] + E[5] + E[6] = 1 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1
扩展扔骰子问题
假设骰子具有均匀的n个面，将所有面都扔到的数学期望
E[diff n sides] = $\sum_{k=0}^{n-1}{\frac{1}{1-k/n}} = n\sum_{k=1}^n\frac{1}{k} = nH(n)$。
针对原问题求解概率
$\Pr[X\ge n\ln n+cn]\lt e^{-c}$
证明：对于任意一个桶一个球都不存在的概率是$\left(1-\frac{1}{n}\right)^{n\ln n+cn}\lt e^{-(\ln n+c)}=\frac{1}{ne^c}.$
$\Pr[X\ge n\ln n+cn] \lt n*1/(ne^c) = 1/e^c$
求最重的桶中的球的数量
问题
n个桶中最重的桶的球的数量是多少，这个求解的保证是在大概率下满足要求，误差不超过1/n。
$X_i$作为桶i中的球的个数 $X_i = |h^{-1}(i)|$，求最大$max\{|h^{-1}(i)|\}$
性质
- $E(X_i) = E(\sum-{j=1}^m{Y_{ij}}) = m*1/n$
- m = n时，$O(\frac{logn}{loglogn})$ with high probability Pr >= 1-1/n
- $m=\Omega(n\log n)$时，$O(m/n)$ with high probability Pr >= 1-1/n
证明
m = n时 $Pr[max_i \space X_i \le 3 \ln \ln n / \ln n] \ge 1 - 1/n$
因为需要将精度满足在1/n的范围内，假定这时候满足要求的最大的桶放置的是t个球。那么就应该满足以下不等式
$$
Pr[max_i \space X_i \le t] \ge 1 - 1/n \rightarrow Pr[max_i \space X_i > t] < 1/n \\
$$
稍微调整一下t，上述的式子可以近似看作
$$
Pr[max_i \space X_i \ge t] \le 1/n
$$
也可以理解为
$$
Pr[\exists i: X_i \ge t] \le 1/n \quad 等价于 \quad Pr[X_i \ge t] \le 1/n^2
$$
所以现在只要找到对应的t值满足$\quad Pr[X_i \ge t] \le 1/n^2$即可。这个概率的意思就是第i个桶中至少含有t个球。因为m=n，所以相当于是从n个球中先取出t个放入第i个桶中，每个球放进第i个桶的概率满足均匀二项分布binominal(n, 1/n)，所以可以得到如下式子：
$$
\begin{aligned}
Pr[X_i \ge t] & \le \binom {n}{t}(1/n)^t \\
& = \frac{n!}{t!(n-t)!n^t} \\
& = \frac{1}{t!} \frac{n(n-1)(n-2)…(n-t+1)}{n!} \\
& = \frac{1}{t!} \prod_{i=0}^{t-1}(1-i/n) \approx \frac{1}{t!} \prod_{i=0}^{t-1}e^{-i/n} \\
& \le \frac{1}{t!}
\end{aligned}
$$
因为$t!\approx \sqrt{2\pi t}\left(\frac{t}{e}\right)^t$所以$Pr[X_i \ge t] \le 1/ \sqrt{2\pi t}\left(\frac{t}{e}\right)^t \le (\frac{e}{t})^t$。
当$t = 3 \ln n / \ln\ln n$:
$$
\begin{align}
\left(\frac{e}{t}\right)^t
&=
\left(\frac{e\ln\ln n}{3\ln n}\right)^{3\ln n/\ln\ln n}\\
&\lt
\left(\frac{\ln\ln n}{\ln n}\right)^{3\ln n/\ln\ln n}\\
&=
e^{3(\ln\ln\ln n-\ln\ln n)\ln n/\ln\ln n}\\
&=
e^{-3\ln n+3\ln\ln\ln n\ln n/\ln\ln n}\\
&\le
e^{-2\ln n}\\
&=
\frac{1}{n^2}.
\end{align}
$$
所以说当n=m的时候，箱子中球的最大数量是$t = 3 \ln n / \ln\ln n$,且在这个数量下达到很高的正确率，误差 不会超过1/n.$m=\Omega(n\log n)$时，$Pr[max_i \space X_i \le m/n] \ge 1 - 1/n$
Chernoff Bound
在n个相互独立的0,1随机变量 $X_1,X_2,…,X_n \in \{0,1\}$，令$X = X_1+X_2+…+X_n$，$\mu = E(X)$。
for any $\delta > 0$
$Pr[X \ge (1+\delta)\mu] \le (\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu$
$Pr[X \le (1-\delta)\mu] \le (\frac{e^{-\delta}}{(1-\delta)^{1-\delta}})^\mu$
更多有用形式的bounds
Let $X=\sum_{i=1}^n X_i$, where X1,X2,…,Xn are independent Poisson trials. Let $μ=E[X]$. Then
1.for $0<\delta<1$
$\Pr[X\ge (1+\delta)\mu]\lt \exp\left(-\frac{\mu\delta^2}{3}\right);$
$\Pr[X\le (1-\delta)\mu]\lt \exp\left(-\frac{\mu\delta^2}{2}\right);$
2.for $t \ge 2e\mu$
$\Pr[X\ge t]\le 2^{-t}.$
Chernoff Bound证明
Chernoff Bound在一定的限制条件下提出了比马尔可夫定理更优秀的边界值。
预备知识
- 马尔可夫定理 $Pr[h(x) \ge t] \le \frac{E[h(x)]}{t}$
- 矩生成函数 $M(\lambda) = E(e^{\lambda X}) = \sum_{k=0}^\infty\frac{\lambda^k}{k!} E[X^k]$ , $e^{\lambda X}$方便用泰勒展开成生成函数的形式，但这里证明用不到，只需要用到$E(e^{\lambda X}) =E(e^{\sum_{i=1}^n{\lambda X_i}})$
- $1+x \le e^x$ 就是将泰勒展开式只取前两项
第一个式子的证明
$s.t. \quad \lambda > 0$
$\begin{aligned} Pr[X \ge (1+\delta)\mu] &= Pr[\lambda X \ge \lambda (1+\delta)\mu] \ &= Pr[e^{\lambda X} \ge e^{\lambda (1+\delta)\mu}] \ & \le \frac{E[e^{\lambda X}]}{e^{\lambda (1+\delta) \mu}} \end{aligned}$
$E[e^{\lambda X}] = E[e^{\lambda \sum_{i=1}^nX_i}] = E[\prod_{i=1}^{n}e^{\lambda X_i}] = \prod_{i=1}^{n}E[e^{\lambda X_i}]$
因为X只有0,1的取值，所以令$p_i = E[X_i]$。那么$E[e^{\lambda X_i}] = (1-p_i)∗1+p_i∗e^\lambda = 1+p_i(e^\lambda -1) \le e^{p_i(e^\lambda-1)}$，所以
$E[e^{\lambda X}] = E[e^{\sum_{i=1}^n\lambda X_i}] = \prod_{i=1}^{n}E[e^{\lambda X_i}] \ \le \prod_{i=1}^{n} e^{p_i(e^\lambda-1)} = exp((e^\lambda -1)\sum_{i=1}^np_i) \\= exp((e^\lambda -1)\sum_{i=1}^nE[X_i]) = exp((e^\lambda -1) \mu) \ = e^{\mu(e^\lambda -1)}$
那么最后就可以求出：
$$
\begin{aligned} Pr[X \ge (1+\delta)\mu] &\le \frac{e^{\mu(e^\lambda-1)}}{e^{\lambda (1+\delta) \mu}} \end{aligned} \\
$$
这就能看出在这里定义$\lambda$的好处了，一开始限制$\lambda > 0$，那么只要大于0就可以任意取值，为了得到我们要的结果只要满足$(e^\lambda - 1) = \delta \rightarrow \lambda = \ln (\delta + 1)$
带入到分母就可以得到
$Pr[X \ge (1+\delta)\mu] \le (\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu$
第二个式子的证明
最关键的就是要利用马尔可夫定理，Pr[]里是满足大于等于的，这里很巧妙的还是$\lambda$，它取值小于0的时候，两边就变符号了.
$s.t. \quad \lambda < 0$
$Pr[X \le (1-\delta)\mu] = Pr[\lambda X \ge \lambda (1-\delta)\mu]$
之后只要按照前面的方法计算即可。
更多形式的证明
可以根据前两者的结论结合对应的限制条件简单证明得到。
Chernoff Bound在m个相同球放入n个相同桶问题求解桶内球最大值的应用
由前面的证明可以得到需要求解$Pr[X_i \ge t] \le 1/n^2$时t的值
因为这可以理解为将m个球放入n个桶中，第i个桶最后球的个数是不是大于等于t的。
所以对于每一个球能否放进第i个桶满足二项分布binomial(m , 1/n)，所以$\mu = m/n , \delta = 1-t/\mu=1-nt/m$.
所以在n=m的时候
$Pr[X_i \ge t] \le \frac{e^{t-1}}{t^t}$
令$t = \frac{e \ln n}{\ln \ln n}$
$ln(\frac{e^t}{t^t}) = t-1-t \ln t = \frac{e \ln n}{\ln \ln n}(1-\ln t) - 1 \ \le \frac{e \ln n}{\ln \ln n}(1-\ln t) = \frac{e \ln n}{\ln \ln n}(1-\ln(e \ln n) + \ln\ln\ln n)) \ = \frac{e \ln n}{\ln \ln n}(-\ln(e \ln n) + \ln\ln\ln n)) \ \le \frac{e \ln n}{\ln \ln n}(\frac{-2\ln \ln n}{e}) = \ln (1/n^2)$
由上述式子可得
$Pr[X_i \ge t] \le \frac{e^{t-1}}{t^t} \le e ^{\ln (1/n^2)} = 1/n^2$
所以这种条件下最多的桶中小球个数在大概率下(1-1/n)最多为$O(\frac{e \ln n}{\ln \ln n})$。
在$m=\Omega(n\log n)$时
根据后面扩展的定理
for $t \ge 2e\mu$
$\Pr[X\ge t]\le 2^{-t}.$
这里$\mu = m/n$
那么令$t = 2em/n$
$Pr[X_i \ge t] \le 2^{-2em/n} \le 2^{-2e\ln n} = (2^e)^{\ln 1/n^2} \le e^{\ln 1/n^2} = 1/n^2$
所以$t = 2em/n = O(m/n)$
Hoeffding’s Inequality
For independent r.v.(随机值) $X_1,X_2,…,X_n$，where $X_i \in [a_i,b_i]$
let $X = \sum_{i=1}^n X_i$，then:
for any t>0 ,
$P(X \ge E(X)+t) \le exp(- \frac{2t^2}{\sum_{i=1}^n{(b_i-a_i)^2}})$
$P(X \le E(X)-t) \le exp(- \frac{2t^2}{\sum_{i=1}^n{(b_i-a_i)^2}})$
(Convenient) Hoeffding’s Inequality
For independent r.v.(随机值) $X_1,X_2,…,X_n$，where $X_i \in \{0,1\}$
let $X = \sum_{i=1}^n X_i$，then:
for any t>0 ,
$P(X \ge E(X)+t) \le exp(- \frac{2t^2}{n})$
$P(X \le E(X)-t) \le exp(- \frac{2t^2}{n})$
Power of Two Choices
Algorithm design
m balls are thrown into n bins in the following manner: for each ball, choose tow bins uniformly and independentlyat random,then place the ball in the less loaded bin
（这里要注意的一点是选中的两个选择要理解为有放回的一个一个选择，所以是可以出现两次选择同一个箱子的情况）
the max loaded bin has O(log log n) balls , w.h.p.
Assume there are at most $\beta_i$ bins each containing at least i balls in the end
Probability that a ball increases # of bins containing at least i+1 balls? at most $(\frac{\beta}{n})^2$
In expectation , after n balls , # of bins containing at least i+1 balls is at most $n(\frac{\beta^2}{n^2})$
我对于上面两个式子是这么理解的，至少有i个小球的箱子个数是$\beta_i$。那么$\beta_{i+1}$是包含在$\beta_i$内的。
那么一个新的小球进来，最多使一个箱子从i个球变成i+1个球，这个的概率是$ \le (\frac{\beta_i}{n})^2$
那么一个球进来$\beta_{i+1} \le \beta_{i+1}+(\frac{\beta_i}{n})^2$
那么n个球进来，最多有$n(\frac{\beta_i^2}{n^2})$个箱子被提高到了i+1个球$\beta_{i+1} \le \beta_{i+1}+(\frac{\beta_i ^2}{n})$
因为初始的时候，所有箱子都是空的，那么扔了n个球进来后$\beta_0 = n \quad \forall_{i>0} \beta_i = 0$
$$
\beta_{i+1} \le \beta_{i}^2/n (上课内容这里是等于，我觉得应该是不大于)\\
\beta _{i} \le n/i ∗\beta_0 ^ 2 / (n∗n) = n/i \rightarrow \beta_4 \le n/4
$$
这个同样很好理解，因为选中一个那么最多可乘以n，那么至少每个要增加i次，所以数量就变成n/i了.
$$
\begin{aligned}
\beta_i & \le (\beta_{i-2}^2/n)^2/n \\
& \le \beta_{i-2}^4/n^3 \\
& \le \beta_{i-3}^6/n^5 \\
& \le \beta_{4}^{2(i-4)} / n^{2(i-4)-1} \\
& \le \frac{n}{4^{2^{i-4}}}
\end{aligned}
$$
那么就很容易得到 $\beta_i \le 1$ when $i \ge loglogn$.
Power of two choice 扩展 Power of d Choice
上一个问题的解决方法是每次有放回的选择两个箱子，找到其中小球数量较小的一个，将球放进去，现在修改为有放回的选择d>=2的箱子，就是将上一个解决方案更一般化了，得到的箱子的最最大值逼近于$O(\log \log n / \log d)$,也就是说最大箱子球的数量在这个数量级下有着很高的正确率。
