Maximum Entropy Interval Aggregations

05/14/2018

∙

by   Ferdinando Cicalese, et al.

∙

0

∙

share

Given a probability distribution p = (p_1, ..., p_n) and an integer 1≤ m < n, we say that q = (q_1, ..., q_m) is a contiguous m-aggregation of p if there exist indices 0=i_0 < i_1 < ... < i_m-1 < i_m = n such that for each j = 1, ..., m it holds that q_j = ∑_k=i_j-1+1^i_j p_k. 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.