一致加权抽样

一段随机对数网格夹住当前权重 ​

由向下取整的定义，$y_i\le s_i<z_i$。把权重画在对数轴上，网格间距为R，偏移由β决定；y是权重所在格子的下端点，z是上端点。在同一格子内改变s，t、y、z、a全部不变。

仅凭这幅图还不能证明抽样正确。网格间距的分布、纵坐标y与比赛分数a的独立性，决定胜出后高度是否仍均匀。下面把这些量一起计算。

完整变量变换给出独立的两段指数量 ​

先固定一个正实权s，省略坐标下标。设 $B=\{\log s/R+\beta \}$ 为小数部分。给定任意R，均匀β加常数后取模1仍均匀，所以B与R独立，联合密度为 $r{e}^{-r}$，其中 r>0、0<b<1。

令 $V=RB$、$W=R(1-B)$，反变换为 $R=V+W$、$B=V/(V+W)$，Jacobian绝对值为 $1/(V+W)$。这个映射在正象限与 $r>0,0<b<1$ 间是一一光滑对应；可先在远离边界的紧区域换元，再递增覆盖整个正象限，零测边界不影响密度。利用多元换元公式理路多元积分换元定理Multivariable change of variables theorem · Jacobian substitution theorem · 重积分换元在C¹微分同胚和紧Jordan域上证明绝对Jacobian换元公式，区分有向符号、零测边界和重复覆盖。，

因此V、W是相互独立的速率1指数变量理路指数分布Exponential distribution具有恒定失效率和连续无记忆性的非负等待时间分布。。格点公式又给出

对0<u<1，$\text{Pr}(e^{-V}\le u)=\text{Pr}(V\ge -\log u)=u$，故y均匀于(0,s)。y只依赖V，z只依赖W，两者独立。

C与V、W独立。令 $a=C{e}^{-W}/s$，因 $e^{-W}$ 均匀于(0,1)，给定C=c时a均匀于(0,c/s)。其密度为

a为速率s的指数变量，而且与y独立。这一联合结论比“y边缘均匀”“a边缘指数”分别成立更强：若两者相关，按最小a选坐标可能把对应y的分布筛偏。[1, §3.3给出同一联合分布的另一推导]

指数竞赛如何给出均匀面积点 ​

不同坐标参数独立，所以 $a_i\sim \mathrm{Exp}(s_i)$ 相互独立。i以时间a胜出的密度为

从0积分到无穷，胜出概率为 $s_i/\sum _j{s}_j$。同时 $y_i$ 独立于全部比赛分数，获胜事件不改变它在(0,$s_i$)的均匀分布。于是“先按面积比例选坐标，再在该高度内均匀选点”成立，面积均匀性得到证明。

共享参数还必须证明嵌套一致性 ​

现固定整批随机参数，对任意 $v\le s$ 比较两次运行。权重降低会使t不增，z不增，故a不减；零权坐标直接退出比赛。假设s的胜出点为(i,y)，并且y≤$v_i$。因为 $y\le v_i\le s_i<z_i$，$v_i$还在原网格区间里，胜出坐标的t、y、a不变。其它坐标的a只能增加，因此i仍胜出，输出同一点。

此处不能给v重新抽R、C、β。均匀性证明把s视为固定输入；一致性证明把参数视为固定，比较多个权重。两步处理的是不同方向的条件，合在一起才构成完整接口。

从并集面积推回碰撞等式 ​

令 $u_i=max(s_i,v_i)$，$m_i=min(s_i,v_i)$。先考察共享参数对u抽出的点p。若p落在 $A_m$，由一致性，它在s、v两侧都保留，因此指纹相同。

反过来，p必至少属于s、v中的一侧，因为每个坐标的最大高度来自其中一侧；一致性使该侧指纹等于p。若两侧指纹相同，另一侧也输出p，故p必须落在交叠面积内。碰撞与“u的均匀面积点落在m中”恰好等价，概率就是 $\sum m_i/\sum u_i$。[2, §2，Lemma 1的统一原理]

不改变格点，与越过格点 ​

两个坐标都手工指定 $R=\log 4$、$\beta =1/2$，并设 $C_0=2$、$C_1=1$。该轨迹用于精确理解操作，不是对连续随机源的离散替代。

对 $s=(1,5)$，坐标0有 $t_0=0,y_0=1/2,z_0=2,a_0=1$；坐标1有 $t_1=1,y_1=2,z_1=8,a_1=1/8$。胜出指纹为(1,1)。把权重缩为v=(1,3)，坐标1仍在区间[2,8)，所以仍输出(1,1)。

继续缩为w=(1,1)，坐标1变成 $t_1=0,y_1=1/2,z_1=2,a_1=1/2$，仍胜出但指纹成为(1,0)。这时旧点高度2已不属于w，嵌套一致性本来就没有要求保留它。

只保存坐标会在一维立刻失败 ​

只有一个正坐标，权重分别为1和2。加权Jaccard为1/2，但两次输出坐标必定相同，若省掉t，错误碰撞率恒为1。保留完整(i,t)后，两次是否落在同一共享格子才是正确碰撞事件。

普通MinHash对支持集做去重，面对s=(1)、v=(2)也总得到同一键。它回答的是两个支持集是否相似，不能承担权重比例这一不同目标。

零、缩放与浮点临界点 ​

权重为零时面积区间为空，禁止计算log0；所有坐标都为零时只返回 $\mathrm{\perp }$。负权重不能解释成区间高度。两个向量同时乘同一正数，不改变加权Jaccard，但在固定随机参数下可能跨网格，指纹未必逐次保持不变。

理想证明使用精确实数、连续Gamma/Uniform和精确floor。数值实现计算 $\log a_i=\log C_i-R_i(t_i-{\beta }_i+1)$，比较log分数以避免直接构造极大z或极小a；输出整数t，避免比较浮点高度是否恰相等。这降低部分数值风险；若对数格点或分数出现非有限中间值，附件明确拒绝该参数。但在floor的整数边界附近仍可能舍入到相邻格子。

附件显式将其标为浮点教学模型。它验证给定数值参数的轨迹、缩权不变量及碰撞与并集点的对应，并用模拟频率作诊断；这些有限检查不证明理想连续碰撞概率，也不提供任意动态范围的逐位精确实现。

副本、稀疏访问和真实成本 ​

独立重复q次构造，每次在两个输入间共享参数，可把完整指纹的碰撞均值作为 $J_w$ 的无偏估计；方差和Hoeffding界与MinHash的独立Bernoulli副本相同。若所有副本复制同一批参数，就没有增加独立信息。

若输入已按不同正权坐标稀疏列出、每个参数能常数时间读取，且log、exp、floor按单位成本的实数RAM计算，q副本需 $O(q(\mathrm{nnz}(s)+1))$ 时间，只保留每个副本当前最小分数和指纹需O(q)个状态。公共随机参数表若为全部d个坐标显式生成，另占O(qd)空间和生成成本，不属于每份向量的小摘要。

附件的可追踪版本扫描长度d的稠密权重数组，还收集所有正权候选以供复核，因此单副本实际时间O(d+1)、辅助记录数O(nnz(s)+1)。若只需最终指纹，可边扫描边维护最小者，省去候选列表。有限精度随机数的生成和高精度超越函数成本不能直接套用理想实数RAM。

相似度指纹不是子集总量抽样 ​

优先级抽样理路优先级抽样Priority sampling以权重除以独立随机数构造优先级，保存k个样本和额外阈值，证明固定子集总量无偏及k≥2时的方差估计。也使用非负权与共享随机键，但其目标是固定子集的加权总量，需要保留记录和阈值后作逆概率修正。本页的(i,t)则专门支持两向量相似度的碰撞检验，单个指纹不能恢复任意子集总权重。

共享随机键终结任务要求同时交出y、z、log分数、完整二元组、缩权是否仍覆盖旧点，以及一个“只保存坐标”的失败例。读者最终应能区分算法的确定性一致性、一般概率证明和有限数值诊断。