Forget_ever
很久没写快速排序了，没事的时候尝试着回忆了一下，顺便结合泛型编程的思想，将代码改成了void * ，满足所有数据类型的要求。
快速排序最大的问题就是在不额外赋值空间的情况下，怎么做到在不变的空间内，按照快排的思想，将base基点左侧都放上比它小的值，base基点右侧都放上比它大的值。
很多时候base基点直接选择的是第一个元素，也是为了方便我们的排序。
但为了防止特殊情况出现，导致快排效率不高，base基点的选择最好是随机的，但只要将随机选中的base和第一个位置的元素交换位置就可以同样达到我们想要的效果。所以思想的讲解主要从base基点作为第一个元素来讲解。
more >>首先再来简单回顾一下莫比乌斯反演
莫比乌斯函数定义如下
$$
n = p_1^{k_1}p_2^{k_2}…p_t^{k_t} \quad \mu(n) = \begin{cases} (-1) ^ t & s.t. \quad k_1=k_2=…=k_t=1 \ 0 & o.w \end{cases}
$$
莫比乌斯函数通过容斥原理可证很容易证明如下两个很重要的式子，可参考贾志鹏线性筛。
$$
n = \sum_{d|n} \phi(d) \\
[n=1] = \sum_{d|n} \mu(d)
$$
$\phi(n)$: # of x (s.t. gcd(x,n)=1 and x<=n)
比如在贝叶斯概率计算中，我们总是利用先验概率来计算后验概率，样本太大，我们总是利用采样的方法来计算先验概率，但为什么采样得到的概率分布就能代替总的样本概率分布呢，其背后就用到了极大似然估计的思想，因为在得到采集样本这个事件A的条件下，只有总样本也满足相同的概率分布，这个事件A发生的可能性才达到最大值。
最大似然估计的目的就是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。
原理：极大似然估计是建立在极大似然原理的基础上的一个统计方法，是概率论在统计学中的应用。极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。通过若干次试验，观察其结果，利用试验结果得到某个参数值能够使样本出现的概率为最大，则称为极大似然估计。
more >>###HBase代码在hadoop集群下运行找不到hbase相关类
hbase代码引入的jar都可以在hbase/lib的目录下找到，一次性都导入，代码就能运行了。单纯的hbase代码是可以直接作为普通java程序运行的，不用再hadoop集群下运行。
但是hbase相关的读写写到了MapReduce的操作中，就需要打成jar包，在maven下，将hbase/lib下的jar包都导入项目，然后代码就不会报错了，然后rebuild project 完成后，就可以通过mvn compile,mvn package将代码打包了。
more >>
用maven创建一个项目，基本的MapReduce，我暂时觉得只用到了两个jar包，所以把依赖写到pom.xml中
|
|
关于具体的依赖包的信息查询可以参考maven2库
比如写了一个WordCount的代码，写完之后发现ide里各种报错，说明包没导入，添加依赖包(File->ProjectStructure->libraries，可以自己下载好上面的两个包(commons-cli-1.4和org.apache.hadoop:hadoop-core:1.2.0)导入，也可以用里面的maven自己帮你下载好导入，查找对应包只要把名字输入就行)。
将这个maven项目打成jar包，就是在主目录下mvn compile 然后mvn package，那么打包出来的jar包在target目录下，就是可以直接使用的了，你要用的对应的类就是你src/main/java 之后的路径，如果你的路径是src/main/java/test/WordCount.java ，那么使用的时候就要hadoop jar name.jar test.WordCount.java /input /output
上述的过程是打包MapReduce程序在hadoop下运行的方法，但是代码出错调试很不方便，你运行的代码本地就能跑，只不过不是分布式环境，但结果正确在拿到hadoop上运行方便很多。
主要配置就是在工具栏运行按钮旁边的小框中点出Edit Configuration，然后点进Application，设置参数，就是输入目录和输出目录（如果你Main函数是写死的输入输出目录就不用参数），将你要运行的类Main Class作为主类，然后确定工作目录没问题即可，你创建的输入输出目录也都是相对于工作目录而言的 。
more >>初始赌博1元，每次输，就在上一次基础上翻倍，那么第一次获胜的时候会赚1元
$2^n - \sum_{i=0}^{n-1}2^i = 1$
那么对于任何一个公平的博弈，$X_i$表示第i轮结束时拥有的财富，在游戏是公平的情况下：
$E(X_{i+1} | X_1,X_2,…,X_i) = X_i$
简单理解下上述的式子就是第i+1轮输赢的概率是相同的，所以相对上一轮来说期望的结果是和上一轮是相同的。
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)|\}$
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$
在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在一定的限制条件下提出了比马尔可夫定理更优秀的边界值。
预备知识
第一个式子的证明
$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)$
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}})$
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})$
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$.
上一个问题的解决方法是每次有放回的选择两个箱子，找到其中小球数量较小的一个，将球放进去，现在修改为有放回的选择d>=2的箱子，就是将上一个解决方案更一般化了，得到的箱子的最最大值逼近于$O(\log \log n / \log d)$,也就是说最大箱子球的数量在这个数量级下有着很高的正确率。
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：
jsonContent:
meta: false
pages: false
posts:
title: true
date: true
path: true
text: false
raw: false
content: false
slug: false
updated: false
comments: false
link: false
permalink: false
excerpt: false
categories: false
tags: true