频率矩问题

不同阶数给频率分布施加不同的放大方式：$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$ 是算法参数，引用空间界时也不能固定后隐藏。

对 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$ 的共同记号迁移保证。