On restricted min‐wise independence of permutations |
| |
Authors: | Jiří Matoušek Miloš Stojaković |
| |
Institution: | 1. Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
Institut für Theoretische Informatik, ETH Zentrum, Zürich, Switzerland;2. Institut für Theoretische Informatik, ETH Zentrum, Zürich, Switzerland |
| |
Abstract: | A family of permutations ℱ ⊆ Sn with a probability distribution on it is called k-restricted min-wise independent if we have Prmin π(X) = π(x)] = 1/|X| for every subset X ⊆ n] with |X| ≤ k, every x ∈ X, and π ∈ ℱ chosen at random. We present a simple proof of a result of Norin: every such family has size at least Some features of our method might be of independent interest. The best available upper bound for the size of such family is 1 + ∑ (j − 1)(). We show that this bound is tight if the goal is to imitate not the uniform distribution on Sn, but a distribution given by assigning suitable priorities to the elements of n] (the stationary distribution of the Tsetlin library, or self-organizing lists). This is analogous to a result of Karloff and Mansour for k-wise independent random variables. We also investigate the cases where the min-wise independence condition is required only for sets X of size exactly k (where we have only an Ω(log log n + k) lower bound), or for sets of size k and k − 1 (where we already obtain a lower bound of n − k + 2). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003 |
| |
Keywords: | |
|
|