CS Paper Radar

On Measures of Dissimilarity on the Majorization Simplex

Tarun Hariharan, Prasad Krishnan, Abhishek Deshpande

cs.IT ·submitted 2026-10-12 12:27 UTC · v1
theory

Abstract

The majorization simplex $\mathcal{P}_n$ is the set of probability vectors of length $n$ whose entries are arranged in non-increasing order. Under the majorization order, $\mathcal{P}_n$ is a lattice, and it is the natural space for comparing distributions when the labels of the outcomes are not relevant. In this work, we study measures of dissimilarity (and, similarity) on $\mathcal{P}_n$. Our first set of results concerns the Rényi-entropy based distance $d_α(p,q)=H_α(p)+H_α(q)-2H_α(p\vee q)$ proposed by Yadav and Shkel (2026), which generalizes a metric of Cicalese, Gargano and Vaccaro (2013). We show that $d_α$ is a metric on $\mathcal{P}_n$ for $α\in[1,\infty)$, while for $α\in[0,1)\cup\{\infty\}$, $d_α$ is not a metric in general. Our main result in this part identifies the necessary and sufficient conditions for equality in the triangle inequality of $d_α$ when $α>1$, for which we identify the equality conditions for the supermodularity of the Rényi entropy $H_α$. Our second set of results concerns the total variation distance and the Hellinger affinity (also called the Bhattacharyya coefficient) on $\mathcal{P}_n$. We obtain a number of bounds on these measures, along with some of their equality conditions. The resulting Hellinger affinity based upper bound on the total variation distance can be smaller than the bounds obtained from Pinsker's and the Bretagnolle--Huber inequalities.

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Rogers--Shephard Inequalities for Rényi Entropy

cs.IT math.PRmath.MG ·2026-10-11 ·Bang-Xian Han, Guoqing Zhan, Chiyu Zhou, Zhuo-Nan Zhu
theory similarity 0.61
Abstract · 29 pages; comments are welcome!

We establish sharp weighted Rogers--Shephard inequalities for Rényi differential entropy. For independent copies $X,X'$ of a log-concave random vector in $\R^n$, we prove $h_p(aX-bX')\le h_p(X)+n\log(a+b)$ for all $a,b>0$ and $1\le p\le\infty$, where orders $1$ and $\infty$ correspond to Shannon entropy and min-entropy, respectively. The Shannon case settles the entropic Rogers--Shephard conjecture of Madiman and Kontoyiannis and its higher-dimensional formulation. For $1\le p<\infty$, equality holds precisely for invertible affine images of random vectors with independent exponential coordinates. At $p=\infty$, the larger equality class is characterized by possibly extended-valued convex potentials that are positively homogeneous of degree one. For every $0<p<1$, uniform laws on sufficiently high-dimensional simplices violate the unweighted bound. Thus $p=1$ is the critical order for this bound to hold in every dimension. The proof combines weighted convex intersections with an exponential lift to a log-affine probability density. At the Shannon endpoint, this lift yields an exact deficit decomposition with a conditional mutual information term for an additive channel with asymmetric Laplace noise.

0.43

Relative Entropy under Ordered Chi-Squared Constraints: Exact Bounds and Extremizers

cs.IT ·2026-11-18 ·Igal Sason
theory similarity 0.60
Abstract

We derive a sharp upper bound on the relative entropy $D(P\|Q)$ in terms of the two ordered chi-squared divergences $χ^2(P\|Q)$ and $χ^2(Q\|P)$. For any $A,B>0$, the constraints $χ^2(P\|Q)\leq A$ and $χ^2(Q\|P)\leq B$ yield upper bounds on $D(P\|Q)$ and $D(Q\|P)$. Two pairs of Bernoulli distributions each attain both bounds simultaneously. As a consequence, for sequences of probability mass functions $\{P_n\}$ and $\{Q_n\}$ on a common finite or countably infinite alphabet, both $D(P_n\|Q_n)$ and $D(Q_n\|P_n)$ tend to zero whenever one of the two ordered chi-squared divergences tends to zero and the other remains uniformly bounded. Without this boundedness assumption, $D(P_n\|Q_n)$ can fail to converge to zero even when $χ^2(Q_n\|P_n)\to 0$. Finally, in contrast to the attainable upper bounds, on any finite or countably infinite alphabet containing at least three elements, the infimum of $D(P\|Q)$ under the exact constraints $χ^2(P\|Q)=A$ and $χ^2(Q\|P)=B$ is zero and is not attained.

0.35

Separating Measures by Hyperplanes

cs.CG math.MG ·2026-11-06 ·José Correa, Svenja M. Griesbach, Elfarouk Harb, Felix Hommelsheim, Reda Jlibene +2 more
theory similarity 0.60
Abstract · 58 pages, 5 figures

Given red and blue points in $\mathbb{R}^d$, connect every red point to every blue point and weigh each segment by its length under a fixed norm. What fraction of the total weight can always be captured by a single affine hyperplane separating the segments' endpoints? We study this question for finite point configurations in affine general position and, more generally, for pairs of probability measures. For dimension one, we show that choosing the best of three thresholds determined by the means of the two distributions captures at least one third of the total red-blue distance. We also give a matching upper bound. Embedding the line construction to higher dimensions shows that the guarantee of $1/3$ cannot be improved for arbitrary measures. Thus, we pivot to the family of measures whose atoms are in affine general position and whose non-atomic part places zero mass on all hyperplanes. Crucially, we establish that the worst-case guarantee is identical for finite configurations in affine general position and several natural classes of probability measures, thereby unifying the discrete and continuous formulations of the problem. For this family of measures and for higher dimensions, we extend our guarantee of $1/3$ for all norms. Our proofs combine the ham-sandwich theorem with a novel coupling argument and, in the planar case, an integral representation of norms. We also show that the optimal guarantee improves as the dimension grows, giving a lower bound of $1/2-\operatorname{O}\left(1/\sqrt{d}\right)$ as well as an asymptotically matching upper bound of $1/2$ for every $d$. For the Euclidean distance, we refine the lower bounds to $8/(8+5π)$ and $1/2-\operatorname{O}\left(1/d\right)$ and, for $d=2$, the upper bound to $5/11$. We also derive dimension-dependent guarantees for finite point configurations, including perfect separation of $n$ points of each color when $d\geq2n-1$.

0.27

Contraction of Rényi Divergences for Discrete Channels

cs.IT math.PR ·2026-09-28 ·Adrien Vandenbroucque, Amedeo Roberto Esposito, Michael Gastpar
highly cited similarity 0.60
Abstract

We investigate Strong Data-Processing Inequality (SDPI) constants for Rényi Divergences on finite spaces. We study their dependence on the Rényi order $α$, proving that they are non-decreasing and that their scaling by $(α-1)$ is convex for $α\geq1$. We also identify several support restrictions on the probability measures involved in determining these constants. In particular, in the distribution-independent setting, measures supported on a common set of at most two points suffice to evaluate the Rényi-SDPI constant. For $α\in[0,1]$, we further prove equality with the $χ^2$-SDPI constant, while at order infinity we obtain a closed-form expression. In order to link contraction over product spaces to contraction along individual coordinates, we provide tensorisation bounds for arbitrary product channels analogous to those known for $\varphi$-Divergences. At finite orders, the Rényi-SDPI constants are bounded above and below through comparisons with the $χ^2$-Divergence and Hellinger Divergences, with sharpness established in multiple cases. At order infinity, we instead relate these constants to the contraction of Total Variation Distance. Finally, our findings are applied to local differential privacy (LDP) and the analysis of Markov chains. This yields sharp contraction guarantees for pure-LDP mechanisms, and connects Rényi-LDP to Rényi-SDPI constants. For Markov chains, we derive finite-time convergence bounds and exhibit a family of chains for which Rényi-SDPIs improve on classical $χ^2$-based bounds by arbitrarily large factors.

0.34

A Structural Characterization of Entropy Functionals

cs.IT math.ST ·2026-08-14 ·Daniel Lazarev
similarity 0.57
Abstract · 31 pages, 1 figure

Entropy functionals and their associated divergences underlie many statistical methods, including maximum entropy inference, minimum divergence estimation, and goodness-of-fit testing, yet choosing among Shannon, Rényi, Tsallis, and more general entropies is often a matter of convention rather than structural principle. We introduce a measure theoretic framework in which admissibility requires the entropy of an input measure to be bounded above by that of its reference measure whenever the former is absolutely continuous with respect to the latter. Under generalized mean-value composition, we characterize all such entropy functionals and obtain a four-level hierarchy determined successively by the mean generator, entropy scale, and additivity assumptions. A continuous strictly monotone generator $g$ is admissible exactly when $t\mapsto g(1/t)$ is strictly convex for increasing $g$, or strictly concave for decreasing $g$. This resolves a question posed by Rényi (Proc. 4th Berkeley Sympos. Math. Statist. Prob., 1961) concerning which generalized means may replace the arithmetic mean in his entropy axiomatization. The same criterion is equivalent to strict convexity of an associated Csiszár $f$-divergence generator and therefore yields data processing under Markov kernels with an exact equality condition. Within this hierarchy, product additivity singles out the Rényi family, while internal additivity, or product additivity together with arithmetic mean-value composition, singles out Shannon entropy. The characterization is constructive and yields new admissible entropy and divergence families, including integral-transform examples.

0.10

An information identity reveals the geometry of deviation events

cs.IT ·2026-09-29 ·Akshay Balsubramani
similarity 0.57
Abstract

In a deviation event, the empirical measure of $n$ independent draws lands in a set of distributions. The exponent of its probability splits, at every $n$, into two nonnegative terms. The first is the rate: $n$ times the relative entropy, from the population, of the distribution of a typical draw under the event. The second is the dependence that conditioning induces among the draws, measured by their total correlation. Their relative sizes depend on the geometry of the set. This paper focuses on this exact split and on the geometry that the interplay of its two terms reveals. The dependence vanishes exactly when the event confines every draw to a single set, and the classical rate of that constraint is exact. On a set invariant under a compact group that fixes the population and leaves no invariant set of intermediate probability, the rate vanishes; uniform convergence over a hypothesis class that such a group permutes is one. On a half-space whose threshold sits a fixed number of standard errors above the mean, the fraction of the exponent that is dependence tends to a function of the event's probability alone. On a set split into pieces, the dependence is the pieces' average plus $n$ times the Jensen-Shannon divergence of their marginals, minus the entropy of their weights. The split extends to a general reference law. When the information projection is such a law, the split gives the exact value of the expectation in the exponential change of measure to the projection.

0.22

Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies

cs.IT quant-ph ·2026-08-18 ·Kean Chen, Qisheng Wang
similarity 0.56
Abstract · 32 pages, 1 table, 4 algorithms

In this paper, we provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity. Specifically, for order $α$, dimension $d$, and additive error $\varepsilon$, 1. For $0 < α< 1$, the sample complexity is $O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})$ for Rényi entropy and $O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)$ for Tsallis entropy. In particular, for $0 < α\leq 1/2$, the sample complexity for both entropies is $O(d^{1+1/α}/\varepsilon^{1/α})$. 2. For non-integer $α> 1$, the sample complexity is $O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)$ for Rényi entropy. Our upper bounds improve the quantum Rényi entropy estimators due to Acharya, Issa, Shende, and Wagner (2017) and the quantum Tsallis entropy estimators due to Chen, Liu, and Wang (2026), and match the lower bounds recently established by Wang (2026).

0.51

Regularized barycentric Rényi divergences

cs.IT quant-phmath-phmath.FA ·2026-09-15 ·Milán Mosonyi
similarity 0.56
Abstract · 27 pages. v5: Improved presentation, slightly stronger results

Barycentric Rényi divergences were introduced in [Mosonyi, Bunth, Vrana, Linear Algebra and its Applications, 2024] as an alternative to standard Kubo-Ando constructions to define multivariate quantum Rényi divergences. They are defined via a variational expression and depend on a finite collection of quantum relative entropies $D^{q_x}$. When all the relative entropies are monotone under CPTP maps then so are the corresponding barycentric Rényi divergences, and when all the relative entropies are additive then the corresponding barycentric Rényi divergences are subadditive under tensor product. Additivity has only been established before for the case where all $D^{q_x}$ are chosen to be the Umegaki relative entropy, which is also the only case where the barycentric Rényi divergence (called the minimal one) was known to admit an explicit expression. Here we settle the problem of additivity by showing that for any choice of monotone quantum relative entropies, the regularized barycentric Rényi divergence coincides with the minimal barycentric Rényi divergence on invertible inputs. This in turn implies that if at least two of the $D^{q_x}$ are strictly larger than the Umegaki relative entropy (in a precise sense), then the resulting barycentric Rényi divergence is not even weakly additive.

0.20