Premium
Coin flipping from a cosmic source: On error correction of truly random bits
Author(s) -
Mossel Elchanan,
O'Donnell Ryan
Publication year - 2005
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.20062
Subject(s) - coin flipping , symmetrization , probability of error , discrete mathematics , mathematics , randomness , function (biology) , random variable , combinatorics , algorithm , computer science , statistics , evolutionary biology , biology
Abstract We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1} n , and k parties, who have noisy version of the source bits y i ∈ {0, 1} n , when for all i and j , it holds that P [ y j i= x j ] = 1 − ϵ, independently for all i and j . That is, each party sees each bit correctly with probability 1 − ϵ, and incorrectly (flipped) with probability ϵ, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f i : {0, 1} n → {0, 1} such that P [ f 1 ( y 1 ) = … = f k ( y k )] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f i may be thought of as an error correcting procedure for the source x . When k = 2,3, no error correction is possible, as the optimal protocol is given by f i ( y i ) = y 1 i . On the other hand, for large values of k , better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n , and ϵ. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005