On Extracting Common Random Bits From Correlated Sources
On Extracting Common Random Bits From Correlated Sources
复制标题
关于从相关源中提取公共随机位
DOI：
10.1109/tit.2011.2134067
复制
发表时间：
2010
影响因子：
2.5
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
Andrej Bogdanov;Elchanan Mossel
假设爱丽丝和鲍勃从某个随机源接收到无偏独立但有噪声的比特串。他们希望使用各自的字符串以高概率提取公共随机位序列，但无需进行通信。他们可以提取多少个这样的位？输出前 k 位的简单策略产生的一致概率为 (1-ε)<sup>k</sup> <; 2<sup>-1.44kε</sup>，其中ε是噪声量。我们证明没有任何策略能够比 2<sup>-kε/(1-ε)</sup> 更好地实现一致概率。另一方面，我们表明，当 k ≥ 10 + 2(1 - ε)/ε 时，存在一种策略，其一致性概率为 0.003(kε)<sup>-1/2</sup> · 2<sup>-kε/(1-ε)</sup>。
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-ε)<sup>k</sup> <; 2<sup>-1.44kε</sup>, where ε is the amount of noise. We show that no strategy can achieve agreement probability better than 2<sup>-kε/(1-ε)</sup>. On the other hand, we show that when k ≥ 10 + 2(1 - ε)/ε, there exists a strategy which achieves an agreement probability of 0.003(kε)<sup>-1/2</sup> · 2<sup>-kε/(1-ε)</sup>.