AFTD Auto-Formalizing Theoretical Domains

plackett_luce_surprisal_variance_profile_nonneg

theoremverified

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

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.

  1. 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`.

    lines 4–5

    uses plackett_luce_surprisal_variance_profile, MeasureTheory.setIntegral_nonneg, measurableSet_Icc

      rw [plackett_luce_surprisal_variance_profile]
      apply MeasureTheory.setIntegral_nonneg measurableSet_Icc
  2. 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.

    lines 6–7

    uses ProbabilityTheory.variance_nonneg

      intro 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

/-- 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))
See it in the graphDiscuss this resultChallenge it