plackett_luce_entropy_eq
lemmaverified
Chain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining alternatives.
Statement
lemma plackett_luce_entropy_eq (w : ℕ → ℝ) (S : Finset ℕ) (hS : S.Nonempty)
(hw : ∀ b ∈ S, 0 < w b) :
plackett_luce_entropy w S =
∑ a ∈ S, Real.negMulLog (w a / ∑ b ∈ S, w b) +
∑ a ∈ S, w a / (∑ b ∈ S, w b) * plackett_luce_entropy w (S.erase a)- Source
- step towards plackett_luce_geometric_entropy_linear (Preference Elicitation as Average-Case Sorting, AAAI 2021, Sec. 5 conjecture (entropy O(m) for every phi in (0,1)))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.
- sum_rankings_of_nonemptyFor nonempty S, a sum over rankings of S splits as a sum over the top alternative a and the rankings of S minus a.
- plackett_luce_prob_consIf a is in S and t ranks S minus a, the Plackett-Luce probability of a followed by t is w(a)/w(S) times that of t.
- sum_plackett_luce_probWith positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
- Used by 1
- plackett_luce_entropy_geometric_leFor 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) =…
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.
/-- Chain rule (grouping by the top-ranked alternative). -/lemma plackett_luce_entropy_eq (w : ℕ → ℝ) (S : Finset ℕ) (hS : S.Nonempty) (hw : ∀ b ∈ S, 0 < w b) : plackett_luce_entropy w S = ∑ a ∈ S, Real.negMulLog (w a / ∑ b ∈ S, w b) + ∑ a ∈ S, w a / (∑ b ∈ S, w b) * plackett_luce_entropy w (S.erase a) := by unfold plackett_luce_entropy rw [sum_rankings_of_nonempty S hS, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun a ha => ?_ have h1 := sum_plackett_luce_prob w _ (S.erase a) rfl (fun b hb => hw b (Finset.mem_of_mem_erase hb)) rw [Finset.sum_congr rfl fun t ht => by rw [plackett_luce_prob_cons w S a ha t ht, Real.negMulLog_mul], Finset.sum_add_distrib, ← Finset.sum_mul, h1, one_mul, ← Finset.mul_sum]