频率矩问题

不同阶数给频率分布施加不同的放大方式：$F_0$ 只看支持集，$F_1$ 线性累计质量，$F_2$ 把碰撞和集中度放大，更高阶则越来越受最大坐标支配。它们共用一个记号，却不是把同一估计器的指数换掉就能互相得到。

AMS 二阶矩估计器 ​

选择四重独立且各自均匀取值的随机符号 ${\xi }_i\in \{-1,+1\}$，维护

更新 $(i,\mathrm{\Delta })$ 只做 $Z\leftarrow Z+{\xi }_i\mathrm{\Delta }$，因此同一状态同时支持正负更新。展开可得

因为交叉项的符号期望为零。对频率 $(3,1)$，符号同号时 $Z^2=16$，异号时为 4，二者平均为 10，恰等于 $3^2+1^2$。

单副本波动很大。四独立性用于控制四阶矩与方差；重复独立副本先分组取均值，再取组间中位数，可把相对误差与失败概率降到目标范围。只写“两两独立使估计无偏”不足以支持集中保证。

各阶任务为何不同 ​

$F_0$ 只看支持集，不随同一键重复增长；$F_1$ 在当前频率非负的流中是带符号更新增量的总和，单位插入时才是更新数 $m$，无需 sketch；$F_2$ 测量碰撞集中度。更高阶 $p$ 更受最大坐标支配，流算法空间随 $p$ 出现相变，不能把 AMS 的平方换成任意指数就得到通用估计器。

General turnstile 中通常定义

若对奇数 $p$ 直接使用 $f_i^p$，正负坐标会抵消，甚至产生负的“矩”，失去范数语义。严格 turnstile 的非负性又要求每个前缀成立，不能只检查最终向量。

近似与输入边界 ​

乘法 $(1\pm \epsilon )$ 在 $F_p=0$ 时要求精确返回 0，接口应单独约定空流或完全抵消状态。若结果只有加性误差，必须说明相对于 $\Vert f{\Vert }_1^p$、尾部范数还是其他尺度；不能把两者统称“近似”。$p$ 是算法参数，引用空间界时也不能固定后隐藏。

用同一条流比较精确与近似任务 ​

INDEX 到流式空间的归约理路通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。提供了一个可复算的比较：前 $n$ 项为 $(1,x_1),\dots ,(n,x_n)$，最后追加 $(i,1)$。当 $x_i=0$ 时全异；当 $x_i=1$ 时一个频率为 2，其余 $n-1$ 个为 1。因此

$F_0$ 和 $F_2$ 都能精确解码该位，故单遍精确算法在 $U=2n,m=n+1$ 的这组输入上需要 $\mathrm{\Omega }(n)$ bits；$F_1$ 对两类输入完全相同，不能承担这项解码。对 $x=10110$，追加 $(4,1)$ 得 $(F_0,F_1,F_2)=(5,6,8)$，追加 $(2,1)$ 则得 $(6,6,6)$。

对二阶矩，加性误差严格小于 1 时，两种答案仍能由阈值 $n+2$ 分开；相对误差却需要 $\epsilon <1/(n+2)$。固定常数相对误差无法维持这个间隔，所以精确二阶矩的线性空间下界与 AMS 的小空间近似并不冲突。成功概率相同也不足以迁移下界，必须同时保持输出误差尺度。

对 turnstile 流中的二阶矩 $F_2$，AMS 二阶矩 Sketch理路AMS 二阶矩 SketchAMS sketch · Alon–Matias–Szegedy sketch用随机符号线性投影的平方无偏估计频率向量二阶矩，并以均值—中位数组合放大。用固定随机符号将频率向量投影为一个标量，再以重复和中位数控制方差与失败概率。其线性更新和可合并性来自同一随机投影；它直接实现的是 $F_2$ 估计，而不是所有 $p$ 的频率矩或逐项 heavy-hitter 恢复。

频率矩统一了 distinct counting、流长、self-join size 与分布集中度等流式目标，并为 AMS、CountSketch 等线性摘要规定了精确估计对象。选用算法时还要固定 insertion-only 或 turnstile 语义、误差尺度与 $p$ 的取值，不能只按 $F_p$ 的共同记号迁移保证。