Common information revisited

Details Common information revisited Common information revisited

2011-04-16

arxiv.org/abs/1104.3207v2

Computer Science

Information Theory

11 pages, 2 figures; submitted to CCC '12

Scientific paper

One of the main notions of information theory is the notion of mutual information in two messages (two random variables in Shannon information theory or two binary strings in algorithmic information theory). The mutual information in $x$ and $y$ measures how much the transmission of $x$ can be simplified if both the sender and the recipient know $y$ in advance. G\'acs and K\"orner gave an example where mutual information cannot be presented as common information (a third message easily extractable from both $x$ and $y$). Then this question was studied in the framework of algorithmic information theory by An. Muchnik and A. Romashchenko who found many other examples of this type. K. Makarychev and Yu. Makarychev found a new proof of G\'acs--K\"orner results by means of conditionally independent random variables. The question about the difference between mutual and common information can be studied quantitatively: for a given $x$ and $y$ we look for three messages $a$, $b$, $c$ such that $a$ and $c$ are enough to reconstruct $x$, while $b$ and $c$ are enough to reconstruct $y$. In this paper: We state and prove (using hypercontractivity of product spaces) a quantitative version of G\'acs--K\"orner theorem; We study the tradeoff between $\abs{a}, \abs{b}, \abs{c}$ for a random pair $(x, y)$ such that Hamming distance between $x$ and $y$ is $\eps n$ (our bounds are almost tight); We construct "the worst possible" distribution on $(x, y)$ in terms of the tradeoff between $\abs{a}, \abs{b}, \abs{c}$.

Affiliated with

Also associated with

No associations

Rating

Common information revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Common information revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Common information revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-346837