Small zero-sum perturbations preserve a strictly positive simplex point
ProvedstdSimplex_small_perturbationbanditsconvex-geometrypartial-monitoringprobability-simplex
Let be a probability vector whose coordinates are all strictly positive, and let have zero coordinate sum. Then there is a radius such that every perturbation with is again a probability vector:
In particular, both and remain valid stochastic environments for sufficiently small . This is the simplex-interiority step in two-environment information-theoretic lower bounds.
Preamble
import Mathlib.Analysis.Convex.StdSimplex import Mathlib.Data.Finset.Max import Mathlib.Tactic
Formal statement
theorem stdSimplex_small_perturbation
{d : ℕ} (u q : Fin d → ℝ)
(hu : u ∈ stdSimplex ℝ (Fin d))
(hupos : ∀ i, 0 < u i) (hq : ∑ i, q i = 0) :
∃ δ : ℝ, 0 < δ ∧ ∀ Δ : ℝ, |Δ| ≤ δ →
(fun i ↦ u i + Δ * q i) ∈ stdSimplex ℝ (Fin d) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 1, printed p. 490, paragraph surrounding Eq. (37.7).