Maximum Entropy Distributions with Applications to Graph Simulation

Paul Glasserman () and Enrique Lelo de Larrea ()
Additional contact information
Paul Glasserman: Graduate School of Business, Columbia University, New York, New York 10027
Enrique Lelo de Larrea: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Operations Research, 2023, vol. 71, issue 5, 1908-1924

Abstract: We study the problem of sampling uniformly from discrete or continuous product sets subject to linear constraints. This family of problems includes sampling weighted bipartite, directed, and undirected graphs with given degree sequences. We analyze two candidate distributions for sampling from the target set. The first one maximizes entropy subject to satisfying the constraints in expectation. The second one is the distribution from an exponential family that maximizes the minimum probability over the target set. Our main result gives a condition under which the maximum entropy and the max-min distributions coincide. For the discrete case, we also develop a sequential procedure that updates the maximum entropy distribution after some components have been sampled. This procedure sacrifices the uniformity of the samples in exchange for always sampling a valid point in the target set. To address the loss of uniformity, we use importance sampling weights. The quality of these weights is affected by the order in which the components are simulated. We propose an adaptive rule for this order that reduces the skewness of the weights in numerical examples.

Keywords: Simulation; maximum entropy; graph simulation; max-min probabilities; exponential families (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2323 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1908-1924

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().