Superadditivity of the pair weight
ProvedBanditAlgorithm.pair_weight_superadditiveFor positive reals ,
The function is half the harmonic mean, characterised by ; in electrical language it is the resistance of two resistors in parallel, and the inequality says that thickening both branches of a parallel pair is at least as good as running the two pairs separately. Since is positively homogeneous of degree one, superadditivity is equivalent to concavity on the open quadrant, so this is the concavity of in the form that avoids mentioning convex combinations.
Clearing denominators reduces the claim to : writing for the difference of the two sides multiplied by , one has the polynomial identity . So the inequality and the description of its equality case come from a single computation.
In the best-arm-identification application is the effective sample size of the pair under an allocation , and concavity of the objective is what makes the set of optimal allocations convex.
import Mathlib.Analysis.SpecialFunctions.Log.Basic
theorem BanditAlgorithm.pair_weight_superadditive {x₁ y₁ x₂ y₂ : ℝ}
(hx₁ : 0 < x₁) (hy₁ : 0 < y₁) (hx₂ : 0 < x₂) (hy₂ : 0 < y₂) :
x₁ * y₁ / (x₁ + y₁) + x₂ * y₂ / (x₂ + y₂)
≤ (x₁ + x₂) * (y₁ + y₂) / ((x₁ + x₂) + (y₁ + y₂)) := by
sorry