A finite strictly positive probability average has a realization at most its mean
ProvedNarrowDNF.Weighted.exists_le_meancombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Let be a nonempty finite set, let satisfy for every and , and let be arbitrary. Then
There is no nonnegativity condition on . This finite averaging principle selects a deterministic realization from the random choices used by the approximation construction.
Preamble
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Real.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
namespace NarrowDNF
end NarrowDNF
namespace NarrowDNF.Weighted
end NarrowDNF.Weighted
open NarrowDNF
open NarrowDNF
open NarrowDNF.Weighted
open scoped BigOperators
variable {α : Type*} [Fintype α]
Formal statement
theorem NarrowDNF.Weighted.exists_le_mean [Nonempty α] (weights : α → ℝ)
(hw : ∀ x, 0 < weights x) (hs : ∑ x, weights x = 1) (value : α → ℝ) :
∃ x, value x ≤ ∑ y, weights y * value y := by sorrySource