On the relationship between Epsilon-based random variables and Epsilon-dependent random variables

The notions of "k-wise Epsilon-dependent" and "k-wise Epsilon-biased" are somewhat weaker in randomness than those of independent random variables. Random variables with these properties could be substitutes for independent random variables of randomized algorithms. An analysis,...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1994-07, Vol.51 (1), p.17
Main Authors: Jimbo, Shuji, Maruoka, Akira
Format: Article
Language:English
Subjects:
Algorithms
Information processing
Mathematical models
Random variables
Studies
Theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The notions of "k-wise Epsilon-dependent" and "k-wise Epsilon-biased" are somewhat weaker in randomness than those of independent random variables. Random variables with these properties could be substitutes for independent random variables of randomized algorithms. An analysis, after giving relevant definitions for these notions, presents the relationship between these notions. The analysis shows that, for any integer k and n, with one less than or equal to k and k less than or equal to n, if a system of n random variables in k-wise Epsilon-biased, then it is k-wise 4 times (one minus 2 to the negative k power) Epsilon-dependent in maximum norm and k-wise 2 times (one minus 2 to the negative k power) Epsilon-dependent in L-subscript one norm with respect to the uniform distribution. It is previously been shown that k-wise Epsilon-biased random variables are substituted for k-wise delta-dependent random variables in many randomized algorithms, so the results are expected to reduce the running time of resultant algorithms due to derandomization.
ISSN:0020-0190
1872-6119