The first moment method
ProvedFamousTheorems.first_moment_methodThe first moment method. Let be a measure, a set with , and integrable on . Then the set of points with
has positive measure.
A function cannot exceed its average everywhere. In the probabilistic method this is the first moment method: if a random variable has expectation , it takes a value at most with positive probability. It is used to prove the existence of combinatorial objects, such as Erdős' lower bound for Ramsey numbers.
Formalization note. Mathlib's MeasureTheory.measure_le_setAverage_pos. ⨍ a in s, f a ∂μ is the average of f over s.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open MeasureTheory
theorem first_moment_method {α : Type*} {m0 : MeasurableSpace α} {μ : Measure α} {s : Set α} {f : α → ℝ} (hμ : μ s ≠ 0)
(hμ' : μ s ≠ ⊤) (hf : IntegrableOn f s μ) : 0 < μ {x | x ∈ s ∧ f x ≤ ⨍ a in s, f a ∂μ} := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `MeasureTheory.measure_le_setAverage_pos`. Proof here reduces to that Mathlib result.