AFTD Auto-Formalizing Theoretical Domains

bivariate_poisson_pmf_le_one

theoremverified

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.

  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.

    lines 3–7

    uses Nat.succ_le_of_lt, div_le_self

      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) hden
  2. 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.

    lines 11–16

    uses Finset.sum_range_succ

      induction n with
      | zero =>
        norm_num
      | succ n ih =>
        rw [Finset.sum_range_succ, ih]
        ring
  3. 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.

    lines 20–22

    uses Finset.sum_range_reflect, Nat.add_sub_cancel_right

      have h := Finset.sum_range_reflect (fun i => (1 / 2 : ℝ) ^ i) (n + 1)
      simp only [Nat.add_sub_cancel_right] at h
      exact h
  4. 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.

    line 25

    uses pow_le_one₀

      pow_le_one₀ (by norm_num) (by norm_num)
  5. 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.

    lines 28–29

    uses pow_succ

      rw [pow_succ]
      ring
  6. 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.

    lines 32–46

    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_two

      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)
  7. 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.

    lines 50–63

    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_product

      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
  8. 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.

    lines 67–84

    uses bivariate_poisson_pmf_term_le_pow, Finset.sum_le_sum, bivariate_poisson_pmf_sum_pow_half, Real.exp_le_one_iff

      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

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

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
See it in the graphDiscuss this resultChallenge it