随机 Hash:堆叠必要条件
如果我们有一种方法来检验某个对象的某个性质,当对象满足这个性质的时候,这个方法必然能使该对象通过检验;否则这个方法会使该对象以 \(p\) 的概率通过检验。那么我们将得到一个极可能正确的检验方法:连续使用前述方法检验该对象足够多次。误通过检验的概率 \(x\) 将随检验次数 \(m\) 的提升而迅速降低,因此我们的方法是极可能正确的。
当然,我们不能无限制地提升检验次数,这会让我们的检验速度变低。那么,我们应该怎样选择检验次数,才能使 错误率 \(x = p^{m}\) 被控制到一个可以接受的范围内?
怎样的错误率是可以被接受的?
不难发现,可以被接受的错误率与实验次数 \(n\) 有关。在具体的题目中,我们几乎要在每一次实验中都不误判,除此之外的结果都难以接受。因此,\(n\) 越大,可以被接受的错误率就越小。
下面是当错误率 \(x\) 和实验次数 \(n\) 在某个量级的时候,通过所有实验的正确率表格。(即通过所有实验不报错的概率)
单次错误率 (\(x\)) / 实验次数 (\(n\)) | \(10^5\) | \(10^6\) | \(10^7\) | \(10^8\) |
---|---|---|---|---|
\(10^{-5}\) | \(0.3679\) | \(0\) | \(0\) | \(0\) |
\(10^{-6}\) | \(0.9048\) | \(0.368\) | \(0\) | \(0\) |
\(10^{-7}\) | \(0.9900\) | \(0.9048\) | \(0.3679\) | \(0.0000\) |
\(10^{-8}\) | \(0.9990\) | \(0.9900\) | \(0.9048\) | \(0.3678\) |
\(10^{-9}\) | \(0.9999\) | \(0.9990\) | \(0.9900\) | \(0.9048\) |
这里的实验次数一般要考虑到数据组数或者测试点数量(毕竟我们不想在 CF 中 WA 哪怕一个点对吧?)。
如果对单次正确率有自信,可以直接使用伯努利不等式:
\[(1-x)^{n} \geq 1 - nx \ \ \ (x > -1,n \geq 1) \]该不等式表明当我们足够悲观(直接认为错误率为单次错误率乘实验次数)时,正确率也是有保障的。
当单次错误率在 \(10^{-9}\)(\(10^{-8}\) 看上去不错,但是接近 \(10\%\) 的错误率不够小)的时候,我们的总体正确率都是非常乐观的,因为几乎没有题目会实验 \(10^{8}\) 次。
当单次错误率较高的时候,我们有几乎没有代价的降低错误率方法:重复随机。选取合适的重复随机次数,将单次错误率维持在 \(10^{-9}\) 级别,我们就可以认为这是可以接受的错误概率。
具体的错误率分析
Sum Hash 一例:QOJ 5254 Differences
考虑答案串,其它每个字符串都和它有 \(m - k\) 个相同的字符。必要条件呼之欲出:和该字符串相同的位恰有 \((n-1)(m-k)\) 个。
进一步地,给每个字符串随机赋权 \(w_i\)。枚举答案串的每一位,统计这一位和答案串相同的串的权值和。那么,仅当权值和为 \(sum(m - k)\) 时,答案串合法。
考虑分析错误率。当某一种权值 \(w_i\) 并非出现了 \((m-k)\) 次时,考虑固定其余的 \(w_j\) 不变,值域内至多只有 \(1\) 种 \(w_i\) 会使得它和 \(sum(m-k)\) 相等,因此错误率可以近似看作 \(1/V\)。
Sum Hash 一例:CF 1746F Kazaee
给每种数赋随机权值然后检验区间和是否是 \(k\) 的倍数。此处值域可看作 \([0,k)\),那么当随机权值取遍 \([0,k)\) 的时候,固定其余的随机权值不变,类似的分析可以分析出:错误率至多 \(1/2\)(当 \(k = 2\) 的时候达到最高)。
此时需要将随机次数提升到 \(25\) 次左右(\(2 \times 10^{-8}\) 左右的错误率)。
Xor Hash 一例:CSP 2022 星战
前面的部分略去。
首先不难分析出按位独立。然后,每一位非法时错误率约 \(1/2\)(套用 Sum Hash 时的分析方法:固定其余不变,改变钦定的关键元素的权值),因此错误率为 \((0.5)^{L}\),其中 \(L\) 为向量长度。
Xor Hash 另一例:Dzy loves Chinese
这里我们需要把随机权值当成 \(2^i\) 使用并插入进线性基里。这要求我们每次取样的大小必须远小于向量位长。我们认为一次错误是误把线性无关组判断为线性相关组,即插进线性基失败了。
如果我们的向量长度为 \(L\),每一位均匀取 \(0/1\),那么我们可以近似估计错误率:第 \(i\) 个向量插入时已经有 \((i-1)\) 位有主元,从而有 \(\frac{1}{2^{L-{i-1}}}\) 的概率被前 \(i\) 个向量线性表出(考虑将有主元的位消成 \(0\),此时只有 \(\frac{1}{2^{L-i-1}}\) 的概率满足整个数就是 \(0\);其它情况下可以找到一位作为主元)。
因此,正确率为 \((1-\frac{1}{2^L})(1-\frac{1}{2^{L-1}})(1-\frac{1}{2^{L-2}}) \cdots (1 - \frac{1}{2^{L- n + 1}})\),其中 \(n\) 是取样大小。这也和蒙特卡洛方法得出的结果大致吻合。
标签:10,Hash,错误率,闲话,检验,随机,权值 From: https://www.cnblogs.com/Meatherm/p/18301654