Maximum Entropy Interval Aggregations
Ferdinando Cicalese, Ugo Vaccaro · 2018
Given a probability distribution p=(p1, ⋯, pn) and an integer 1 ≤ m1, ⋯, qm) is a contiguous m-aggregation of p if there exist indices such that for each j=1, ⋯, m it holds that qj= Σk=i(j-1)+1ijpk. In this paper, we consider the problem of efficiently finding the contiguous m-aggregation of maximum entropy. We design a dynamic programming algorithm that solves the problem exactly, and two more time-efficient greedy algorithms that provide slightly sub-optimal solutions. We also discuss a few scenarios where our problem matters.