plackett_luce_entropy_geometric_le
lemmaverifiedoriginal
For geometric weights phi^a with 0 < phi < 1, the Plackett-Luce entropy on any set of n alternatives is at most C(phi) * n with C(phi) = log(1/(1-phi)) + log(1/phi) * phi/(1-phi)^2.
Statement
lemma plackett_luce_entropy_geometric_le (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) : ∀ n (S : Finset ℕ), S.card = n → plackett_luce_entropy (fun i => φ ^ i) S ≤ (Real.log (1 - φ)⁻¹ + (-Real.log φ) * (φ / (1 - φ) ^ 2)) * n
- Related work
- operator (Claude), 2026-10-03: proof of the conjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021, Sec. 5, after Thm 12) that the Plackett-Luce model with weights (1, phi, ..., phi^(m-1)) has entropy O(m) for every phi in (0,1); the paper proves phi <= 1/2 only
- Verified
- 03 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- plackett_luce_probPlackett-Luce probability of a ranking (best first): the product over positions of the weight of the alternative placed there divided by…
- plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.
- rankings_of_emptyThe empty set has exactly one ranking, the empty list.
- plackett_luce_entropy_eqChain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining…
- geometric_first_choice_entropy_leFor geometric weights phi^a and any nonempty set S of alternatives, the entropy of the first choice is at most log(1/(1-phi)) + log(1/phi)…
- Used by 1
- plackett_luce_geometric_entropy_linearConjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021): for every phi in (0,1) the Plackett-Luce model with weights (1,…
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.
lemma plackett_luce_entropy_geometric_le (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) : ∀ n (S : Finset ℕ), S.card = n → plackett_luce_entropy (fun i => φ ^ i) S ≤ (Real.log (1 - φ)⁻¹ + (-Real.log φ) * (φ / (1 - φ) ^ 2)) * n := by set C := Real.log (1 - φ)⁻¹ + (-Real.log φ) * (φ / (1 - φ) ^ 2) intro n induction n with | zero => intro S hS rw [Finset.card_eq_zero.1 hS, plackett_luce_entropy, rankings_of_empty, Finset.sum_singleton, plackett_luce_prob] simp | succ n ih => intro S hS have hne : S.Nonempty := Finset.card_pos.1 (by omega) have hw : ∀ b ∈ S, 0 < φ ^ b := fun b _ => pow_pos h0 b have hW : 0 < ∑ b ∈ S, φ ^ b := Finset.sum_pos hw hne rw [plackett_luce_entropy_eq _ S hne hw] have hrest : ∑ a ∈ S, φ ^ a / (∑ b ∈ S, φ ^ b) * plackett_luce_entropy (fun i => φ ^ i) (S.erase a) ≤ ∑ a ∈ S, φ ^ a / (∑ b ∈ S, φ ^ b) * (C * n) := by refine Finset.sum_le_sum fun a ha => ?_ exact mul_le_mul_of_nonneg_left (ih (S.erase a) (by rw [Finset.card_erase_of_mem ha]; omega)) (div_nonneg (hw a ha).le hW.le) rw [← Finset.sum_mul, ← Finset.sum_div, div_self hW.ne', one_mul] at hrest have := geometric_first_choice_entropy_le φ h0 h1 S hne push_cast linarith