The common information of two dependent random variables

The problem of finding a meaningful measure of the "common information" or "common randomness' of two discrete dependent random variables X, Y is studied. The quantity C (X; Y) is defined as the minimum possible value of I (X, Y; W) where the minimum is taken over all distributions defining an auxiliary random variable W W, a finite set, such that X, Y are conditionally independent given W. The main result of the paper is contained in two theorems which show that C (X; Y) is i) the minimum R₀ such that a sequence of independent copies of (X, Y) can be efficiently encoded into three binary streams W₀, W₁, W₂ with rates R₀, R₁, R₂, respectively, Rᵢ = H (X, Y) and X recovered from (W₀, W₁), and Y recovered from (W₀, W₂), i. e. , W₀ is the common stream; ii) the minimum binary rate R of the common input to independent processors that generate an approximation to X, Y.