Exact common information
Authors:
- 1 June 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 161-165
Abstract
This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables (X, Y). We introduce the quantity G(X; Y) = min X→W→Y H(W) as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS (X, Y). We give a multiletter characterization for it as the limit G̅(X; Y) = lim n→∞ (1/n)G(X n ; Y n ). While in general G̅(X; Y) is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Network Information Theory2011
- Coordination CapacityIEEE Transactions on Information Theory, 2010
- Common randomness in information theory and cryptography. I. Secret sharingIEEE Transactions on Information Theory, 1993
- Multiple access channels with arbitrarily correlated sourcesIEEE Transactions on Information Theory, 1980
- The common information of two dependent random variablesIEEE Transactions on Information Theory, 1975
- Source Coding for a Simple NetworkBell System Technical Journal, 1974