Rearrangements of distributions on integers that minimize variance

2025/10/09 by Aistis Atminas, Atminas, Aistis, Valentas Kurauskas +1
Computer Science · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2510.07899

openalex publication_date 2025/10/09 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

Which permutations of a probability distribution on integers minimize variance? Let X be a random variable on a set of integers \x₁, …, x_N\ such that ℙ(X_i = x_i) = p_i, i ∈ \1,…,N\. Let (p⁽¹⁾, …, p^(N)) be the sequence (p₁, …, p_N) ordered non-increasingly. Let X⁺ be the random variable defined by ℙ(X⁺=0)=p⁽¹⁾, ℙ(X⁺=1) = p⁽²⁾, ℙ(X⁺=-1)=p⁽³⁾, …, ℙ(X⁺=(-1)^N \lfloor \frac N 2 \rfloor)=p^(N). In this short note we generalize and prove the inequality Var X⁺ ≤ Var X.

Citations

• The sharp form of the Kolmogorov--Rogozin inequality and a conjecture of Leader--Radcliffe

Related

• The runsort permuton
• Records, permutations and greatest convex minorants
• Variance Bounds: Some Old and Some New
• Mean and variance of the longest alternating subsequence in a random separable permutation
• On the maximal halfspace depth of permutation-invariant distributions on the simplex