How Many Queries Will Resolve Common Randomness?
How Many Queries Will Resolve Common Randomness?
复制标题
有多少查询可以解决常见的随机性？
DOI：
10.1109/isit.2013.6620809
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
P. Narayan
中科院分区：
文献类型：
--
作者：
Himanshu Tyagi;P. Narayan
一组M终端观察相应的信号，以交流为特定子集的共同随机性，仅知道通信，有多少个通用随机性的直接查询可以解决一般的上限？通过使用适用于所有共同的随机性和相关的通信的查询策略，为此类查询的数量开发了任意信号字母。 M相关的随机变量的分布式重复，在这种情况下，查询数量可以指数，上述上限是紧密的，并导致最大的查询指数的单字母公式实际上，相应的多定位源模型是最佳查询指数的强大匡威，这也意味着秘密钥匙能力的新的强烈交谈。估计较大概率集的大小，以rényi熵的形式分别解释为一般来源的无损块编码结果。
A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Rényi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.