plackett_luce_surprisal_variance_profile_nonneg
For any weight profile w on [0,1], the asymptotic surprisal variance plackett_luce_surprisal_variance_profile w is non-negative.
Statement
theorem plackett_luce_surprisal_variance_profile_nonneg (w : ℝ → ℝ) :
0 ≤ plackett_luce_surprisal_variance_profile w- Source
- arXiv:2009.09172 (Preference Elicitation as Average-Case Sorting, AAAI 2021)
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- plackett_luce_surprisal_variance_profileThe asymptotic surprisal variance V for a weight profile w is the integral over x in [0,1] of the variance of log(L(X_x)) + w(x) * X_x,…
- plackett_luce_laplace_profileFor a weight profile w on [0,1], the Laplace profile L(t) is the integral over [0,1] of w(x) * exp(-t * w(x)) dx.
Read back from the Lean
For every function $w : ℝ → ℝ$, the Plackett-Luce surprisal variance profile of $w$ is greater than or equal to 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The asymptotic surprisal variance profile is defined as an integral over the unit interval [0, 1] of the variance of a random variable under an exponential distribution. The proof expands this definition and applies the fact that an integral of a non-negative function over a measurable set is non-negative. Pointwise non-negativity of the integrand then follows immediately because the variance of any real-valued random variable is non-negative.
It suffices to show that the integrand in the definition of the surprisal variance profile is non-negative for every x ∈ [0, 1].
Rewriting with the definition of `plackett_luce_surprisal_variance_profile` expresses the profile as an integral over the closed interval [0, 1]. By `MeasureTheory.setIntegral_nonneg`, an integral over a set is non-negative provided the set is measurable and the integrand is non-negative everywhere on it; the interval [0, 1] is measurable by `measurableSet_Icc`.
uses
plackett_luce_surprisal_variance_profile,MeasureTheory.setIntegral_nonneg,measurableSet_Iccrw [plackett_luce_surprisal_variance_profile] apply MeasureTheory.setIntegral_nonneg measurableSet_Icc
For every x ∈ [0, 1], the integrand is non-negative, completing the proof.
Let x ∈ [0, 1] be given. The integrand at x is the variance of the random variable t ↦ ln(plackett_luce_laplace_profile w t) + w(x) * t under the exponential measure with parameter w(x). By `ProbabilityTheory.variance_nonneg`, the variance of any real-valued random variable is non-negative.
uses
ProbabilityTheory.variance_nonnegintro x hx exact ProbabilityTheory.variance_nonneg _ (ProbabilityTheory.expMeasure (w x))
plackett_luce_surprisal_variance_profile- The definition of the asymptotic surprisal variance profile of a weight function w as an integral over the unit interval [0, 1] of the variance of t ↦ ln(plackett_luce_laplace_profile w t) + w(x) * t with respect to the exponential measure expMeasure(w(x)).
MeasureTheory.setIntegral_nonneg- The integral of a function over a set s is non-negative whenever s is measurable and the function is non-negative at every point of s.
measurableSet_Icc- The closed interval [a, b] is a measurable set in an ordered topological space with closed rays.
ProbabilityTheory.variance_nonneg- The variance of any real-valued random variable with respect to any measure is non-negative.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The asymptotic surprisal variance profile is always non-negative. -/theorem plackett_luce_surprisal_variance_profile_nonneg (w : ℝ → ℝ) : 0 ≤ plackett_luce_surprisal_variance_profile w := by rw [plackett_luce_surprisal_variance_profile] apply MeasureTheory.setIntegral_nonneg measurableSet_Icc intro x hx exact ProbabilityTheory.variance_nonneg _ (ProbabilityTheory.expMeasure (w x))