sum_plackett_luce_prob
lemmaverified
With positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
Statement
lemma sum_plackett_luce_prob (w : ℕ → ℝ) :
∀ n (S : Finset ℕ), S.card = n → (∀ b ∈ S, 0 < w b) →
∑ l ∈ rankings_of S, plackett_luce_prob w l = 1- 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 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…
- rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
- rankings_of_emptyThe empty set has exactly one ranking, the empty list.
- 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.
- Used by 1
- 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…
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 sum_plackett_luce_prob (w : ℕ → ℝ) : ∀ n (S : Finset ℕ), S.card = n → (∀ b ∈ S, 0 < w b) → ∑ l ∈ rankings_of S, plackett_luce_prob w l = 1 := by intro n induction n with | zero => intro S hS _ rw [Finset.card_eq_zero.1 hS, rankings_of_empty, Finset.sum_singleton, plackett_luce_prob] | succ n ih => intro S hS hw have hne : S.Nonempty := Finset.card_pos.1 (by omega) have hW : 0 < ∑ b ∈ S, w b := Finset.sum_pos hw hne rw [sum_rankings_of_nonempty S hne] calc ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), plackett_luce_prob w (a :: t) = ∑ a ∈ S, w a / (∑ b ∈ S, w b) := by refine Finset.sum_congr rfl fun a ha => ?_ rw [Finset.sum_congr rfl fun t ht => plackett_luce_prob_cons w S a ha t ht, ← Finset.mul_sum, ih (S.erase a) (by rw [Finset.card_erase_of_mem ha]; omega) (fun b hb => hw b (Finset.mem_of_mem_erase hb)), mul_one] _ = 1 := by rw [← Finset.sum_div, div_self hW.ne']