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-\varepsilon)^{k}<2^{-1.44k\varepsilon}$, where$\varepsilon$is the amount of noise. We show that no strategy can achieve agreement probability better than$2^{-k\varepsilon/(1-\varepsilon)}$.
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 firstkbits yields an agreement probability of(1−ε)k<2−1.44kε, whereεis the amount of noise. We show that no strategy can achieve agreement probability better than2−kε/(1−ε).
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)}$.
Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n but so that X and Y are correlated . For each symbol i, we have that Yi=Xi with probability $1-\eps$ and otherwise Yi is chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of $(1 - \eps + \eps/s)^k$. In a recent work by Bogdanov and Mossel it was shown that in the binary case where s=2 and $k = k(\eps)$ is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability $(k\eps)^{-1/2} \cdot 2^{-k\eps/(2(1 - \eps/2))}$ using a random construction based on Hamming balls, and this is optimal up to lower order terms. In the current paper we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular we show no strategy can achieve agreement probability better than $(1-\eps)^k (1+δ(s))^k$ where δ(s)→0 as s→∞. We also show that Hamming ball based constructions have {\em much lower} agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.
Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n, but so that X and Y are correlated. For each symbol i, we have that Yi=Xiwith probability 1-ε and otherwise Yiis chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k, but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of (1-ε+ε/s)k. In a recent work by Bogdanov and Mossel, it was shown that in the binary case where s=2 and k=k(ε) is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability (kε)-1/2·2-kε/(2(1-ε/2))using a random construction based on Hamming balls, and this is optimal up to lower order terms. In this paper, we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular, we show no strategy can achieve agreement probability better than (1-ε)k(1+δ(s))kwhere δ(s)→ 0 as s→∞. We also show that Hamming ball-based constructions have much lower agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.
Abstract: Suppose that both Alice and Bob receive independent random bits without any bias, which are influenced by an independent noise. From the received random bits, Alice and Bob are willing to extract common randomness, without any communication. The extracted common randomness can be used for authentication or secrets. Recently, Bogdanov and Mossel derived an upper bound of the agreement probability, based on the min-entropy of outputs. In this paper, we derive a generalized upper bound of the probability of extracting common random bits from correlated sources, using the Rènyi entropy of order 1/(1−ε), where ε is the error probability of the binary symmetric noise. It is shown that the generalized upper bound is always less than or equal to the previous bound.
Suppose Alice holds a uniformly random string X ∈ {0, 1}N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability e ∈ [0, 1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2-γk (γk ≥ 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely [EQUATION], where C:= 4e(1 - e). In particular, the optimal communication to achieve Ω(1) agreement probability approaches 4e(1 - e)k.
We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1 - e and is otherwise erased (that is, replaced by a '?'). In this case, the communication required becomes [EQUATION]. In particular, the optimal communication to achieve Ω(1) agreement probability approaches ek, and with no communication the optimal agreement probability approaches [EQUATION].
Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular most informative Boolean function conjecture of Courtade and Kumar.
Suppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar.