mixture_representation_monotone_distribution
Let $P : \mathbb{N}^+ \to \mathbb{R}$ be a nonincreasing probability distribution on the positive integers, so that $P(k) \ge 0$ for all $k$, $P$ is antitone, and $\sum_{k=1}^\infty P(k) = 1$. Then the mixture weights $w_k = k(P(k) - P(k+1))$ satisfy: $w_k \ge 0$ for all $k \in \mathbb{N}^+$; $\sum_{k=1}^\infty w_k = 1$; for every $n \in \mathbb{N}^+$, $\sum_{k=n}^\infty \frac{w_k}{k} = P(n)$; and for every $n \in \mathbb{N}^+$, $\sum_{k=1}^\infty w_k U_k(n) = P(n)$, where $U_k$ is the uniform distribution on $\{1, \dots, k\}$.
Statement
theorem mixture_representation_monotone_distribution (P : ℕ+ → ℝ) (h_nonneg : ∀ k : ℕ+, 0 ≤ P k) (h_anti : Antitone P) (h_sum : HasSum P 1) : (∀ k : ℕ+, 0 ≤ monotoneMixtureWeight P k) ∧ HasSum (monotoneMixtureWeight P) 1 ∧ (∀ n : ℕ+, HasSum (fun k : ℕ+ => if n ≤ k then monotoneMixtureWeight P k / (k : ℝ) else 0) (P n)) ∧ (∀ n : ℕ+, HasSum (fun k : ℕ+ => monotoneMixtureWeight P k * uniformDistribution k n) (P n))
- Formalizes
- arXiv:2610.01563 Lemma 3
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- monotoneMixtureWeightFor a sequence $P : \mathbb{N}^+ \to \mathbb{R}$, the mixture weight at $k \in \mathbb{N}^+$ is defined by $w_k = k (P(k) - P(k+1))$.
- uniformDistributionThe uniform distribution $U_k$ on $\{1, \dots, k\}$, viewed as a function on $\mathbb{N}^+$, evaluates to $1/k$ for $n \le k$ and $0$ for…
- monotoneMixtureWeight_nonnegIf $P : \mathbb{N}^+ \to \mathbb{R}$ is antitone (nonincreasing), then the mixture weight $w_k = k(P(k) - P(k+1))$ is nonnegative for…
- monotoneMixtureWeight_sum_by_partsFor any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any $n \in \mathbb{N}^+, the finite sum of mixture weights satisfies $\sum_{k=1}^n…
- monotone_distribution_telescoping_sumFor any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any positive integers $n \le N$, the sum $\sum_{k=n}^N \frac{w_k}{k}$ telescopes to…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
Let $P : \mathbb{N}^+ \to \mathbb{R}$ be a sequence of real numbers indexed by the positive integers. Assume:
1. $P$ is non-negative everywhere: for every $k \in \mathbb{N}^+$, $0 \le P(k)$.
2. $P$ is antitone (non-increasing): for all $a, b \in \mathbb{N}^+$, if $a \le b$, then $P(b) \le P(a)$.
3. The infinite sum of $P$ converges to 1: $\sum_{k \in \mathbb{N}^+} P(k) = 1$ (in the sense of HasSum P 1).
Then the following four conclusions hold:
1. For every $k \in \mathbb{N}^+$, the mixture weight $\text{monotoneMixtureWeight}(P, k) \ge 0$.
2. The infinite sum of mixture weights converges to 1: $\sum_{k \in \mathbb{N}^+} \text{monotoneMixtureWeight}(P, k) = 1$ (HasSum).
3. For every $n \in \mathbb{N}^+$, the series $\sum_{k \in \mathbb{N}^+} (\text{if } n \le k \text{ then } \text{monotoneMixtureWeight}(P, k) / k \text{ else } 0)$ converges to $P(n)$ (HasSum).
4. For every $n \in \mathbb{N}^+$, the series $\sum_{k \in \mathbb{N}^+} \text{monotoneMixtureWeight}(P, k) \cdot \text{uniformDistribution}(k, n)$ converges to $P(n)$ (HasSum).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
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.
open Filteropen scoped Topologyprivate lemma mixture_representation_monotone_distribution_succPNat_add_one (m : ℕ) : Nat.succPNat m + 1 = Nat.succPNat (m + 1) := by apply PNat.coe_injective show ((Nat.succPNat m : ℕ+) : ℕ) + 1 = ((Nat.succPNat (m + 1) : ℕ+) : ℕ) simp [Nat.succPNat]private lemma mixture_representation_monotone_distribution_succPNat_val (m : ℕ) : ((Nat.succPNat m : ℕ+) : ℕ) = m + 1 := by simp [Nat.succPNat]private lemma mixture_representation_monotone_distribution_succPNat_val_real (m : ℕ) : ((Nat.succPNat m : ℕ+) : ℝ) = (m : ℝ) + 1 := by have h := mixture_representation_monotone_distribution_succPNat_val m push_cast [h] ringprivate lemma mixture_representation_monotone_distribution_succPNat_natPred (n : ℕ+) : Nat.succPNat ((n : ℕ) - 1) = n := by apply PNat.coe_injective show ((Nat.succPNat ((n : ℕ) - 1) : ℕ+) : ℕ) = (n : ℕ) rw [mixture_representation_monotone_distribution_succPNat_val] have := n.pos omegaprivate lemma mixture_representation_monotone_distribution_pnat_hassum_iff {a : ℕ+ → ℝ} {s : ℝ} : HasSum a s ↔ HasSum (fun m : ℕ => a (Nat.succPNat m)) s := by have h := Equiv.hasSum_iff (Equiv.pnatEquivNat.symm) (f := a) (a := s) have he : (a ∘ ⇑(Equiv.pnatEquivNat.symm)) = fun m : ℕ => a (Nat.succPNat m) := by funext m; simp rw [he] at h exact h.symmprivate lemma mixture_representation_monotone_distribution_monotone_succPNat : Monotone (Nat.succPNat : ℕ → ℕ+) := by intro a b hab refine (PNat.coe_le_coe _ _).mp ?_ rw [mixture_representation_monotone_distribution_succPNat_val, mixture_representation_monotone_distribution_succPNat_val] omegaprivate lemma mixture_representation_monotone_distribution_succPNat_le_iff (n : ℕ+) (m : ℕ) : n ≤ Nat.succPNat m ↔ (n : ℕ) - 1 ≤ m := by rw [← PNat.coe_le_coe, mixture_representation_monotone_distribution_succPNat_val] have := n.pos omegaprivate lemma mixture_representation_monotone_distribution_tail_tendsto (Q : ℕ → ℝ) (hsum : Summable Q) : Tendsto (fun N : ℕ => ∑' i : ℕ, Q (i + N)) atTop (𝓝 0) := by have heq : (fun N : ℕ => ∑' i : ℕ, Q (i + N)) = fun N => (∑' i : ℕ, Q i) - ∑ i ∈ Finset.range N, Q i := by funext N have h := hsum.sum_add_tsum_nat_add N linarith rw [heq] have hc : Tendsto (fun _ : ℕ => (∑' i : ℕ, Q i)) atTop (𝓝 (∑' i : ℕ, Q i)) := tendsto_const_nhds simpa using hc.sub hsum.tendsto_sum_tsum_natprivate lemma mixture_representation_monotone_distribution_block_le_tail (Q : ℕ → ℝ) (hnonneg : ∀ n, 0 ≤ Q n) (hanti : Antitone Q) (hsum : Summable Q) (n : ℕ) : (n : ℝ) * Q n ≤ 2 * (∑' i : ℕ, Q (i + n / 2)) := by set M := n / 2 with hM have hshift : Summable (fun i : ℕ => Q (i + M)) := (summable_nat_add_iff M).mpr hsum have step1 : (n : ℝ) * Q n ≤ 2 * (((n + 1 - M : ℕ)) : ℝ) * Q n := by have hnum : (n : ℝ) ≤ 2 * ((n + 1 - M : ℕ) : ℝ) := by have h : n ≤ 2 * (n + 1 - M) := by omega exact_mod_cast h have hQn : 0 ≤ Q n := hnonneg n nlinarith have step2 : (((n + 1 - M : ℕ)) : ℝ) * Q n ≤ ∑ j ∈ Finset.Icc M n, Q j := by have h1 : ∑ j ∈ Finset.Icc M n, Q n ≤ ∑ j ∈ Finset.Icc M n, Q j := by apply Finset.sum_le_sum intro j hj simp only [Finset.mem_Icc] at hj exact hanti hj.2 have h2 : ∑ j ∈ Finset.Icc M n, Q n = ((Finset.Icc M n).card : ℝ) * Q n := by rw [Finset.sum_const, nsmul_eq_mul] have hcard : (Finset.Icc M n).card = n + 1 - M := by simp rw [h2, hcard] at h1 exact h1 have step3 : ∑ j ∈ Finset.Icc M n, Q j ≤ ∑' i : ℕ, Q (i + M) := by rw [show Finset.Icc M n = Finset.Ico M (n + 1) from by ext x; simp] rw [Finset.sum_Ico_eq_sum_range] have : ∑ k ∈ Finset.range (n + 1 - M), Q (M + k) = ∑ k ∈ Finset.range (n + 1 - M), Q (k + M) := by apply Finset.sum_congr rfl intro k _; rw [Nat.add_comm] rw [this] exact hshift.sum_le_tsum _ (fun i _ => hnonneg _) calc (n : ℝ) * Q n ≤ 2 * (((n + 1 - M : ℕ)) : ℝ) * Q n := step1 _ ≤ 2 * (∑ j ∈ Finset.Icc M n, Q j) := by linarith _ ≤ 2 * (∑' i : ℕ, Q (i + M)) := by linarithprivate lemma mixture_representation_monotone_distribution_tendsto_nat_mul (Q : ℕ → ℝ) (hnonneg : ∀ n, 0 ≤ Q n) (hanti : Antitone Q) (hsum : Summable Q) : Tendsto (fun n : ℕ => (n : ℝ) * Q n) atTop (𝓝 0) := by have htail := mixture_representation_monotone_distribution_tail_tendsto Q hsum have hcomp : Tendsto (fun n : ℕ => n / 2) atTop atTop := Nat.tendsto_div_const_atTop (by norm_num) have hupper : Tendsto (fun n : ℕ => 2 * (∑' i : ℕ, Q (i + n / 2))) atTop (𝓝 0) := by simpa using (htail.comp hcomp).const_mul 2 apply squeeze_zero' _ _ hupper · filter_upwards with n exact mul_nonneg (Nat.cast_nonneg n) (hnonneg n) · filter_upwards with n using mixture_representation_monotone_distribution_block_le_tail Q hnonneg hanti hsum nprivate lemma mixture_representation_monotone_distribution_weight_sum_identity (Q : ℕ → ℝ) : ∀ N : ℕ, ∑ m ∈ Finset.range N, ((m : ℝ) + 1) * (Q m - Q (m + 1)) = ∑ m ∈ Finset.range N, Q m - (N : ℝ) * Q N := by intro N induction N with | zero => simp | succ N ih => rw [Finset.sum_range_succ, Finset.sum_range_succ, ih] push_cast ringprivate lemma mixture_representation_monotone_distribution_indicator_sum_identity (Q : ℕ → ℝ) {ñ N : ℕ} (h : ñ ≤ N) : ∑ m ∈ Finset.range N, (if ñ ≤ m then (Q m - Q (m + 1)) else 0) = Q ñ - Q N := by rw [← Finset.sum_filter] have hf : (Finset.range N).filter (fun m => ñ ≤ m) = Finset.Ico ñ N := by ext m simp only [Finset.mem_filter, Finset.mem_range, Finset.mem_Ico] omega rw [hf] have h2 : ∑ m ∈ Finset.Ico ñ N, (Q m - Q (m + 1)) = -(∑ m ∈ Finset.Ico ñ N, (Q (m + 1) - Q m)) := by rw [← Finset.sum_neg_distrib] exact Finset.sum_congr rfl (fun m _ => by ring) rw [h2, Finset.sum_Ico_sub Q h] ring/-- Mixture representation of monotone probability distributions on ℕ+ by uniform distributions. -/theorem mixture_representation_monotone_distribution (P : ℕ+ → ℝ) (h_nonneg : ∀ k : ℕ+, 0 ≤ P k) (h_anti : Antitone P) (h_sum : HasSum P 1) : (∀ k : ℕ+, 0 ≤ monotoneMixtureWeight P k) ∧ HasSum (monotoneMixtureWeight P) 1 ∧ (∀ n : ℕ+, HasSum (fun k : ℕ+ => if n ≤ k then monotoneMixtureWeight P k / (k : ℝ) else 0) (P n)) ∧ (∀ n : ℕ+, HasSum (fun k : ℕ+ => monotoneMixtureWeight P k * uniformDistribution k n) (P n)) := by set Q : ℕ → ℝ := fun m => P (Nat.succPNat m) with hQdef have hQnonneg : ∀ m, 0 ≤ Q m := fun m => h_nonneg _ have hQanti : Antitone Q := fun a b hab => h_anti (mixture_representation_monotone_distribution_monotone_succPNat hab) have hQhasSum : HasSum Q 1 := mixture_representation_monotone_distribution_pnat_hassum_iff.mp h_sum have hQsum : Summable Q := hQhasSum.summable have hw : ∀ m : ℕ, monotoneMixtureWeight P (Nat.succPNat m) = ((m : ℝ) + 1) * (Q m - Q (m + 1)) := by intro m simp only [monotoneMixtureWeight, hQdef] rw [mixture_representation_monotone_distribution_succPNat_val_real, mixture_representation_monotone_distribution_succPNat_add_one] have h2 : HasSum (monotoneMixtureWeight P) 1 := by refine mixture_representation_monotone_distribution_pnat_hassum_iff.mpr ?_ rw [hasSum_iff_tendsto_nat_of_nonneg (fun m => monotoneMixtureWeight_nonneg P h_anti _)] have hpartial : ∀ N : ℕ, ∑ m ∈ Finset.range N, monotoneMixtureWeight P (Nat.succPNat m) = ∑ m ∈ Finset.range N, Q m - (N : ℝ) * Q N := by intro N rw [← mixture_representation_monotone_distribution_weight_sum_identity Q N] exact Finset.sum_congr rfl (fun m _ => hw m) rw [show (fun N : ℕ => ∑ m ∈ Finset.range N, monotoneMixtureWeight P (Nat.succPNat m)) = fun N => ∑ m ∈ Finset.range N, Q m - (N : ℝ) * Q N from funext hpartial] have htend : Tendsto (fun N : ℕ => ∑ m ∈ Finset.range N, Q m - (N : ℝ) * Q N) atTop (𝓝 (1 - 0)) := hQhasSum.tendsto_sum_nat.sub (mixture_representation_monotone_distribution_tendsto_nat_mul Q hQnonneg hQanti hQsum) simpa using htend have h3 : ∀ n : ℕ+, HasSum (fun k : ℕ+ => if n ≤ k then monotoneMixtureWeight P k / (k : ℝ) else 0) (P n) := by intro n refine mixture_representation_monotone_distribution_pnat_hassum_iff.mpr ?_ set ñ := (n : ℕ) - 1 with hñ have hnn : Nat.succPNat ñ = n := mixture_representation_monotone_distribution_succPNat_natPred n have hpn : Q ñ = P n := by simp [hQdef, hnn] have hle : ∀ m : ℕ, (n ≤ Nat.succPNat m) ↔ (ñ ≤ m) := by intro m rw [← hnn] exact mixture_representation_monotone_distribution_succPNat_le_iff (Nat.succPNat ñ) m have hfun : (fun m : ℕ => (if n ≤ Nat.succPNat m then monotoneMixtureWeight P (Nat.succPNat m) / ((Nat.succPNat m : ℕ+) : ℝ) else 0)) = fun m : ℕ => if ñ ≤ m then (Q m - Q (m + 1)) else 0 := by funext m by_cases h : ñ ≤ m · rw [if_pos (hle m |>.mpr h), if_pos h] have hpos : ((m : ℝ) + 1) ≠ 0 := by positivity rw [hw m, mixture_representation_monotone_distribution_succPNat_val_real, mul_div_cancel_left₀ _ hpos] · rw [if_neg (fun hc => h ((hle m).mp hc)), if_neg h] rw [hfun] rw [hasSum_iff_tendsto_nat_of_nonneg] · have hlim : Tendsto (fun N : ℕ => Q ñ - Q N) atTop (𝓝 (Q ñ)) := by have h := (tendsto_const_nhds (x := Q ñ) (f := (atTop : Filter ℕ))).sub hQsum.tendsto_atTop_zero simpa using h have hev : (fun N : ℕ => ∑ m ∈ Finset.range N, (if ñ ≤ m then (Q m - Q (m + 1)) else 0)) =ᶠ[atTop] fun N => Q ñ - Q N := by filter_upwards [eventually_ge_atTop ñ] with N hN exact mixture_representation_monotone_distribution_indicator_sum_identity Q hN have hres := Tendsto.congr' hev.symm hlim rw [← hpn] exact hres · intro m by_cases h : ñ ≤ m · rw [if_pos h] exact sub_nonneg.mpr (hQanti (Nat.le_succ m)) · rw [if_neg h] refine ⟨fun k => monotoneMixtureWeight_nonneg P h_anti k, h2, h3, ?_⟩ intro n have hpt : (fun k : ℕ+ => monotoneMixtureWeight P k * uniformDistribution k n) = fun k : ℕ+ => if n ≤ k then monotoneMixtureWeight P k / (k : ℝ) else 0 := by funext k by_cases h : n ≤ k <;> simp [uniformDistribution, h, div_eq_mul_inv] rw [hpt] exact h3 n