AMS 二阶矩 Sketch

无偏与四阶矩 ​

展开平方，异项因 $\mathbb{E}[s_i{s}_j]=0$ 消失：

控制 $\mathrm{Var}(Z^2)$ 需要展开四个符号的乘积，故 4-wise independence 是自然充分条件；仅 2-wise 不能自动控制四阶矩。展开后得到 $\mathrm{Var}(X)=2(F_2^2-\sum _i{f}_i^4)\le 2F_2^2$。

置信放大 ​

取 $0<\epsilon <1$、$0<\delta <1$。当 $F_2>0$ 时，每组平均 $a=\lceil 8/{\epsilon }^2\rceil$ 个独立副本，方差至多 $2F_2^2/a$。由Chebyshev 不等式理路Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。，组均值偏离 $F_2$ 超过 $\epsilon F_2$ 的概率至多 $1/4$。

再取独立的奇数 $b$ 组，返回组均值的中位数。若中位数失准，至少一半组失准；对坏组的 $[0,1]$ 指示变量使用Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，概率至多 $e^{-b/8}$。因此取最小的奇数 $b\ge 8\ln \left(1/\delta \right)$ 即可。若 $F_2=0$，净频率全零，每个 $Z$ 也恰为零，输出精确为零。

这套组内平均、组间中位数的机制可抽成 有限方差均值估计接口理路分组均值中位数估计Median-of-means estimator · MoM 均值估计将独立样本分成不相交的组，先平均再取中位数，以有限方差取得依赖置信度的均值误差保证，并明确组数、余数和尺度条件。。通用页面另行处理固定样本数的丢余、未知均值与已知方差上界；此处的 $F_2$ 目标、随机符号副本和相对误差预算仍由 AMS 模型负责。

更新例子与边界 ​

同一键多次正负更新只改变一个带固定符号的计数器，最终恰按净频率进入 $Z$；这展示线性 sketch理路线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。 可合并。例如 $f=(1,1)$ 而符号取 $(1,-1)$ 时，$Z^2=0$，但 $F_2=2$；独立重复用来减小这种抵消造成的估计波动。均值和中位数的层次若颠倒，方差缩减与尾部放大的证明也随之失效。

位空间与哈希种子 ​

若流总绝对更新量为 $L_1$, 则 $|Z|\le L_1$，一个计数器需 $O(\log (2+L_1))$ 位。令 $q$ 为不小于 $max\{2,U\}$ 的最小二次幂，在二元有限域理路有限域Finite field · Galois field底层集合有限的域。 ${\mathbb{F}}_q$ 中嵌入所有键。独立均匀选择四个系数，用次数至多三的随机多项式求值，再取一个固定的非零二元线性坐标 $b$，并输出符号 $(-1{)}^b$；四个不同键的域值独立均匀，所得四个符号也独立均匀。每个副本的种子占 $O(\log (U+1))$ 位。

共 $ab=O({\epsilon }^{-2}\log \left(2/\delta \right))$ 个副本，因此计数器和种子的总位空间为

这还采用能容纳计数与种子的字长；逐位算术和哈希求值成本应另计。

两个 AMS sketch 只有使用相同符号函数时才能相加合并；独立副本的编号和种子必须对齐。合并后 $Z$ 等于两频率向量和的投影，平方应在合并后计算，不能把各自 $Z^2$ 直接相加。

更新吞吐与查询时机 ​

所有计数器都在一条更新到来时同步执行

因此朴素每次更新需计算并写 $\mathrm{\Theta }({\epsilon }^{-2}\log \left(2/\delta \right))$ 个投影；位空间还包括上述每个副本的种子。批量 SIMD 可以改善处理常数；各副本仍使用各自的符号函数，以实现组内独立重复。

查询时先对每个计数器平方，再在组内平均、组间取中位数；保留带符号的线性计数器 $Z$，才能继续处理负更新并合并流片段。若采用模整数避免溢出，模回绕后的平方不再是实数上的 $F_2$ 估计，需另做恢复分析。