2019/01/19 by Cicalese, Ferdinando, Gargano, Luisa, Vaccaro, Ugo · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1901.07530
Given two discrete random variables X and Y, with probability distributions \bf p=(p1, … , pn) and \bf q=(q1, … , qm), respectively, denote by \cal C(\bf p, \bf q) the set of all couplings of \bf p and \bf q, that is, the set of all bivariate probability distributions that have \bf p and \bf q as marginals. In this paper, we study the problem of finding a joint probability distribution in \cal C(\bf p, \bf q) of minimum entropy (equivalently, a coupling that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in \cal C(\bf p, \bf q) with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum--entropy joint distribution of arbitrary k≥ 2 discrete random variables X1, … , Xk, consistent with the known k marginal distributions of the individual random variables X1, … , Xk. In this case, our algorithm has an additive gap of at most log k from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.