# 证明这家族哈希函数是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

### 问题

$$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$$

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

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 )

1  关于佐色斯散系与碰撞机会的理论问题  ( Theoretical question about zobrist hashing and chances of collision with slight )

8  如何计算线性时间最坏情况？  ( How to count in linear time worst case )

1  解释操作系统中的哈希页面表  ( Explain hashed page tables in operating system )

5  哈希函数究竟是什么？  ( What exactly is a hash function )

23  填充糕点的路由表如何工作？  ( How does populating pastrys routing table work )

18  对于哈希表操作O（1）是什么样的数据？  ( For what kind of data are hash table operations o1 )

-1  完美（或几乎完美）哈希函数，用于n位整数，恰好k位设置  ( Perfect or almost perfect hash function for n bit integers with exactly k bits )

3  是Von Neumann架构中的所有数据结构，基于阵列，也是阵列的？  ( Are all data structures in the von neumann architecture based on the array or a )

83  为什么最好在散列函数中使用素数作为mod？  ( Why is it best to use a prime number as a mod in a hashing function )

0  使用MOD方法选择已知的单独链接数量键的数组大小  ( Choosing array size for known number of keys in seperate chaining using mod meth )

0  确定哈希函数的适当数量的桶  ( Determining an appropriate number of buckets for a hash function )

1  成功插入哈希表之前的平均碰撞次数  ( Average number of collisions before successful insertion into hash table )

0  转换为基础-R号码  ( Conversion to base r numbers )

1  在哈希表中获取任意条目的缩小时间复杂度  ( Lower bound time complexity for obtaining an arbitrary entry in a hashtable )

0  所有值哈希如何与给定公式相同的值  ( How all values hash to the same value with a given formula )

35  哈希表与二元树  ( Hash tables versus binary trees )