

























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\to W \to 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 $\bar{G}(X;Y)=\lim_{n\to \infty}(1/n)G(X^n;Y^n)$. While in general $\bar{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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。