bivariate_poisson_pmf_le_one
For any natural numbers a and b, bivariate_poisson_pmf a b ≤ 1.
Statement
theorem bivariate_poisson_pmf_le_one (a b : ℕ) : bivariate_poisson_pmf a b ≤ 1- Source
- step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- bivariate_poisson_pmfThe bivariate Poisson probability mass function bivariate_poisson_pmf a b is defined by Real.exp (-(3/2)) * ∑ j ∈ Finset.range (min a b +…
The proof, explained
The proof bounds the bivariate Poisson probability mass function by 1 by splitting it into the product of exp(-3/2) and a finite sum. Each term in the sum is bounded above by omitting the factorials in the denominator, reducing the sum to a geometric progression that evaluates to (1/2)^(a+b-min(a,b)) * (2 - (1/2)^(min(a,b))) ≤ 1. Since exp(-3/2) ≤ 1 and both factors are non-negative, the product is at most 1.
The denominator is at least 1, so dividing the power by it does not increase the value.
The product of factorials is strictly positive, hence at least 1. Dividing a non-negative real by a number at least 1 is bounded by the numerator itself.
uses
Nat.succ_le_of_lt,div_le_selfhave hpos : 0 < j.factorial * (a - j).factorial * (b - j).factorial := by positivity have hden : (1 : ℝ) ≤ ↑(j.factorial * (a - j).factorial * (b - j).factorial) := by exact_mod_cast Nat.succ_le_of_lt hpos push_cast at hden exact div_le_self (by positivity) hden
The finite geometric sum of powers of 1/2 equals 2 minus (1/2)^n.
By induction on n: for n = 0 it is 1 = 2 - 1, and the inductive step follows by separating the last term and simplifying algebraically.
uses
Finset.sum_range_succinduction n with | zero => norm_num | succ n ih => rw [Finset.sum_range_succ, ih] ring
Reversing the order of summation preserves the sum.
Applying Finset.sum_range_reflect reverses the index range from n down to 0, which leaves the sum over powers of 1/2 unchanged.
uses
Finset.sum_range_reflect,Nat.add_sub_cancel_righthave h := Finset.sum_range_reflect (fun i => (1 / 2 : ℝ) ^ i) (n + 1) simp only [Nat.add_sub_cancel_right] at h exact h
Powers of 1/2 are at most 1.
Since 1/2 is non-negative and at most 1, its powers are bounded above by 1.
uses
pow_le_one₀pow_le_one₀ (by norm_num) (by norm_num)
Multiplying (1/2)^(k+1) by 2 gives (1/2)^k.
Factoring (1/2)^(k+1) into (1/2)^k * (1/2) and multiplying by 2 simplifies directly.
uses
pow_succrw [pow_succ] ring
For n ≤ M, the product (1/2)^M * (2 - (1/2)^n) is at most 1.
If n = 0, the second factor is 1 and (1/2)^M ≤ 1. If n > 0, then M > 0 as well, so write M = k + 1; then 2 - (1/2)^n ≤ 2, so the product is at most (1/2)^(k+1) * 2 = (1/2)^k ≤ 1.
uses
pow_zero,mul_one,bivariate_poisson_pmf_pow_half_le_one,Nat.exists_eq_succ_of_ne_zero,bivariate_poisson_pmf_pow_succ_mul_tworcases n with _ | n' · simp only [pow_zero] have : (2 : ℝ) - 1 = 1 := by norm_num rw [this, mul_one] exact bivariate_poisson_pmf_pow_half_le_one M · have hM : M ≠ 0 := by omega obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hM have h1 : 2 - (1 / 2 : ℝ) ^ (n' + 1) ≤ 2 := by have : 0 ≤ (1 / 2 : ℝ) ^ (n' + 1) := by positivity linarith have h2 : (1 / 2 : ℝ) ^ (k + 1) * (2 - (1 / 2 : ℝ) ^ (n' + 1)) ≤ (1 / 2 : ℝ) ^ (k + 1) * 2 := by have : 0 ≤ (1 / 2 : ℝ) ^ (k + 1) := by positivity nlinarith rw [bivariate_poisson_pmf_pow_succ_mul_two] at h2 exact h2.trans (bivariate_poisson_pmf_pow_half_le_one k)
The sum of powers (1/2)^(a+b-j) up to min(a,b) is at most 1.
Setting n = min(a,b) and M = a+b-n, each exponent a+b-j splits as M + (n-j). Factoring out (1/2)^M, reversing the sum, and evaluating the geometric series reduces the bound to the previous product lemma.
uses
pow_add,Finset.sum_congr,Finset.mul_sum,bivariate_poisson_pmf_sum_reflect_half,bivariate_poisson_pmf_geom_sum_half,bivariate_poisson_pmf_bound_productset n := min a b set M := a + b - n have hnM : n ≤ M := by omega have hsplit : ∀ j ∈ Finset.range (n + 1), a + b - j = M + (n - j) := by intro j hj have : j ≤ n := Nat.lt_succ_iff.mp (Finset.mem_range.mp hj) omega have hterm : ∀ j ∈ Finset.range (n + 1), (1 / 2 : ℝ) ^ (a + b - j) = (1 / 2 : ℝ) ^ M * (1 / 2 : ℝ) ^ (n - j) := by intro j hj rw [hsplit j hj, pow_add] rw [Finset.sum_congr rfl hterm, ← Finset.mul_sum, bivariate_poisson_pmf_sum_reflect_half, bivariate_poisson_pmf_geom_sum_half] exact bivariate_poisson_pmf_bound_product M n hnM
The bivariate Poisson PMF is at most 1.
Unfolding the definition, each term in the sum is bounded by omitting the factorial denominator. The resulting sum of powers is at most 1, and exp(-3/2) ≤ 1, so the non-negative product is at most 1.
uses
bivariate_poisson_pmf_term_le_pow,Finset.sum_le_sum,bivariate_poisson_pmf_sum_pow_half,Real.exp_le_one_iffunfold bivariate_poisson_pmf have hle : ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) ≤ ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) := by apply Finset.sum_le_sum intro j _ exact bivariate_poisson_pmf_term_le_pow a b j have hsum_le : ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) ≤ 1 := hle.trans (bivariate_poisson_pmf_sum_pow_half a b) have hexp_le : Real.exp (-(3 / 2 : ℝ)) ≤ 1 := by rw [Real.exp_le_one_iff] norm_num have hexp_pos : 0 ≤ Real.exp (-(3 / 2 : ℝ)) := by positivity have hsum_nonneg : 0 ≤ ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) := by positivity nlinarith
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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 bivariate_poisson_pmf_term_le_pow (a b j : ℕ) : (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) ≤ (1 / 2 : ℝ) ^ (a + b - j) := by have hpos : 0 < j.factorial * (a - j).factorial * (b - j).factorial := by positivity have hden : (1 : ℝ) ≤ ↑(j.factorial * (a - j).factorial * (b - j).factorial) := by exact_mod_cast Nat.succ_le_of_lt hpos push_cast at hden exact div_le_self (by positivity) hdenlemma bivariate_poisson_pmf_geom_sum_half (n : ℕ) : ∑ i ∈ Finset.range (n + 1), (1 / 2 : ℝ) ^ i = 2 - (1 / 2 : ℝ) ^ n := by induction n with | zero => norm_num | succ n ih => rw [Finset.sum_range_succ, ih] ringlemma bivariate_poisson_pmf_sum_reflect_half (n : ℕ) : ∑ j ∈ Finset.range (n + 1), (1 / 2 : ℝ) ^ (n - j) = ∑ j ∈ Finset.range (n + 1), (1 / 2 : ℝ) ^ j := by have h := Finset.sum_range_reflect (fun i => (1 / 2 : ℝ) ^ i) (n + 1) simp only [Nat.add_sub_cancel_right] at h exact hlemma bivariate_poisson_pmf_pow_half_le_one (k : ℕ) : (1 / 2 : ℝ) ^ k ≤ 1 := pow_le_one₀ (by norm_num) (by norm_num)lemma bivariate_poisson_pmf_pow_succ_mul_two (k : ℕ) : (1 / 2 : ℝ) ^ (k + 1) * 2 = (1 / 2 : ℝ) ^ k := by rw [pow_succ] ringlemma bivariate_poisson_pmf_bound_product (M n : ℕ) (h : n ≤ M) : (1 / 2 : ℝ) ^ M * (2 - (1 / 2 : ℝ) ^ n) ≤ 1 := by rcases n with _ | n' · simp only [pow_zero] have : (2 : ℝ) - 1 = 1 := by norm_num rw [this, mul_one] exact bivariate_poisson_pmf_pow_half_le_one M · have hM : M ≠ 0 := by omega obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hM have h1 : 2 - (1 / 2 : ℝ) ^ (n' + 1) ≤ 2 := by have : 0 ≤ (1 / 2 : ℝ) ^ (n' + 1) := by positivity linarith have h2 : (1 / 2 : ℝ) ^ (k + 1) * (2 - (1 / 2 : ℝ) ^ (n' + 1)) ≤ (1 / 2 : ℝ) ^ (k + 1) * 2 := by have : 0 ≤ (1 / 2 : ℝ) ^ (k + 1) := by positivity nlinarith rw [bivariate_poisson_pmf_pow_succ_mul_two] at h2 exact h2.trans (bivariate_poisson_pmf_pow_half_le_one k)lemma bivariate_poisson_pmf_sum_pow_half (a b : ℕ) : ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) ≤ 1 := by set n := min a b set M := a + b - n have hnM : n ≤ M := by omega have hsplit : ∀ j ∈ Finset.range (n + 1), a + b - j = M + (n - j) := by intro j hj have : j ≤ n := Nat.lt_succ_iff.mp (Finset.mem_range.mp hj) omega have hterm : ∀ j ∈ Finset.range (n + 1), (1 / 2 : ℝ) ^ (a + b - j) = (1 / 2 : ℝ) ^ M * (1 / 2 : ℝ) ^ (n - j) := by intro j hj rw [hsplit j hj, pow_add] rw [Finset.sum_congr rfl hterm, ← Finset.mul_sum, bivariate_poisson_pmf_sum_reflect_half, bivariate_poisson_pmf_geom_sum_half] exact bivariate_poisson_pmf_bound_product M n hnM/-- Upper bound of 1 on bivariate Poisson probability mass function. -/theorem bivariate_poisson_pmf_le_one (a b : ℕ) : bivariate_poisson_pmf a b ≤ 1 := by unfold bivariate_poisson_pmf have hle : ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) ≤ ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) := by apply Finset.sum_le_sum intro j _ exact bivariate_poisson_pmf_term_le_pow a b j have hsum_le : ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) ≤ 1 := hle.trans (bivariate_poisson_pmf_sum_pow_half a b) have hexp_le : Real.exp (-(3 / 2 : ℝ)) ≤ 1 := by rw [Real.exp_le_one_iff] norm_num have hexp_pos : 0 ≤ Real.exp (-(3 / 2 : ℝ)) := by positivity have hsum_nonneg : 0 ≤ ∑ j ∈ Finset.range (min a b + 1), (1 / 2 : ℝ) ^ (a + b - j) / (↑j.factorial * ↑(a - j).factorial * ↑(b - j).factorial) := by positivity nlinarith