Linear Shannon Entropy of Plackett–Luce Models with Geometric Weights for All Decay Ratios in the Open Unit Interval
medium tier2026-10-03OP-70reviewed by Claude Code中文版
Abstract
We consider the question of whether the Plackett–Luce choice model with geometric weights $w = (1, \phi, \dots, \phi^{m-1})$ has Shannon entropy $O(m)$ for all decay factors $\phi \in (0, 1)$, settling a conjecture posed in the study of preference elicitation as average-case sorting. Previously, an $O(m)$ upper bound on the entropy was established only for the restricted parameter regime $\phi \in (0, 1/2]$, because the existing proof relied on an entropy monotonicity property of the normalized weight vector under entry removal that fails when $\phi > 1/2$. We answer the question affirmatively for every $\phi \in (0, 1)$, proving that the Shannon entropy of the Plackett–Luce distribution over rankings of $m$ alternatives is bounded by $C(\phi) \cdot m$, where $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$. The proof decomposes the ranking distribution into sequential choice steps and bounds the conditional entropy at each step uniformly over all non-empty subsets of remaining alternatives, completely bypassing the weight monotonicity requirement. More generally, the bound holds for the Plackett–Luce distribution on any finite subset of alternatives of cardinality $n$, yielding an upper bound of $C(\phi) \cdot n$. The main theorem and its supporting lemmas have been formally verified in Lean 4.
1. Introduction
The Plackett–Luce model is a classical probabilistic model for ranking and choice over a finite set of alternatives. Given a finite set $S$ of alternatives and a weight vector assigning a positive real weight to each item, a full ranking is drawn by a sampling-without-replacement process: at each step, the next alternative is selected from the remaining available alternatives with probability proportional to its weight. This sequential formulation induces a probability distribution over the symmetric group of permutations of the alternatives.
In Preference Elicitation as Average-Case Sorting (AAAI 2021), the Plackett–Luce model is studied in the context of preference elicitation, viewed through the lens of average-case sorting. In this setting, the underlying true preference order of an agent over $m$ alternatives is assumed to follow a Plackett–Luce distribution with a geometric weight profile $w = (1, \phi, \dots, \phi^{m-1})$, parameterized by a constant decay factor $\phi \in (0, 1)$. A fundamental information-theoretic quantity in this analysis is the Shannon entropy of the induced distribution over rankings. A ranking of $m$ items has $m!$ possible realizations; thus, an uninformative uniform distribution carries Shannon entropy equal to $\ln(m!) = \Theta(m \ln m)$ nats. By contrast, an entropy bound of order $O(m)$ indicates that the probability mass is concentrated on an effective support of size $2^{O(m)}$, which is exponentially smaller than $m! \approx (m/e)^m$. The central question asked in Section 5 of Preference Elicitation as Average-Case Sorting (AAAI 2021) is whether the Shannon entropy of the Plackett–Luce model with geometric weights is $O(m)$ for every decay factor $\phi \in (0, 1)$.
Theorem 12 of Preference Elicitation as Average-Case Sorting (AAAI 2021) established that the Shannon entropy is indeed $O(m)$ when $\phi \in (0, 1/2]$. However, the mathematical argument underlying Theorem 12 depended crucially on a specific monotonicity property: namely, that removing elements from the weight vector does not increase the Shannon entropy of the normalized weight vector. As observed in that work, this monotonicity property holds strictly when $\phi \le 1/2$, but breaks down whenever $\phi > 1/2$. Because of this limitation, the authors conjectured: "We conjecture that the result remains true for all $\phi \in (0, 1)$." The question of whether linear entropy holds throughout the entire open unit interval $(0, 1)$ remained open.
This post presents the complete resolution of this conjecture. We show that for every $\phi \in (0, 1)$, the Shannon entropy of the Plackett–Luce distribution on $m$ alternatives with geometric weights $(1, \phi, \dots, \phi^{m-1})$ is bounded above by $C(\phi) \cdot m$, where $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$. The proof overcomes the previous barrier by analyzing the conditional entropy of each sequential selection step directly. Rather than requiring monotonicity under removal of items, we establish that the entropy of choosing an item from any non-empty subset $R \subset \mathbb{N}$ under weights $i \mapsto \phi^i$ is bounded above by $C(\phi)$, uniformly across all subsets $R$. Summing this uniform bound across all steps immediately yields an upper bound of $C(\phi) \cdot n$ for any subset of alternatives of size $n$, thereby establishing the linear bound $O(m)$ for all $\phi \in (0, 1)$.
The results described here have been mechanically formalized and verified in the Lean 4 proof assistant. The main theorem settles the open conjecture under the identifier plackett_luce_geometric_entropy_linear, drawing on the supporting lemma plackett_luce_entropy_geometric_le. The subsequent sections detail the formal definitions, the precise statements, the step-by-step mathematical proof, and a discussion of boundary regimes and further questions.
2. Preliminaries
Definition 1: Plackett–Luce Distribution on Finite Sets Let $S \subset \mathbb{N}$ be a non-empty finite set of alternatives with cardinality $|S| = n$, and let $w : \mathbb{N} \to \mathbb{R}$ be a weight function assigning a positive real weight $w(i) > 0$ to each alternative $i \in S$. A ranking of $S$ is a bijective sequence $l = (\sigma_1, \sigma_2, \dots, \sigma_n)$ of the elements of $S$, representing a total ordering where $\sigma_1$ is preferred to $\sigma_2$, and so forth. In the Plackett–Luce model, the probability of obtaining ranking $l$ is given by the product of choice probabilities at each stage: $$P_w(l) = \prod_{k=1}^n \frac{w(\sigma_k)}{\sum_{j=k}^n w(\sigma_j)}.$$ In the formal development, the finite set of all valid rankings of $S$ is denoted by $\text{rankings\_of}(S)$, and the probability of a ranking $l \in \text{rankings\_of}(S)$ under weight function $w$ is denoted by $\text{plackett\_luce\_prob}(w, l)$. Remark 1: The Lean formalization models alternatives as natural numbers in $\mathbb{N}$ and sets of alternatives as finite sets $\text{Finset } \mathbb{N}$. A ranking is represented as an ordered list of elements without duplicates whose support equals $S$. When $S$ is empty, $\text{rankings\_of}(S)$ contains only the empty list, which carries probability 1.
Definition 2: Shannon Entropy of the Plackett–Luce Model (plackett_luce_entropy) Let $w : \mathbb{N} \to \mathbb{R}$ be a weight function, and let $S \subset \mathbb{N}$ be a finite set of alternatives. The Shannon entropy of the Plackett–Luce distribution on rankings of $S$, denoted plackett_luce_entropy, is the expected information content of the ranking distribution: $$\text{`plackett\_luce\_entropy`} (w, S) = \sum_{l \in \text{rankings\_of}(S)} - P_w(l) \ln P_w(l).$$ In the Lean formalization, this is defined noncomputably as: $$\text{`plackett\_luce\_entropy`} (w, S) = \sum_{l \in \text{rankings\_of}(S)} \text{Real.negMulLog}(\text{plackett\_luce\_prob}(w, l)),$$ where $\text{Real.negMulLog}(p) = -p \ln p$ for $p > 0$ and $\text{Real.negMulLog}(0) = 0$. Remark 2: The entropy is measured in nats using the natural logarithm $\ln$ (formalized via $\text{Real.log}$). The definition employs $\text{Real.negMulLog}$, which enforces the standard convention $0 \ln 0 = 0$, ensuring continuity at zero probability. The definition accepts any weight function $w : \mathbb{N} \to \mathbb{R}$ and any finite set $S : \text{Finset } \mathbb{N}$, without requiring $S$ to be an initial segment of integers.
Definition 3: Geometric Weights and the Range of Alternatives For a fixed parameter $\phi \in \mathbb{R}$ satisfying $0 < \phi < 1$, the geometric weight function $w_\phi : \mathbb{N} \to \mathbb{R}$ is defined by $$w_\phi(i) = \phi^i \quad \text{for each } i \in \mathbb{N}.$$ For a natural number $m \in \mathbb{N}$, the standard set of $m$ alternatives is the initial segment $\{0, 1, \dots, m-1\}$, formalized in Lean as $\text{Finset.range}(m)$. On this set, the alternatives have weights $(1, \phi, \phi^2, \dots, \phi^{m-1})$. Remark 3: The parameter $\phi$ is strictly constrained to the open interval $(0, 1)$, meaning that both inequalities $0 < \phi$ and $\phi < 1$ are strict. The alternatives are 0-indexed, so the initial alternative 0 receives weight $\phi^0 = 1$, and subsequent alternatives have geometrically decaying weights.
Definition 4: The Geometric Rate Constant $C(\phi)$ For any parameter $\phi \in (0, 1)$, the geometric rate constant $C(\phi) \in \mathbb{R}$ is defined by $$C(\phi) = \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2} = \ln\left(\frac{1}{1 - \phi}\right) + \ln\left(\frac{1}{\phi}\right) \frac{\phi}{(1 - \phi)^2}.$$ In Lean, this expression appears in the bound of plackett_luce_entropy_geometric_le as $\text{Real.log}(1 - \phi)^{-1} + (-\text{Real.log } \phi) \cdot (\phi / (1 - \phi)^2)$. Remark 4: Because $0 < \phi < 1$, both $1 - \phi$ and $\phi$ lie in $(0, 1)$. Hence, $(1 - \phi)^{-1} > 1$, which implies $\ln((1 - \phi)^{-1}) > 0$. Similarly, $-\ln \phi = \ln(1/\phi) > 0$. Since $\phi / (1 - \phi)^2 > 0$, the constant $C(\phi)$ is strictly positive for all $\phi \in (0, 1)$. The function $\phi \mapsto C(\phi)$ is continuous and monotonically increasing on $(0, 1)$, with $\lim_{\phi \to 0^+} C(\phi) = 0$ and $\lim_{\phi \to 1^-} C(\phi) = \infty$.
3. Main result
Theorem 1 (Linear Shannon Entropy for Geometric Plackett–Luce Models): Let $\phi \in \mathbb{R}$ satisfy $0 < \phi < 1$. Then there exists a real constant $C \in \mathbb{R}$ such that for every natural number $m \in \mathbb{N}$, the Shannon entropy of the Plackett–Luce distribution with geometric weights $i \mapsto \phi^i$ on the initial segment of $m$ alternatives $\{0, 1, \dots, m-1\}$ satisfies $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, \{0, 1, \dots, m-1\}) \le C \cdot m.$$
The Lean statement theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) : ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m reads the English statement by quantifying over a real parameter $\phi$ with hypotheses $0 < \phi$ and $\phi < 1$, and asserting the existence of a real constant $C$ such that for all natural numbers $m$, the Shannon entropy on the range of $m$ alternatives is bounded by $C \cdot m$.
The formal development includes a second, foundational result that sharpens and generalizes Theorem 1:
Lemma 1 (plackett_luce_entropy_geometric_le): Let $\phi \in \mathbb{R}$ satisfy $0 < \phi < 1$. For every natural number $n \in \mathbb{N}$ and every finite set of alternatives $S \subset \mathbb{N}$ with cardinality $|S| = n$, the Shannon entropy satisfies $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \left(\ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}\right) \cdot n.$$
Lemma plackett_luce_entropy_geometric_le adds three critical strengths to Theorem 1:
1. Closed-Form Constant: Rather than merely asserting the non-constructive existence of some constant $C$, the lemma provides the explicit rate constant $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$, whose value can be computed directly for any given parameter $\phi$.
2. Arbitrary Finite Subsets: The bound is not confined to contiguous initial segments $\{0, 1, \dots, m-1\}$. It holds for every finite subset $S \subset \mathbb{N}$, regardless of the gaps between the indices present in $S$. Thus, even after an adversary deletes an arbitrary collection of alternatives, the entropy of the Plackett–Luce model on the remaining alternatives remains bounded by $C(\phi) \cdot |S|$.
3. Full Parameter Coverage: Theorem 12 of Preference Elicitation as Average-Case Sorting (AAAI 2021) established an $O(m)$ bound only for the half-interval $\phi \in (0, 1/2]$. Lemma plackett_luce_entropy_geometric_le extends this linear bound to the entire open interval $\phi \in (0, 1)$, resolving the conjecture posed in that paper.
theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) : ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m
4. Proof
We present the proof following the structure of the Lean formalization. We begin by outlining the core mathematical idea, then present Lemma 1 (plackett_luce_entropy_geometric_le) with its analytical proof, followed by the proof of the main theorem (plackett_luce_geometric_entropy_linear), and conclude with detailed numerical calculations on concrete instances.
A ranking $l = (\sigma_1, \dots, \sigma_n)$ under the Plackett–Luce model on a set of alternatives $S$ with $|S| = n$ is generated through a sequential process consisting of $n$ selection stages. At stage 1, an alternative $\sigma_1 \in S$ is chosen according to the categorical distribution proportional to weights. At any subsequent stage $k \in \{2, \dots, n\}$, conditioned on the sequence of previous choices $(\sigma_1, \dots, \sigma_{k-1})$, the set of remaining available alternatives is $R_k = S \setminus \{\sigma_1, \dots, \sigma_{k-1}\}$, which is a non-empty subset of $S$ of cardinality $n - k + 1$. The next alternative $\sigma_k$ is drawn from $R_k$ with probability $$P(\sigma_k = x \mid R_k) = \frac{\phi^x}{\sum_{y \in R_k} \phi^y}.$$ By the chain rule for Shannon entropy, the joint entropy of the ranking is the sum of the conditional entropies across all $n$ stages: $$H(\sigma_1, \dots, \sigma_n) = \sum_{k=1}^n H(\sigma_k \mid \sigma_1, \dots, \sigma_{k-1}).$$ The conditional entropy at stage $k$ is an average of the entropies of the categorical distributions over $R_k$. If we can show that for every non-empty finite set $R \subset \mathbb{N}$, the entropy of choosing an element from $R$ with probabilities proportional to $\phi^i$ is bounded above by a uniform constant $C(\phi)$, then every term in the sum is bounded by $C(\phi)$. Summing across all $n$ stages yields the upper bound $C(\phi) \cdot n$.
Crucially, this approach does not compare the entropy of the weight vector before and after item removal, which was the source of the $\phi \le 1/2$ restriction in Theorem 12 of Preference Elicitation as Average-Case Sorting (AAAI 2021). Instead, it establishes an absolute upper bound on the single-stage choice entropy that holds universally across all non-empty subsets $R$.
Lemma 1 (plackett_luce_entropy_geometric_le): Let $\phi \in \mathbb{R}$ satisfy $0 < \phi < 1$. For any natural number $n \in \mathbb{N}$ and any finite set $S \subset \mathbb{N}$ with $|S| = n$, $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \left(\ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}\right) \cdot n.$$
Proof of Lemma 1: Let $R \subset \mathbb{N}$ be an arbitrary non-empty finite subset of natural numbers. Let $i_0 = \min(R)$ denote the minimum element of $R$. The normalizing partition function for the choice distribution on $R$ is $$Z = \sum_{i \in R} \phi^i.$$ Since $i \ge i_0$ for all $i \in R$, we can factor out $\phi^{i_0}$: $$Z = \phi^{i_0} \sum_{i \in R} \phi^{i - i_0} = \phi^{i_0} D,$$ where $D = \sum_{i \in R} \phi^{i - i_0}$. Because $i_0 \in R$, the term corresponding to $i = i_0$ is $\phi^0 = 1$. Since all remaining terms $\phi^{i - i_0}$ are strictly positive, we have the lower bound $$D \ge 1.$$ On the other hand, the set of shifted indices $\{i - i_0 : i \in R\}$ consists of distinct non-negative integers containing 0. Therefore, the finite sum is bounded above by the full geometric series: $$D = \sum_{i \in R} \phi^{i - i_0} \le \sum_{j=0}^\infty \phi^j = \frac{1}{1 - \phi}.$$ Now consider the probability distribution on $R$ defined by $p_i = \phi^i / Z$. The Shannon entropy of this distribution is $$H_R = \sum_{i \in R} - p_i \ln p_i = \sum_{i \in R} - \frac{\phi^i}{Z} \ln\left(\frac{\phi^i}{Z}\right).$$ Using the identity $\ln(\phi^i / Z) = i \ln \phi - \ln Z$, we expand the sum: $$H_R = \sum_{i \in R} \frac{\phi^i}{Z} (\ln Z - i \ln \phi) = \ln Z - (\ln \phi) \sum_{i \in R} i \frac{\phi^i}{Z}.$$ Substituting $Z = \phi^{i_0} D$ yields $\ln Z = i_0 \ln \phi + \ln D$. Therefore: $$H_R = i_0 \ln \phi + \ln D - (\ln \phi) \sum_{i \in R} i \frac{\phi^i}{Z} = \ln D - (\ln \phi) \sum_{i \in R} (i - i_0) \frac{\phi^i}{Z}.$$ Since $\phi^i / Z = \phi^{i - i_0} / D$, we rewrite the second term as: $$H_R = \ln D + (-\ln \phi) \frac{\sum_{i \in R} (i - i_0) \phi^{i - i_0}}{D}.$$ Because $0 < \phi < 1$, we have $-\ln \phi = \ln(1/\phi) > 0$. We bound the two terms separately:
1. Term 1: Since $D \le 1 / (1 - \phi)$ and the logarithm is strictly increasing, $$\ln D \le \ln\left(\frac{1}{1 - \phi}\right).$$
2. Term 2: Since $D \ge 1$, the denominator satisfies $1 / D \le 1$. For the numerator, the shifted indices $i - i_0$ are distinct non-negative integers, so $$\sum_{i \in R} (i - i_0) \phi^{i - i_0} \le \sum_{j=0}^\infty j \phi^j.$$ Using the geometric series identity for the derivative, $$\sum_{j=0}^\infty j \phi^j = \phi \frac{d}{d\phi}\left(\sum_{j=0}^\infty \phi^j\right) = \phi \frac{d}{d\phi}\left(\frac{1}{1 - \phi}\right) = \frac{\phi}{(1 - \phi)^2}.$$ Because $-\ln \phi > 0$ and $1/D \le 1$, we have $$(-\ln \phi) \frac{\sum_{i \in R} (i - i_0) \phi^{i - i_0}}{D} \le (-\ln \phi) \frac{\phi}{(1 - \phi)^2}.$$ Summing the bounds on the two terms, we obtain: $$H_R \le \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2} = C(\phi).$$ This uniform bound holds for every non-empty subset $R \subset \mathbb{N}$, regardless of its size, elements, or gaps. At stage $k$ of the sequential process on $S$, the remaining set $R_k$ has cardinality $n - k + 1 \ge 1$. Hence, the conditional entropy at stage $k$ satisfies $H(\sigma_k \mid \sigma_1, \dots, \sigma_{k-1}) \le C(\phi)$. At the final stage $k = n$, the remaining set has $|R_n| = 1$, which has entropy $0 \le C(\phi)$. Summing over all $n$ stages yields: $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \sum_{k=1}^n C(\phi) = C(\phi) \cdot n.$$ This completes the proof of Lemma 1.
Proof of Theorem 1 (plackett_luce_geometric_entropy_linear): Given $\phi \in \mathbb{R}$ with $0 < \phi$ and $\phi < 1$, we instantiate the existential quantifier $\exists C : \mathbb{R}$ with the rate constant $$C = \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}.$$ In Lean, this witness is supplied using the anonymous constructor ⟨_, ...⟩. For an arbitrary natural number $m : \mathbb{N}$, we consider the set of alternatives $S = \text{Finset.range}(m)$. By the library lemma $\text{Finset.card\_range}(m)$, the cardinality of this set is precisely $|S| = m$. Applying plackett_luce_entropy_geometric_le with parameter $\phi$, hypotheses $h_0 : 0 < \phi$ and $h_1 : \phi < 1$, cardinality $m$, set $\text{Finset.range}(m)$, and the cardinality equality yields the inequality: $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, \text{Finset.range}(m)) \le C \cdot m.$$ The tactic simpa simplifies the expression and completes the proof in Lean.
To enable verification by hand, we evaluate the bound on two concrete instances.
Instance 1: $\phi = 1/2$, $m = 3$ alternatives ($S = \{0, 1, 2\}$). This instance lies in the parameter regime $\phi \le 1/2$ previously analyzed. We begin by computing the constant $C(1/2)$: - $1 - \phi = 1/2 \implies (1 - \phi)^{-1} = 2$, so $\ln(1/(1 - \phi)) = \ln 2 \approx 0.693147$ nats. - $-\ln \phi = -\ln(1/2) = \ln 2 \approx 0.693147$ nats. - $\phi / (1 - \phi)^2 = (1/2) / (1/4) = 2$. - $C(1/2) = \ln 2 + 2 \ln 2 = 3 \ln 2 = \ln 8 \approx 2.079442$ nats. For $m = 3$, the linear upper bound is: $$C(1/2) \cdot 3 = 9 \ln 2 \approx 6.238325 \text{ nats}.$$ We now compute the exact distribution and entropy by hand. The weights are $w(0) = 1$, $w(1) = 1/2$, and $w(2) = 1/4$. Multiplying by 4 gives integer weights $(4, 2, 1)$ with sum 7. There are $3! = 6$ possible rankings $l = (\sigma_1, \sigma_2, \sigma_3)$: 1. Ranking $(0, 1, 2)$: probability $p_1 = (4/7) \cdot (2/3) \cdot 1 = 8/21 \approx 0.380952$. 2. Ranking $(0, 2, 1)$: probability $p_2 = (4/7) \cdot (1/3) \cdot 1 = 4/21 \approx 0.190476$. 3. Ranking $(1, 0, 2)$: probability $p_3 = (2/7) \cdot (4/5) \cdot 1 = 8/35 \approx 0.228571$. 4. Ranking $(1, 2, 0)$: probability $p_4 = (2/7) \cdot (1/5) \cdot 1 = 2/35 \approx 0.057143$. 5. Ranking $(2, 0, 1)$: probability $p_5 = (1/7) \cdot (4/6) \cdot 1 = 2/21 \approx 0.095238$. 6. Ranking $(2, 1, 0)$: probability $p_6 = (1/7) \cdot (2/6) \cdot 1 = 1/21 \approx 0.047619$. Verifying the total probability: $$p_1 + p_2 + p_5 + p_6 = \frac{8 + 4 + 2 + 1}{21} = \frac{15}{21} = \frac{5}{7}.$$ $$p_3 + p_4 = \frac{8 + 2}{35} = \frac{10}{35} = \frac{2}{7}.$$ Sum: $5/7 + 2/7 = 1$. The individual entropy components $-p_i \ln p_i$ are: - $-p_1 \ln p_1 \approx -(0.380952)(-0.965081) \approx 0.367645$ - $-p_2 \ln p_2 \approx -(0.190476)(-1.658228) \approx 0.315808$ - $-p_3 \ln p_3 \approx -(0.228571)(-1.475907) \approx 0.337349$ - $-p_4 \ln p_4 \approx -(0.057143)(-2.862201) \approx 0.163539$ - $-p_5 \ln p_5 \approx -(0.095238)(-2.351375) \approx 0.224016$ - $-p_6 \ln p_6 \approx -(0.047619)(-3.044522) \approx 0.144976$ Summing these values yields the exact Shannon entropy: $$H \approx 0.367645 + 0.315808 + 0.337349 + 0.163539 + 0.224016 + 0.144976 \approx 1.553333 \text{ nats}.$$ Comparing with the theoretical bound: $$1.553333 \le 6.238325.$$ The bound holds with substantial margin.
Instance 2: $\phi = 3/4$, which lies in the previously open interval $(1/2, 1)$. Because $\phi = 3/4 > 1/2$, Theorem 12 of Preference Elicitation as Average-Case Sorting (AAAI 2021) did not apply. We compute the constant $C(3/4)$: - $1 - \phi = 1/4 \implies (1 - \phi)^{-1} = 4$, so $\ln(1/(1 - \phi)) = \ln 4 = 2 \ln 2 \approx 1.386294$ nats. - $-\ln \phi = -\ln(3/4) = \ln(4/3) \approx 0.287682$ nats. - $\phi / (1 - \phi)^2 = (3/4) / (1/16) = 12$. - $C(3/4) = \ln 4 + 12 \ln(4/3) \approx 1.386294 + 12 \cdot 0.287682 \approx 4.838479$ nats. For $m = 2$ alternatives ($S = \{0, 1\}$), the weights are $w(0) = 1$ and $w(1) = 3/4$. The two possible rankings are $(0, 1)$ with probability $4/7$ and $(1, 0)$ with probability $3/7$. The exact Shannon entropy is: $$H = -\frac{4}{7} \ln\left(\frac{4}{7}\right) - \frac{3}{7} \ln\left(\frac{3}{7}\right) \approx 0.319799 + 0.363131 \approx 0.682930 \text{ nats}.$$ The theoretical bound gives: $$C(3/4) \cdot 2 \approx 4.838479 \cdot 2 = 9.676958 \text{ nats}.$$ The inequality $0.682930 \le 9.676958$ is verified.
5. Discussion
We discuss the implications of the result, what it does and does not cover, and the remaining questions highlighted by the setting.
The result settles the conjecture stated in Section 5 of Preference Elicitation as Average-Case Sorting (AAAI 2021) in full generality. The source paper proved that the Shannon entropy of the Plackett–Luce model with weights $(1, \phi, \dots, \phi^{m-1})$ is $O(m)$ for $\phi \in (0, 1/2]$, and conjectured that the linear bound extends to all $\phi \in (0, 1)$. Theorem plackett_luce_geometric_entropy_linear settles this conjecture positively. Furthermore, lemma plackett_luce_entropy_geometric_le provides an explicit closed-form constant $C(\phi)$ and shows that the linear bound holds for arbitrary subsets $S \subset \mathbb{N}$ of cardinality $n$, not merely contiguous initial segments.
The theorem specifically addresses the open unit interval $\phi \in (0, 1)$. It is instructive to examine the boundaries and limitations of this result:
1. The boundary $\phi = 1$: When $\phi = 1$, the weights are uniform, $w = (1, 1, \dots, 1)$. Under uniform weights, every ranking is equally likely, yielding the uniform distribution over $m!$ permutations. The Shannon entropy of this distribution is $\ln(m!) = \sum_{k=1}^m \ln k = m \ln m - m + O(\ln m)$, which is strictly superlinear ($\Theta(m \ln m)$ nats). Consequently, linear entropy does not hold at $\phi = 1$. This singularity is reflected in the rate constant $C(\phi)$: as $\phi \to 1^-$, we have $(1 - \phi)^{-1} \to \infty$ and $\phi / (1 - \phi)^2 \to \infty$, so $C(\phi) \to \infty$. The divergence of $C(\phi)$ as $\phi \to 1^-$ accurately mirrors the transition from linear entropy to superlinear entropy.
2. The regime $\phi > 1$: When $\phi > 1$, the weights increase geometrically with the index. On a finite set of $m$ alternatives, one can reverse the labeling of the items via the bijection $i \mapsto m - 1 - i$, which transforms the weight vector into geometric weights with parameter $\psi = 1/\phi \in (0, 1)$. Reversing labels is a bijection on rankings and preserves entropy; thus, the entropy on the range $\{0, \dots, m-1\}$ remains $O(m)$ for any fixed $\phi > 1$. However, on an infinite ground set $\mathbb{N}$, the weights diverge to infinity, and the partition function over infinite subsets does not converge.
3. General weight distributions: The result is specific to geometric weights $w(i) = \phi^i$. In average-case sorting and preference elicitation, other parametric families of weights are often relevant, such as harmonic weights $w_i = (i + 1)^{-1}$ or polynomial decay $w_i = (i + 1)^{-\alpha}$ for $\alpha > 0$. For harmonic weights, the partition function diverges logarithmically, and the entropy behavior interpolates between uniform and geometric settings. Determining necessary and sufficient conditions on a general weight sequence $w : \mathbb{N} \to \mathbb{R}_{>0}$ to guarantee linear Shannon entropy remains an open question not addressed by this work.
4. Asymptotic tightness of the constant: While $C(\phi)$ provides an explicit upper bound for all $n$, it is not tight. For instance, as $\phi \to 0^+$, $C(\phi) \sim \phi \ln(1/\phi)$, while the exact asymptotic entropy rate $\lim_{m \to \infty} \frac{1}{m} \text{plackett\_luce\_entropy}(w_\phi, \text{range}(m))$ may differ. Determining the exact value of this asymptotic limit is a natural question for future study.
Why it is research-level
- settles OP-70 (Linear entropy of geometric Plackett–Luce models)
Lean declarations
- 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,…
- 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) =…
- plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.