On Sequences of Pairs of Dependent Random Variables

Abstract

The generalized random variables $( {x,y} )$ have a given joint distribution. Pairs $( {x_i ,y_i } )$ are drawn independently. The observer of $( {x_1 , \cdots ,x_n } )$ and the observer of $( {y_1 , \cdots ,y_n } )$ each make a binary decision, of entropy bounded away from zero, with probability of disagreement $\varepsilon _n $. It is shown that $\varepsilon _n $ can be made to approach zero as $n \to \infty $ if and only if the maximum correlation of x and y is unity. Under a compactness condition, satisfied in particular when x and/or y takes only finitely many values, this occurs if and only if the joint distribution decomposes, that is when $\varepsilon _1 $ can be made to vanish by nontrivial decisions, as had been conjectured. Results are also obtained for nonidentically distributed pairs, for randomized decisions, for multivalued decisions and for decisions based on the infinite sequences. The question arose in the transmission of data from two dependent sources to two receivers. The results of Gács and Körner [1] for that problem are sharpened and clarified.