随机算法概论
Union Bound：若算法失败概率为 \(\delta\)，则 \(Q\) 次询问中存在一次失败的概率可以放缩至 \(\le Q\delta\). 所以对于多组询问，只需要将失败概率降低至 \(\frac{1}{Q}\) 即可.
Markov Inequality：随机变量 \(X\ge 0\)，有 \(Pr[X\ge a]\le E[x]/a\). 考虑离散的情形会发现这是显然的.
这个告诉我们当我们某个算法有较好的期望结果，那么随机算法正确率也应该不低. Eg：给定无向图求一个边数大于一半的割. 考虑如果随机选择点作为左部的话那么每条边都有 \(1/2\) 概率在割中，所以期望是对的，于是直接这么做就好了.
Chernoff Bound：一组独立同期望的随机变量 \(X_1,\dots,X_n\)，其中期望 \(\mu\ge t\). 令 \(X=\sum X_i/n\)，则对任何失败概率 \(\delta\)，有 \(Pr[|X-\mu|\ge \sqrt{\frac{\log(1/\delta)}{nt}}\mu]\le \delta\). 即相对误差能被随机次数以 \(O(\frac{1}{\log \delta})\) 的量级去控制.
随机排列：一种生成方式是，从 \(j=n\to 1\)，随机 \(k\in[1,j]\) 并交换 \(a_j,a_k\). 还有一种方法是每个数随机赋一个 \([0,1]\) 实数然后排序. 后者由于每个元素独立采样有局部性，易于动态维护；前者复杂度线性.
Rejection Sampling：给定均匀 \(\{0,1\}\) 生成器 \(F\)，如何构造一个 \(p\) 概率的 \(\{0,1\}\) 生成器？考虑 \(p\) 的二进制构造，从最高位开始，若 \(F\) 得到 \(1\) 就返回 \(p_h\).
1-median 问题
一个题目：给定 \(k\) 维空间的 \(n\) 个点 \(a_i\)，每次查询给定一个问询点，估计这个问询点到所有点的距离和.
一种特殊情况：所有数据点都到某个 \(c\) 的距离在 \([r,2r]\). 我们直接随机采样，然后以这些样本来估计答案.
听上去很奇怪. 但是令 \(f_i\) 表示第 \(i\) 个点的距离，则由于在环上，所以 \(|f_i-f_j|\le |a_i-a_j|\le 2r\).
我们计算一下误差，由相加误差版本的 Chernoff Bound 知 \(Pr[X-E[x]\ge z]\le 2\exp(-\frac{2z^2}{n(r-l)^2})\)，\(x_i\in[l,r]\). 那么我们就可以知道上述误差在 \(\epsilon|P|r\). 于是取采样数 \(m=O(1/\epsilon^2\log(1\delta))\) 即可.
现在考虑总的情况. 我们固定一个点 \(c\)，然后令 \(D=\sum |c-a_i|\)，\(r_0=\epsilon D/n\)，\(r_i=2r_{i-1}\)，令属于第 \(i\) 个环的集合为 \(P_i\)，那么就有总误差 \(\epsilon\sum |P_i|r_i\le \epsilon \sum_i \sum_{x\in P_i} |x-c|=\epsilon D\). 于是尽量取 \(D\) 小的 \(c\) 即可. 一个完全可行的做法是取中位数.
这个算法也可以推广到 \(k-median\)，即给定 \(k\) 个闻讯点，然后计算最近邻距离之和. 做法是做聚类，然后每类做环划分.
哈希
Consistent Hashing
现在一个场景，有很多份文件，每个文件要单独存到一个服务器上. 但是不仅文件会变多，服务器也会变多. 那么考虑如下方法：设计一个任意将文件 & 服务器都能映射到 一个随机整数的函数 \(h\)，将 \(h\) 的值域写成一个环，那么每个文件和服务器就都能唯一对应着环上的一个位置. 然后我们每次无论是新加服务器还是新加环，只需要像某个叫 Toilet 的 Ucup 题那样做就行了（即对于每个文件，找到其往逆时针走的第一个空着的服务器）.
Count-min Sketch
输入整数，然后输入结束过后要近似求出每个数的出现频率. 当然是要小于线性的空间.
直接简述方法：设计若干个哈希，然后求 \(i\) 的出现频率只需要取这若干种哈希中的结果的 \(\min\) 即可. 这听上去就非常的对！
毛估估一下，首先对于一个哈希，设 \(m\) 是哈希值域. 期望是 \(c_x+n/m\). 然后用 Markov Inequality 得知成功概率为 \(\frac{1}{\epsilon m}\). 取 \(m=\frac{2}{\epsilon}\) 就有 \(1/2\) 的概率. 于是多哈希几次显然正确.
Heavy Hitter求出至少出现了 \(n/k\) 次的元素，并且要满足返回的元素每个都不少于 \(n/k-\epsilon n\) 次. 即在保证找出所有 heavy hitter 的情况下，假阳性也足够 heavy. 我们可以直接使用上述的 Count-min sketch 来解决这个问题.
Bloom Filter
随机 \(T\) 个哈希函数. 每次插入的时候将所有 \(A[h_j(a_i)]\)，\(j\in[1,T]\) 设为 \(1\). 并且在问询的时候，只有所有 \(A[h_j(a_i)]=1\) 才返回 \(1\).
容易发现这样只会有小概率的假阳性.
推导暂时省略.
\(A\) 的大小只需要开 \(\frac{n\ln \delta^{-1}}{(\ln 2)^2}\)，\(T\) 开 \(\log_2(\delta^{-1})\). 就能将失败概率控制在 \(\delta\).