Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 289-304 |
Number of pages | 16 |
Journal | Random Structures & Algorithms |
Volume | 3 |
Issue number | 3 |
DOIs | |
State | Published - 1992 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Keywords
- Probabilistic computation
- removing randomness
- shiftregister sequences
- small probability spaces