Documentation

Linglib.Core.Analysis.MeanInequalities

Gibbs' inequality for finite sums #

For weights $p$ summing to $1$ and $q$ summing to at most $1$, Gibbs' inequality says $\prod_i q_i^{p_i} \le \prod_i p_i^{p_i}$: the geometric mean of $q$ weighted by $p$ is greatest at $q = p$. It is the weighted inequality of arithmetic and geometric means applied to the ratios $q_i / p_i$, which bounds the left side by $\sum_i q_i$ times the right with no condition on $q$. Its logarithm says the cross-entropy of $q$ relative to $p$ is at least the entropy of $p$; mathlib has that for measures as InformationTheory.integral_llr_add_sub_measure_univ_nonneg.

With the relative frequencies of counts $x$ as the weights, it bounds the likelihood of the counts under any $q$ by their likelihood under their relative frequencies, so the maximum-likelihood estimate of a categorical distribution is the empirical one. Equality holds only at $q = p$, so the estimate is unique.

Implementation notes #

[UPSTREAM] candidate for the AM-GM section of Mathlib/Analysis/MeanInequalities.lean. The Each statement comes in Real, NNReal and ENNReal versions with the arguments of the corresponding geom_mean_le_arith_mean_weighted; the ℝ≥0∞ equality case is transferred from the real one.

References #

theorem Real.prod_rpow_le_sum_mul_prod_rpow_self {ι : Type u_1} (s : Finset ι) (p q : ι → ℝ) (hp : ∀ i ∈ s, 0 ≤ p i) (hp' : ∑ i ∈ s, p i = 1) (hq : ∀ i ∈ s, 0 ≤ q i) :
∏ i ∈ s, q i ^ p i ≤ (∑ i ∈ s, q i) * ∏ i ∈ s, p i ^ p i

Gibbs' inequality, homogeneous in q: the geometric mean of q weighted by p is at most the total of q times the geometric mean of p weighted by itself.

theorem Real.prod_rpow_le_prod_rpow_self {ι : Type u_1} (s : Finset ι) (p q : ι → ℝ) (hp : ∀ i ∈ s, 0 ≤ p i) (hp' : ∑ i ∈ s, p i = 1) (hq : ∀ i ∈ s, 0 ≤ q i) (hq' : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ p i ≤ ∏ i ∈ s, p i ^ p i

Gibbs' inequality: the geometric mean of q weighted by p, over q summing to at most 1, is greatest at q = p.

theorem Real.prod_rpow_eq_prod_rpow_self_iff {ι : Type u_1} (s : Finset ι) (p q : ι → ℝ) (hp : ∀ i ∈ s, 0 ≤ p i) (hp' : ∑ i ∈ s, p i = 1) (hq : ∀ i ∈ s, 0 ≤ q i) (hq' : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ p i = ∏ i ∈ s, p i ^ p i ↔ ∀ i ∈ s, q i = p i

Gibbs' inequality, equality case: the geometric mean of q weighted by p, over q summing to at most 1, attains its greatest value only at q = p.

theorem NNReal.prod_rpow_le_prod_rpow_self {ι : Type u_1} (s : Finset ι) (p q : ι → NNReal) (hp : ∑ i ∈ s, p i = 1) (hq : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ ↑(p i) ≤ ∏ i ∈ s, p i ^ ↑(p i)

Gibbs' inequality: the geometric mean of q weighted by p, over q summing to at most 1, is greatest at q = p.

theorem NNReal.prod_rpow_eq_prod_rpow_self_iff {ι : Type u_1} (s : Finset ι) (p q : ι → NNReal) (hp : ∑ i ∈ s, p i = 1) (hq : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ ↑(p i) = ∏ i ∈ s, p i ^ ↑(p i) ↔ ∀ i ∈ s, q i = p i

Gibbs' inequality, equality case: the geometric mean of q weighted by p, over q summing to at most 1, attains its greatest value only at q = p.

theorem ENNReal.prod_rpow_le_sum_mul_prod_rpow_self {ι : Type u_1} (s : Finset ι) (p : ι → NNReal) (q : ι → ENNReal) (hp : ∑ i ∈ s, p i = 1) :
∏ i ∈ s, q i ^ ↑(p i) ≤ (∑ i ∈ s, q i) * ∏ i ∈ s, ↑(p i) ^ ↑(p i)

Gibbs' inequality, homogeneous in q: the geometric mean of q weighted by p is at most the total of q times the geometric mean of p weighted by itself.

theorem ENNReal.prod_rpow_le_prod_rpow_self {ι : Type u_1} (s : Finset ι) (p : ι → NNReal) (q : ι → ENNReal) (hp : ∑ i ∈ s, p i = 1) (hq : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ ↑(p i) ≤ ∏ i ∈ s, ↑(p i) ^ ↑(p i)

Gibbs' inequality: the geometric mean of q weighted by p, over q summing to at most 1, is greatest at q = p.

theorem ENNReal.prod_rpow_eq_prod_rpow_self_iff {ι : Type u_1} (s : Finset ι) (p : ι → NNReal) (q : ι → ENNReal) (hp : ∑ i ∈ s, p i = 1) (hq : ∑ i ∈ s, q i ≤ 1) :
∏ i ∈ s, q i ^ ↑(p i) = ∏ i ∈ s, ↑(p i) ^ ↑(p i) ↔ ∀ i ∈ s, q i = ↑(p i)

Gibbs' inequality, equality case: the geometric mean of q weighted by p, over q summing to at most 1, attains its greatest value only at q = p.

theorem ENNReal.prod_pow_le_prod_div_sum_pow {ι : Type u_1} (s : Finset ι) {w : ι → ENNReal} (hsum : ∑ i ∈ s, w i ≤ 1) (x : ι → ℕ) :
∏ i ∈ s, w i ^ x i ≤ ∏ i ∈ s, (↑(x i) / ∑ j ∈ s, ↑(x j)) ^ x i

Maximum likelihood of a categorical distribution. Under weights w summing to at most 1, counts x have likelihood at most their likelihood under their relative frequencies.

theorem ENNReal.prod_pow_eq_prod_div_sum_pow_iff {ι : Type u_1} (s : Finset ι) {w : ι → ENNReal} (hsum : ∑ i ∈ s, w i ≤ 1) {x : ι → ℕ} (hX : ∑ j ∈ s, x j ≠ 0) :
∏ i ∈ s, w i ^ x i = ∏ i ∈ s, (↑(x i) / ∑ j ∈ s, ↑(x j)) ^ x i ↔ ∀ i ∈ s, w i = ↑(x i) / ∑ j ∈ s, ↑(x j)

Uniqueness of the maximum-likelihood estimate. Under weights w summing to at most 1, counts x that are not all 0 attain their greatest likelihood only at their relative frequencies.