证明这家族哈希函数是3美元,但不是4美元 -- algorithms 领域 和 algorithm-analysis 领域 和 data-structures 领域 和 probability-theory 领域 和 hash-tables 领域 cs 相关 的问题

Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent


简体版||繁體版
1
vote

问题

中文

考虑哈希函数映射$ w $ -bit键到哈希值 $ {0,...,m-1 } $。假设$ w = cr $。以$ W $ -bit键$ x $作为一个 Vector $(x_1,...,x_c)$ c $ $ $ $ r $ r $键。

考虑散列家族:

$$ h = {h_ {t_1,...,t_c}:t_i in {0,...,m-1 } ^ {2 ^ r} } $$

其中

$$ h_ {t_1,...,t_c}(x)= sum limits_ {1 le i le c} t_i [x_i] mod m $$

证明,$ H $是3美元$ 3 $独立,但不是4美元$ 4。

$ h $是$ k $ $,如果输入$ x_1,...,x_k $和输出 $ v_1,...,v_k $,$ pr [h(x_1)= v_1 wedge ... wedge h(x_k)= v_k] = frac {1} {m ^ k} $

所以我当然可以看到为什么$ h $ 1 $ 1 $ 1美元和2美元,如果我们选择哈希函数的输入,则为2美元无关。但是,看到为什么这个家庭没有4美元,我觉得这很难以证明这个家庭是3美元的困难,我觉得很多。

所以对于家庭而不是4美元,如果我们有输入$ x_1,...,x_4 $和输出$ v_1,...,v_4 $,$ pr [h(x_1)= v_1 wedge ... wedge h(x_4)= v_4] not = frac {1} {m ^ 4} $。我正试图想到一个反例,在那里这是不是这种情况,但似乎我们需要,例如,$ x_4 $才能以$ v_4 $的方式通过$ v_1的组合来实现$ v_4 $。 v_2,v_3 $。但是,所有$ x_1,...,x_4 $都是$ w $ -bit键,所以即使$ x_4 $从$ x_1,x_2,x_3 $中拍摄的比特,输出$ v_4 $仍然是一些随机款对应于$ C $ $ r $ r $ -bit块访问每个$ t_i $。

在这里有什么东西吗?也许这是不可能的$ v_4 $的某种组合$ v_1,...,v_3 $,但我们如何显示$ h $的否则是$ 4 $ 4 $独立的?

英文原文

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys.

Consider the hash family:

$$H = \{h_{T_1,...,T_c}:T_i \in \{0,...,m-1\}^{2^r}\}$$

where

$$h_{T_1,...,T_c}(x) = \sum\limits_{1\le i \le c}T_i[x_i]\mod m$$

Prove that $H$ is $3$-wise independent, but not $4$-wise independent.

$H$ is $k$-wise independent if for inputs $x_1,...,x_k$ and output $v_1,...,v_k$, $\Pr[h(x_1) = v_1 \wedge ... \wedge h(x_k)=v_k] = \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x_1,...,x_4$ and outputs $v_1,...,v_4$, $\Pr[h(x_1)=v_1\wedge...\wedge h(x_4)=v_4]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x_4$ to be constructed in such a way that $v_4$ can be attained by some combination of $v_1,v_2,v_3$. However, all of $x_1,...,x_4$ are $w$-bit keys, so even if $x_4$ had bits taken from each of $x_1,x_2,x_3$, the output $v_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T_i$.

Is there something I'm missing here? Perhaps it's not possible for $v_4$ to be some combination of $v_1,...,v_3$, but how else would we show that $H$ is not $4$-wise independent?

              
 
 

回答列表

0
 
vote
vote
最佳答案
 

提示用于反驳4-wise独立:为简单来说假设$ c = 2 $,选择一些$ alpha neq beta $ long lengt $ r $,并考虑四个输入$ ( alpha, alpha),( alpha, beta),( beta, alpha),( beta, beta)$。

提示用于证明3-Wise独立:让三个输入是$ x,y,z $。如果有一些坐标$ i $,则为$ x_i,y_i,z_i $均为不同,我们完成了。否则,没有普遍存在的概要有坐标$ i,j $,因为$ x_i = y_i neq z_i $和$ x_j = z_j neq y_j $,我们再次完成。

 

Hint for refuting 4-wise independence: Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

Hint for proving 3-wise independence: Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x_i,y_i,z_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x_i = y_i \neq z_i$ and $x_j = z_j \neq y_j$, and we are again done.

 
 
         
         

相关问题

0  哈希函数订单从原产地最接近最近的船只  ( Hash function orders ships from closest to furthest from the origin ) 
假设我们有一个圆雷达,扫描 $ x ^ 2 + y ^ 2 leq z ^ 2 $ (一个圆圈) 。 我们希望设计一个哈希函数 $ h $ ,我们可以订购 $ n $ 从最接近的船只远离原产地。 我们希望在 $ theta(n)$ 时间中进行这个订购算法的<强>预期时间复杂性。< / p> 每艘船都有一个坐标 ...

1  关于佐色斯散系与碰撞机会的理论问题  ( Theoretical question about zobrist hashing and chances of collision with slight ) 
我有一个哈希表,它使用 zobrist散列计算各种位置的散列。哈希表用于查找各种换位。对于某些位置,我不想允许任何换位,但我仍然想要将位置存储在哈希表中。因此,我试图通过xor与保存位置结构的对象的内存地址来使职位的哈希统一。这是一些伪代码: hash = zobristHash(position); if (m...

8  如何计算线性时间最坏情况?  ( How to count in linear time worst case ) 
这个问题和这个问题让我思考一点点。用于排序长度阵列 $ n $ 使用 $ k $ $ O(n + k log k)$ ,我们需要能够在数组中存储值的数量。有一些建议,但我正在寻找在最坏情况下在线性时间做到这一点的方法。更具体地说: 给定列列表 $ a $ $ n $ 元素,其中 $ k $ 元素不同,确...

1  解释操作系统中的哈希页面表  ( Explain hashed page tables in operating system ) 
我有一个难以了解虚拟内存管理中使用的散列页表。这是我参考的幻灯片的图片: 我理解p是哈希,然后在页面表中检查哈希以进行匹配。什么是元素参考这里?这是页表输入吗?链均值是什么以及虚拟页码所在的地方? 某种物体可以帮助我理解流程图吗?谢谢 ...

5  哈希函数究竟是什么?  ( What exactly is a hash function ) 
我不知道我如何在生活中得到这种遥远,而不是真正掌握这一点,而是因为它发生了,我仍然非常困惑哈希函数的概念。我做了一些googling / wikipedia-ing,这就是我得到的: 哈希表很好,因为索引可以存储在较小的数组中 散列函数有点像均匀的随机数发生器,总是具有相同的种子但不是真的(而且我没有为什么) 但...

23  填充糕点的路由表如何工作?  ( How does populating pastrys routing table work ) 
我正在尝试实现糕点分布式哈希表,但有些事情正在逃避我的理解。我希望有人可以澄清。 免责声明:我不是计算机科学学生。我的生命中恰好是两种计算机科学课程,也没有与任何远程复杂的东西涉及。我多年来一直在用软件,所以我觉得我达到了实施任务,如果我能把头部包裹在想法上。所以我可能只是遗漏了一些明显的东西。 我已经阅读了作者发...

18  对于哈希表操作O(1)是什么样的数据?  ( For what kind of data are hash table operations o1 ) 
从答案到(当时)是哈希表查找o(1) ?,我收集哈希表有$ o(1)$最坏情况行为,至少摊销,当数据满足某些统计条件时,有技术有助于使这些条件宽。 但是,从程序员的角度来看,我不知道我的数据是什么:它通常来自一些外部来源。我很少有数据一次:通常会插入和删除以低于查找速率的速率发生,因此预处理数据以微调散列函数出局。 ...

-1  完美(或几乎完美)哈希函数,用于n位整数,恰好k位设置  ( Perfect or almost perfect hash function for n bit integers with exactly k bits ) 
我有一个数据集,其中包含2598960元元素(最多)52位长度的无符号整数。数据集具有完全5位设置的属性。 这只是1个数据集 - 我有类似的数据集的整数,精确地设置了6,7和9位。 鉴于数据集的这种特殊属性,有没有办法,我可以创建除了提出的方法之外的最小完美哈希函数在这里,我被拒绝,因为查找需要2个哈希并使用if语句...

3  是Von Neumann架构中的所有数据结构,基于阵列,也是阵列的?  ( Are all data structures in the von neumann architecture based on the array or a ) 
我现在是一个旧的Pythonista学习c以及如何实现各种数据结构和类型,例如二叉树和哈希表。了解后者,让我了解哈希函数服务器从密钥计算存储值的键上的键计算。我还了解到,树木可以存储为数组。鉴于阵列据说是有效的(对于查找,如果不是插入/删除),因为它们匹配了VON Neumann架构中的内存寻址的方式,这一般是所有其...

83  为什么最好在散列函数中使用素数作为mod?  ( Why is it best to use a prime number as a mod in a hashing function ) 
如果我有1到100的键值列表,我希望在11个桶中组织它们,我被教导形成mod函数 $$ h = k bmod 11 $$ 现在所有值都将在9行中一个接一个地放置。例如,在第一个桶中,将有0,11,22磅$ 0.在第二,将有1,12,23 dots $等。 让我们说我决定成为一个坏男孩,并使用非素数作为我的散...

0  使用MOD方法选择已知的单独链接数量键的数组大小  ( Choosing array size for known number of keys in seperate chaining using mod meth ) 
如果我们知道我们将得到的键数,我们如何计算阵列的大小我们需要在哈希表中存储我们的单独链条? 使用mod hashfunction ...

0  确定哈希函数的适当数量的桶  ( Determining an appropriate number of buckets for a hash function ) 
我想在我的哈希表中选择适当数量的存储桶,以获取此方案: 需要碰撞解决的哈希表来保存约10000条记录。每个记录都要被客户名称的2个字符初始索引索引,使用映射转换为整数:a = 01,b = 02,...,z = 26。预计每次要求搜索时,平均不超过8个比较。 如何根据此方案选择用于分区哈希函数的适当数量的桶,以及乘...

1  成功插入哈希表之前的平均碰撞次数  ( Average number of collisions before successful insertion into hash table ) 
我想在成功将项目添加到哈希表之前计算平均碰撞次数。让$ M $是哈希表$ H $的大小。 我在认为,由于它是一个线性探测,我们不知道哈希表中的自由插槽是哪里,首先插槽是免费的概率是$(mn)/ m $,其中$ n $表示金额'坏'插槽,即我们的哈希表中存储了$ n $商品。 如果第二个插槽是免费的,那么$(m-n)/...

5  使用散列在文本中计算不同的单词  ( Counting different words in text using hashing ) 
我仍然与哈希战斗,我问自己:使用哈希表计算文本中不同单词数量的最有效方法是什么? 我的直觉说,将HashCode函数应用于文本中的每个单词,结果我们将在不同的存储桶中具有不同的哈希值的单词,同一单词将具有相同的桶,因此我们将产生碰撞问题可以使用链接方法来解决。 它是这样的吗? ...

7  “分布式哈希表”一词的起源  ( Origins of the term distributed hash table ) 
我目前正在研究我的计算机科学文凭论点,并在分布式哈希表的区域中有一个话题。当然,我来到了这个问题是分布式哈希表来自。 (我知道它不是火箭科学,只需从分发哈希桌,但某个地方必须提出它)。 我读取的大多数纸张上的原始纸张上的原始纸张上的一致散列以及使用它的第一算法之一(例如,和弦)。我知道80年代分布式数据库有很多研究,...

1  挑战:关闭哈希,线性探测,探头长度1  ( Challenge closing hash linear probing probe length 1 ) 
挑战说,有一个带有错误的哈希算法,如果它到达数组的末尾,则给出了错误,并且没有找到保存元素的空间, 它直接丢弃它(即,它不会尝试将其放在0,1,2 ...上的位置,因为它是正确的) 在散列表中使用闭合散列,线性探测,探头1。 在此测试的可能性是什么,我们发现实现n有一个错误,如果n = 27并且k = 42? 示...

1  与素数步行有关吗?  ( Is open adressing with prime steps bijective ) 
谁可以帮助我这个主题:探测,具有素数。 我正在努力定义散列函数$ h(k,i)$ h(k,i)$以便在长度m表中的开放寻址,即,带插槽数$ 0,1,2, dots,m - 1 $。 我们知道函数$ h(k,i)= h_1(k)+ i cdot h_2(k) mod m $为每一个$ h_2(k)$和$ m产生每...

1  概率,所有索引在具有线性探测的哈希表中可被100所以的索引被占用  ( Probability that all indices divisible by 100 in a hash table with linear probin ) 
我试图在Sedgewick和Wayne的算法上解决这个问题: 假设大小10 ^ 6的线性探测表是半满,占用位置随机选择。估计通过100可分离的索引的所有位置被占用的概率被占用。 所以我们在哈希表上有500.000插入,需要检查占用的位置0,100,200,...,99900的概率。到目前为止,我考虑一个接一个地计...

1  系列的渐近生长  ( Asymptotic growth of a series ) 
我们如何证明: $$ sum_ {k = 1} ^ {c log n-1} :k cdot left( frac {1} {2} 右)^ { frac {k} {3}} 在o o 左(1 右) quad mbox {?} $$ ...

72  (当时)是哈希表查找o(1)?  ( When is hash table lookup o1 ) 
通常表示,哈希表查找在恒定的时间内运行:计算散列值,这为您提供了数组查找的索引。然而,这忽略了碰撞;在最坏的情况下,每个项目都发生在相同的桶中降落,查找时间变为线性($ theta(n)$)。 是否有可能使哈希表查找真正$ o(1)$的数据?是,只有平均,或者可以哈希表有$ o(1)$最坏情况查找? 注意:我来自...

1  有没有办法散列一个图灵机?  ( Is there a way to hash a turing machine ) 
如果我们有一个具有各种 $ delta(q_i,a_i)=(q_j,a_j,方向)$ 的方向可以是l或r(表示头部的运动),我们可以独特地编码一些自然数(后来可以解码,让我们回到Deltas)吗?如果所有自然数地图一对一地图到所有图定机器都无关紧要。 ...

0  转换为基础-R号码  ( Conversion to base r numbers ) 
我正在阅读robert sedgewick的算法4th版本,并且难以在一个特定的问题上陷入困境。本书的第460页,作者正在描述散列字符串的技术并使用模块化散列的素数。从第四行开始: If R is greater than any character value, this computation would ...

1  在哈希表中获取任意条目的缩小时间复杂度  ( Lower bound time complexity for obtaining an arbitrary entry in a hashtable ) 
我刚刚回答这个问题上的stackoverflow ,它要求提供一个有效的算法,使得给出一个非空的哈希特, 该算法应返回哈希表中任意非空条目的指针。 我的答案非常随意,如果我的证据是正确的,我并不自信。 我正在重新描述以下问题陈述: 我们被允许扩展 998876655443313 / 99887766554331...

0  所有值哈希如何与给定公式相同的值  ( How all values hash to the same value with a given formula ) 
在看散列时,并给出以下问题: Given ASCII values: a = 97, b = 98, c = 99, d = 100, e = 101 Given keys: {e, ae, be, ce, de, abe, ace, ade, bae, cae, dae, bce, bde, cbe, dbe...

35  哈希表与二元树  ( Hash tables versus binary trees ) 
在实施字典时('我想通过客户IDS查找客户数据),所使用的典型数据结构是哈希表和二进制搜索树。我知道例如,C ++ STL库使用(平衡)二进制搜索树实现词典(它们调用它们映射),并且.NET Framework在引擎盖下使用哈希表。 这些数据结构的优缺点是什么?是否有一些在某些情况下合理的其他选项? 注意,我对键...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有