In this talk I will discuss the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. For instance, given a weighted bipartite graph, can we compute a probability distribution over the set of perfect matchings in the graph whose marginals are the edge weights which maximizes the entropy?
While there has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms, a rigorous and systematic study of how to compute such distributions has been lacking. In this talk, I will discuss the challenges in the computability of max-entropy distributions and show that the problem, in a fairly general setting, is equivalent to a counting problem on the underlying set. As one consequence, for several combinatorial settings, there is an efficient algorithm to compute max-entropy distributions.
This is joint work with Nisheeth Vishnoi.