Min-Wise Independent Linear Permutations

Abstract

A set of permutations ${\cal F} \subseteq S_n$ is min-wise independent if for any set $X \subseteq [n]$ and any $x \in X$, when $\pi$ is chosen at random in ${\cal F}$ we have ${\bf P} \left(\min\{\pi(X)\} = \pi(x)\right) = {{1}\over {|X|}}$. This notion was introduced by Broder, Charikar, Frieze and Mitzenmacher and is motivated by an algorithm for filtering near-duplicate web documents. Linear permutations are an important class of permutations. Let $p$ be a (large) prime and let ${\cal F}_p=\{p_{a,b}:\;1\leq a\leq p-1,\,0\leq b\leq p-1\}$ where for $x\in [p]=\{0,1,\ldots,p-1\}$, $p_{a,b}(x)=ax+b\pmod p$. For $X\subseteq [p]$ we let $F(X)=\max_{x\in X}\left\{{\bf P}_{a,b}(\min\{p(X)\}=p(x))\right\}$ where ${\bf P}_{a,b}$ is over $p$ chosen uniformly at random from ${\cal F}_p$. We show that as $k,p \to\infty$, ${\bf E}_X[F(X)]={{1}\over {k}}+O\left({(\log k)^3}\over {k^{3/2}}\right)$ confirming that a simply chosen random linear permutation will suffice for an average set from the point of view of approximate min-wise independence.