Chain Independence and Common Information
We present a new proof of a celebrated result of Gacs and Korner that the common information is far less than the mutual information. Consider two sequences alpha(1),...alpha(n) and beta(1),...,beta(n) of random variables, where pairs (alpha(1),beta(1)),..., (alpha(n),beta(n)) are independent and identically distributed. Gacs and Korner proved that it is not possible to extract "common information" from these two sequences unless the joint distribution matrix of random variables (alpha(i), beta(i)) is a block matrix. In 2000, Romashchenko introduced a notion of chain independent random variables and gave a simple proof of the result of Gacs and Korner for chain independent random variables. Furthermore, Romashchenko showed that Boolean random variables and are chain independent unless alpha = beta a.s. or alpha = 1 - beta a.s. In this paper, we generalize this result to arbitrary (finite) distributions of alpha and beta and thus give a simple proof of the result of Gacs and Korner.
common information chain independent random variables rate region