On construction ofk-wise independent random variables |
| |
Authors: | Howard Karloff Yishay Mansour |
| |
Institution: | (1) Georgia Institute of Technology, College of Computing, 30332-0280 Atlanta, GA;(2) Computer Science Dept., Tel-Aviv University, Tel-Aviv, Israel |
| |
Abstract: | A 0–1probability space is a probability space ( , 2 ,P), where the sample space ![OHgr](/content/vv12581v2j011755/xxlarge937.gif) -{0, 1}
n
for somen. A probability space isk-wise independent if, whenY
i
is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY
i
's is (mutually) independent, and it is said to be a probability spacefor p
1,p
2, ...,p
n
ifPY
i
=1]=p
i
.We study constructions ofk-wise independent 0–1 probability spaces in which thep
i
's are arbitrary. It was known that for anyp
1,p
2, ...,p
n
, ak-wise independent probability space of size
always exists. We prove that for somep
1,p
2, ...,p
n
0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp
i
=k/n has size (n
k
). For a very large degree of independence —k= n], for >1/2- and allp
i
=1/2, we prove a lower bound on the size of
. We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology. |
| |
Keywords: | 68 Q 99 68 R 05 60 C 05 |
本文献已被 SpringerLink 等数据库收录! |
|