Constrained Maximum Entropy Contiguous Aggregations

Given a probability distribution p = (p1,..., pn) and an integer 1 ≤ m ≤ n, a contiguous aggregation of p is a probability distribution q = (q1,..., qm) such that each qi is a sum of consecutive elements of p. Given p and a positive number R, we consider the problem of computing a maximum entropy contiguous aggregation q of p, under the constraint that its Shannon entropy H(q) is at most R. We devise a dynamic programming algorithm that solves the problem exactly, and two time-efficient greedy algorithms that provide close-to-optimal solutions. We discuss a few scenarios where our problem arises.