Sharp high-entropy lower bounds for the entropy of a sum were known for identically distributed summands in torsion-free abelian groups and in prime cyclic groups. For arbitrary independent summands, Gavalakis, Goh and Kontoyiannis obtained an additive constant of $1/8$ and conjectured that the sharp constant is $1/2$. We prove that independent discrete random variables $X,Y$ with finite Shannon entropies satisfy $H(X+Y)\ge (H(X)+H(Y))/2+1/2-o(1)$ in every torsion-free abelian group as $\max{H(X),H(Y)}\to\infty$. The same conclusion holds in the prime cyclic group $\mathbb F_p$ when both $\max{H(X),H(Y)}$ and $\log_2 p-\max{H(X),H(Y)}$ tend to infinity. We give explicit error bounds in both settings. The proof extracts a component with paired point probabilities while controlling the entropy of the remainder independently of its support. Discrete rearrangement and uniform perturbation then transfer the continuous entropy power inequality to this component. In prime cyclic groups, an additional estimate controls the entropy lost under modular reduction. Binomial distributions show that the constant $1/2$ is optimal.
Suppose $X,Y$ are independent random variables with values in a compact abelian group $(G,+)$. We examine the following two entropy power-type inequalities: $h(X+Y)\geq \frac{1}{2}h(X)+\frac{1}{2}h(Y)$ and $h(X+Y)\geq \max\{h(X),h(Y)\}$, where the entropy $h(Z)$ of a $G$-valued random variable $Z$ is defined in terms o...
Lampros Gavalakis, I. Kontoyiannis, Sharang M. Sriramu et al.· 1 citation
Let $X_1,X_2,\ldots$ be i.i.d. finitely supported random variables in a torsion-free abelian group, and write $S_k=X_1+\cdots+X_k$, and $H(S_k)$ is the Shannon entropy $S_k$, for all $k \ge 1$. We prove that, for every fixed $n\geq1$, \[ H(S_{n+1})-H(S_n) \geq \frac12\log\frac{n+1}{n} -o_{H(X_1)\to\infty}(1), \] unifor...
We determine the sharp exponential growth rate of the minimum number of abelian subgroups required to cover a group with bounded pairwise noncommutativity. Let $\omega(G)$ denote the largest size of a pairwise noncommuting subset of a group $G$, let $a(G)$ be the least size of an abelian cover, and define $h(n)=\sup\{a...
We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $\Delta_i=\mu_*-\mu_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}\Delta_i^{-2}$. Let $p_r$ be the...
P. M. Aronow, Nathan Kallus, Patrick Lopatto· 1 citation
We use tools and techniques from $p$-adic analysis and algebraic number theory to study the algebraicity of the hard square entropy constant and its high dimensional analogues. Specifically, we study arithmetic properties of $a_d(n)$, the number of independent sets in the $d$-dimensional discrete torus, and the associa...
Let $X_H$ denote the number of copies of a fixed graph $H$ in $G_{n, p}$. Gilmer and Kopparty conjectured that $X_H$ satisfies a local central limit theorem (LCLT) provided that $H$ is connected, $p \gg n^{-1/m(H)}$, and $n^2 (1-p) \gg 1$, where $m(H)$ is the maximum density. Following the work of Berkowitz, Sah and Sa...
Asaf Cohen Antonir, Ilay Hoshen, M. Zhukovskii· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
