How Many Queries Will Resolve Common Randomness?
This work addresses a fundamental problem in information theory for scenarios involving secure communication and distributed systems, with incremental contributions linking query complexity to existing concepts like secret key capacity.
The paper tackles the problem of determining how many direct queries are needed to resolve common randomness generated by terminals observing correlated signals, given only their communication. It provides a general upper bound for arbitrary signal alphabets and shows that for i.i.d. correlated signals, the number of queries can be exponential in signal length, with the bound being tight and leading to a single-letter formula that matches secret key capacity.
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 Renyi 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.