On extracting common random bits from correlated sources

Details On extracting common random bits from correlated sources On extracting common random bits from correlated sources

2010-07-14

arxiv.org/abs/1007.2315v2

Computer Science

Information Theory

Scientific paper

Suppose Alice and Bob receive strings of unbiased independent but noisy bits from some random source. They wish to use their respective strings to extract a common sequence of random bits with high probability but without communicating. How many such bits can they extract? The trivial strategy of outputting the first $k$ bits yields an agreement probability of $(1 - \eps)^k < 2^{-1.44k\eps}$, where $\eps$ is the amount of noise. We show that no strategy can achieve agreement probability better than $2^{-k\eps/(1 - \eps)}$. On the other hand, we show that when $k \geq 10 + 2 (1 - \eps) / \eps$, there exists a strategy which achieves an agreement probability of $0.1 (k\eps)^{-1/2} \cdot 2^{-k\eps/(1 - \eps)}$.

Affiliated with

Also associated with

No associations

Rating

On extracting common random bits from correlated sources does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On extracting common random bits from correlated sources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On extracting common random bits from correlated sources will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120773