Given a probability distribution $p = (p_1, \dots, p_n)$ and an integer $1\leq m \leq 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.

This work investigates binary hypothesis testing between $H_0\sim P_0$ and $H_1\sim P_1$ in the finite-sample regime under asymmetric error constraints. By employing the ``reverse" Rényi divergence, we derive novel non-asymptotic bounds on the Type II error probability which naturally establish a strong converse result. Furthermore, when the Type I error is constrained to decay exponentially with a rate $c$, we show that the Type II error converges to 1 exponentially fast if $c$ exceeds the Kullback-Leibler divergence $D(P_1\|P_0)$, and vanishes exponentially fast if $c$ is smaller. Finally, we present numerical examples demonstrating that the proposed converse bounds strictly improve upon existing finite-sample results in the literature.

Given a random variable X that takes values in a finite setX= {x1, . . . ,xn}, and a positive numberR, we consider the problem of finding a deterministic functionf:X→Ythat maximizes the entropyH(f(X)), while satisfying the constraintH(f(X)) ≤R. This problem occurs in several contexts, including lossy compression with logarithmic loss and the well-known Deterministic Information Bottleneck problem. We prove the NP-hardness of finding the optimal solution to the above maximization problem. On the positive side, we design approximation algorithms that achieve improved approximation factors compared to existing methods in the literature.

In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most$D$ones, where$D$is a given input parameter. We provide an$O\left(n^{2} D\right)$-time complexity algorithm for the construction of such codes, where$n$is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. Our algorithms allow us to construct both optimal average-length prefix binary codes and optimal average-length alphabetic binary codes. In the former case, our$O\left(n^{2} D\right)$-time algorithm substantially improves on the previously known$O\left(n^{2+D}\right)$-time complexity algorithm for the same problem. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword.

Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.