AMS 二阶矩 Sketch

无偏与四阶矩 ​

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

控制 $\mathrm{Var}(Z^2)$ 需要展开四个符号的乘积，故 4-wise independence 是自然充分条件；仅 2-wise 不能自动控制四阶矩。标准计算给 $\mathrm{Var}(X)\le 2F_2^2$ 的量级。

置信放大 ​

单个 $Z^2$ 方差很大。每组平均 $\mathrm{\Theta }(1/{\epsilon }^2)$ 个独立副本，经 Chebyshev 得相对误差 $\epsilon$ 的常数成功率；再取 $\mathrm{\Theta }(\log \left(1/\delta \right))$ 组平均值的中位数，把失败率降到 $\delta$。空间还要乘每个计数器存储位宽。

更新例子与边界 ​

同一键多次正负更新只改变一个带固定符号的计数器，最终恰按净频率进入 $Z$；这展示线性 sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。 可合并。一次 $Z^2$ 偶然接近零不说明 $F_2$ 小，不能省略重复。均值和中位数的层次若颠倒，方差缩减与尾部放大的证明也随之失效。

位空间与哈希种子 ​

若流总绝对更新量为 $L_1$, 则 $|Z|\le L_1$，一个计数器需 $O(\log L_1)$ 位，而不是一个抽象“字”。4-wise independent 符号可由有限域低次多项式生成，种子空间也要计入摘要。

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

单个 AMS 投影的二阶矩可控但方差较大；Chebyshev 不等式公理库Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。把方差界转成常数成功概率，再由独立重复、组内平均和组间中位数把失败概率降到 δ。

更新吞吐与查询时机 ​

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

因此朴素每次更新需计算并写 $\mathrm{\Theta }({\epsilon }^{-2}\log \left(1/\delta \right))$ 个投影；空间同阶乘以单计数器位宽。批量 SIMD 可以改善常数，却不会让所有副本共享同一个符号，因为组内独立性正用于降低方差。

查询时先对每个计数器平方，再在组内平均、组间取中位数；在投影阶段提前平方会失去后续负更新抵消，也无法合并流片段。若采用模整数避免溢出，模回绕后的平方不再是实数上的 $F_2$ 估计，需另做恢复分析。