On the sample size of k-min-wise independent permutations and other k-wise distributions

摘要

A family F of permutations of {0,1,..., n - 1} is k-restricted mm-wise independent if for any set x {is contained in} {0,1,..., n - 1} with |X| ≤ k and any x ∈ X, Pr[π(x) = min{π(X)}] 1/|X| when a permutation π is randomly drawn from F. We show that if a permutation family F of an n-set is k-restricted mm-wise independent, |F| ≥ m(n - 1, k - 1). The lower bound for the size of F still holds when we allow an arbitrary probability distribution on F. It is well known that if random variables X{sub}1,X{sub}2,..., X{sub}n : Ω→{0, 1} are d-wise independent and Pr[X{sub}i = 1] = p{sub}i is neither 0 nor 1, then |Ω| ≥ m(n, d). We give the following generalization and derive the result above: if random variables X{sub}1, ..., X{sub}n : Ω→{0,1} have an identical d-wise distribution with some random variables Y{sub}1, ..., Y{sub}n and the n-tuple (Y{sub}1,..., Y{sub}n) visits all the 2{sup}n values with positive probabilities, then |Ω|≥m(n, d). The existence of such Y{sub}i's is immediate when one starts with fully-distributed truly random variables and considers random variables with an identical d-wise distribution.