A note on the influence of an \(\epsilon\)-biased random source. (English) Zbl 0938.68047

Ben-Dor, Amir; Karlin, Anna; Linial, Nathan; Rabinovich, Yuri

J. Comput. Syst. Sci. 58, No. 1, 174-176 (1999).

Summary: An \(\varepsilon\)-biased random source is a sequence \(X= (X_1,X_2,\dots, X_n)\) of \(0\), \(1\)-valued random variables such that the conditional probability

•  Encyclopedia of Mathematics
•  Wikipedia
•  Wolfram MathWorld

\(\text{Pr}[X_i= 1\mid X_1,X_2,\dots, X_{i-1}]\) is always between \({1\over 2}-\varepsilon\) and \({1\over 2}+\varepsilon\). Given a family \(S\subseteq \{0,1\}^n\) of binary strings of length \(n\), its \(\varepsilon\)-enhanced probability \(\text{Pr}_\varepsilon(S)\) is defined as the maximum \(\text{Pr}_X(S)\) over all \(\varepsilon\)-biased random sources \(X\). In this paper, we establish a tight lower bound on \(\text{Pr}_\varepsilon(S)\) as a function of \(|S|\), \(n\) and \(\varepsilon\).

© Academic Press

MSC:

68P25

Data encryption (aspects in computer science)

Keywords:

\(\varepsilon\)-biased random source

References:

[1]	Alon, N.; Rabin, M. O., Biased coins and randomized algorithms, Adv. in Comput. Res., 5, 499-507, 1987
[2]	Ben-Or, M.; Linial, N.; Saks, M., Collective coin flipping and other models of imperfect randomness, Colloq. Math. Soc. Janos Bolyai. Colloq. Math. Soc. Janos Bolyai, Combinatorics, 52, 1987 · Zbl 0675.90107
[3]	Bollobas, B., Combinatorics, 1986, Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0603.01017
[4]	J. Hastad, A simpler proof that it is not possible to extract a good random bit from one slightly random source
[5]	Pinkas, B., Cryptography and Models of Weak Randomness, 1991, Technion
[6]	M. Santha, U. V. Vazirani, Generating quasi-random sequences from semi-random sources, Proc. 25th Annual Symposium of Foundation of Computer Science, 1984, 434, 440
[7]	Santha, M.; Vazirani, U. V., Generating quasi-random sequences from semi-random sources, J. Comput. System. Sci., 33, 75-87, 1986 · Zbl 0612.94004