Constrained Maximum Entropy Contiguous Aggregations

Abstract

Given a probability distribution $p=(p_1,\dots ,p_n)$ and an integer $1\le m\le n$, a contiguous aggregation of $p$ is a probability distribution $q=(q_1,\dots ,q_m)$ such that each $q_i$ 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.

Accepted to IEEE ISIT 2026

References in corpus (2)

• Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
• Old and New Results on Alphabetic Codes