Premium
Simple Constructions of Almost k‐wise Independent Random Variables
Author(s) -
Alon Noga,
Goldreich Oded,
Håstad Johan,
Peralta René
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030308
Subject(s) - mathematics , simple (philosophy) , combinatorics , distribution (mathematics) , discrete mathematics , binary logarithm , upper and lower bounds , random variable , log log plot , point (geometry) , space (punctuation) , statistics , mathematical analysis , computer science , geometry , philosophy , epistemology , operating system
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o (1)) (log log n + k /2 + log k + log 1/ϵ), where ϵ is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ϵ < 1/( k log n )). An additional advantage of our constructions is their simplicity.