Communication and Distributional Complexity of Joint Probability Mass Functions

Abstract — The problem of truly-lossless (Pe = 0) distributed source coding [1] requires knowledge of the joint statistics of the sources. In particular the locations of the zeroes of the probability mass func-tions (pmfs) are crucial for encoding at rates below (H(X),H(Y)) [2]. We consider the distributed com-putation of the empirical joint pmf Pn of a sequence of random variable pairs observed at physically sep-arated nodes of a network. We consider both worst-case and average measures of information exchange and treat both exact calculation of Pn and a notion of approximation. We find that in all cases the com-munication cost grows linearly with the size of the in-put. Further, we consider the problem of determining whether the empirical pmf has a zero in a particular location and show that in most cases considered this also requires a communication cost that is linear in the input size. I