Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ToMathlib.Probability.ProbabilityMassFunction.RenyiDivergence.part0

Definition
Yukon_f588a8e35720876de725963a

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-codes

Source module ToMathlib.Probability.ProbabilityMassFunction.RenyiDivergence.

Definition code
/-
Copyright (c) 2026 Quang Dao. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao
-/

module
public import Mathlib.Probability.ProbabilityMassFunction.Constructions
public import Mathlib.Analysis.SpecialFunctions.Pow.NNReal
public import Definitions.Def_Yukon_8321510fb5e60b1f0f309da5

public import Definitions.Def_Yukon_65a3e7bccec6dd2d9b06d366



public import Mathlib.Topology.Algebra.InfiniteSum.ENNReal
public import Init
public import Mathlib.Probability.ProbabilityMassFunction.Monad
public import Mathlib.MeasureTheory.Integral.Lebesgue.Countable
public import Mathlib.MeasureTheory.Integral.MeanInequalities
meta import Definitions.Def_Yukon_8321510fb5e60b1f0f309da5
meta import Definitions.Def_Yukon_65a3e7bccec6dd2d9b06d366
set_option backward.isDefEq.respectTransparency.types false
/-!
# Rényi Divergence for PMFs

This file defines Rényi divergence on probability mass functions, following the
multiplicative convention `R_α(p ‖ q) = (∑ x, p(x)^α · q(x)^(1-α))^(1/(α-1))` used
in the lattice cryptography literature (Falcon, GPV, etc.).

We also define the max-divergence (Rényi divergence of order `∞`) as `⨆ x, p(x) / q(x)`.

## Main Definitions

- `PMF.renyiMGF a p q : ℝ≥0∞` — the Rényi moment generating function (the base quantity
  before exponentiation): `∑ x, p(x)^a * q(x)^(1-a)`
- `PMF.renyiDiv a p q : ℝ≥0∞` — the multiplicative Rényi divergence of order `a > 1`:
  `(renyiMGF a p q)^(1/(a-1))`
- `PMF.maxDiv p q : ℝ≥0∞` — the max-divergence (order `∞`): `⨆ x, p(x) / q(x)`

## Main Results

- `renyiMGF_self` — `M_a(p ‖ p) = 1`
- `renyiDiv_self` — `R_a(p ‖ p) = 1`
- `renyiMGF_map_le` — data processing inequality for deterministic maps
- `renyiDiv_map_le` — data processing inequality for Rényi divergence
- `renyiDiv_prob_bound` — probability preservation bound

## Design Notes

We use `ℝ≥0∞` throughout rather than `ℝ` to avoid partiality issues (Rényi divergence can
be infinite when `q` has zeros that `p` doesn't). The multiplicative form (not the log form)
is used because:

1. The Falcon literature uses `R_α` (multiplicative), not `D_α` (log form).
2. Multiplicative form composes better: `R_α(p₁⊗p₂ ‖ q₁⊗q₂) = R_α(p₁‖q₁) · R_α(p₂‖q₂)`.
3. The probability preservation bound is cleaner: `q(E) ≥ p(E)^{α/(α-1)} / R_α(p‖q)`.

## References

- Rényi, A. "On measures of entropy and information." 1961.
- van Erven, T., Harremoës, P. "Rényi divergence and Kullback-Leibler divergence." 2014.
- Bai, S., et al. "An Improved Compression Technique for Signatures Based on Learning
  with Errors." 2014. (multiplicative convention for lattice crypto)
- Fouque, P.-A., et al. "A closer look at Falcon." ePrint 2024/1769.
-/

@[expose] public section


noncomputable section

open ENNReal

namespace PMF

variable {α : Type*}

/-! ### Rényi Moment Generating Function -/

/-- The Rényi moment generating function of order `a ∈ ℝ` between two PMFs:
`M_a(p ‖ q) = ∑ x, p(x)^a * q(x)^(1-a)`.
This is the base quantity whose `1/(a-1)` power gives the multiplicative Rényi divergence. -/
protected def renyiMGF (a : ℝ) (p q : PMF α) : ℝ≥0∞ :=
  ∑' x, (p x) ^ a * (q x) ^ (1 - a)

@[simp]
theorem renyiMGF_self (a : ℝ) (p : PMF α) : p.renyiMGF a p = 1 := by
  simp only [PMF.renyiMGF]
  have h : ∀ x, (p x) ^ a * (p x) ^ (1 - a) = p x := fun x => by
    by_cases hx : p x = 0
    · by_cases ha : 0 < a
      · simp [hx, ENNReal.zero_rpow_of_pos ha]
      · push Not at ha
        have h1a : 0 < 1 - a := by linarith
        simp [hx, ENNReal.zero_rpow_of_pos h1a]
    · rw [← ENNReal.rpow_add a (1 - a) hx (PMF.apply_ne_top p x),
        show a + (1 - a) = 1 from by ring, ENNReal.rpow_one]
  simp [h, p.tsum_coe]

/-! ### Multiplicative Rényi Divergence -/

/-- The multiplicative Rényi divergence of order `a > 1` between two PMFs:
`R_a(p ‖ q) = M_a(p ‖ q)^(1/(a-1))`.

When `a ≤ 1`, this returns `1` (the trivial bound). -/
protected def renyiDiv (a : ℝ) (p q : PMF α) : ℝ≥0∞ :=
  if a ≤ 1 then 1 else (p.renyiMGF a q) ^ ((a - 1)⁻¹ : ℝ)

@[simp]
theorem renyiDiv_self (a : ℝ) (p : PMF α) : p.renyiDiv a p = 1 := by
  unfold PMF.renyiDiv
  split
  · rfl
  · simp

theorem renyiDiv_eq_rpow {a : ℝ} (ha : 1 < a) (p q : PMF α) :
    p.renyiDiv a q = (p.renyiMGF a q) ^ ((a - 1)⁻¹ : ℝ) := by
  simp [PMF.renyiDiv, not_le.mpr ha]

/-! ### Max-Divergence (Rényi order ∞) -/

/-- The max-divergence (Rényi divergence of order `∞`): `⨆ x, p(x) / q(x)`.
This bounds the pointwise likelihood ratio. -/
protected def maxDiv (p q : PMF α) : ℝ≥0∞ := ⨆ x, p x / q x

@[simp]
theorem maxDiv_self (p : PMF α) : p.maxDiv p = 1 := by
  apply le_antisymm
  · exact iSup_le fun x => ENNReal.div_self_le_one
  · obtain ⟨x, hx⟩ := p.support_nonempty
    exact le_iSup_of_le x ((ENNReal.div_self hx (PMF.apply_ne_top p x)).ge)

theorem maxDiv_one_le (p q : PMF α) :
    1 ≤ p.maxDiv q := by
  by_cases hq : ∀ x, p x ≠ 0 → q x ≠ 0
  · unfold PMF.maxDiv
    calc (1 : ℝ≥0∞) = ∑' x, p x := p.tsum_coe.symm
      _ = ∑' x, (p x / q x) * q x := by
          congr 1; ext x
          by_cases hpx : p x = 0
          · simp [hpx]
          · rw [ENNReal.div_mul_cancel (hq x hpx) (PMF.apply_ne_top q x)]
      _ ≤ ∑' x, (⨆ y, p y / q y) * q x :=
          ENNReal.tsum_le_tsum fun x => by
            gcongr; exact le_iSup (fun y => p y / q y) x
      _ = (⨆ y, p y / q y) * ∑' x, q x := ENNReal.tsum_mul_left
      _ = ⨆ y, p y / q y := by rw [q.tsum_coe, mul_one]
  · simp only [not_forall] at hq
    rcases hq with ⟨x, hpx, hqx⟩
    have hqx0 : q x = 0 := by simpa using hqx
    calc
      (1 : ℝ≥0∞) ≤ p x / q x := by
        rw [hqx0, ENNReal.div_zero hpx]
        simp
      _ ≤ p.maxDiv q := by
        unfold PMF.maxDiv
        exact le_iSup (fun y => p y / q y) x

/-! ### Data Processing Inequality -/

section DataProcessing

universe u₀
variable {α' : Type u₀} {β : Type u₀}

/-- Data processing inequality for the Rényi MGF under deterministic maps:
`M_a(f∗p ‖ f∗q) ≤ M_a(p ‖ q)`.
Applying a deterministic function can only decrease the Rényi MGF. -/
theorem renyiMGF_map_le (a : ℝ) (ha : 1 ≤ a) (f : α' → β) (p q : PMF α') :
    (f <$> p).renyiMGF a (f <$> q) ≤ p.renyiMGF a q := by
  rcases eq_or_lt_of_le ha with rfl | ha'
  · simp only [PMF.renyiMGF, sub_self, ENNReal.rpow_zero, mul_one, ENNReal.rpow_one]
    rw [(f <$> p).tsum_coe, p.tsum_coe]
  · classical
    have ha0 : (0 : ℝ) < a := lt_trans zero_lt_one ha'
    have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha'
    have h1a : (1 : ℝ) - a < 0 := by linarith
    have hconj : a.HolderConjugate (a / (a - 1)) := Real.HolderConjugate.conjExponent ha'
    have hainv : a⁻¹ * a = (1 : ℝ) := inv_mul_cancel₀ ha0.ne'
    have hainv' : a * a⁻¹ = (1 : ℝ) := mul_inv_cancel₀ ha0.ne'
    have hsinv : (a - 1) / a * (a / (a - 1)) = (1 : ℝ) := by field_simp
    simp only [PMF.renyiMGF, PMF.monad_map_eq_map, PMF.map_apply]
    have sum_rearr : ∑' x, (p x) ^ a * (q x) ^ (1 - a) =
        ∑' y, ∑' x, if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0 := by
      trans ∑' x, ∑' y, if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0
      · exact tsum_congr fun x =>
          (tsum_ite_eq (f x) (fun _ => (p x) ^ a * (q x) ^ (1 - a))).symm
      · exact ENNReal.tsum_comm
    rw [sum_rearr]
    apply ENNReal.tsum_le_tsum
    intro y
    set P : α' → ℝ≥0∞ := fun x => if y = f x then p x else 0
    set Q : α' → ℝ≥0∞ := fun x => if y = f x then q x else 0
    change (∑' x, P x) ^ a * (∑' x, Q x) ^ (1 - a) ≤
      ∑' x, if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0
    have hif : ∀ x, P x ^ a * Q x ^ (1 - a) =
        if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0 := by
      intro x; simp only [P, Q]
      split_ifs with h
      · rfl
      · simp [ENNReal.zero_rpow_of_pos ha0]
    by_cases hac : ∀ x, P x ≠ 0 → Q x ≠ 0
    · by_cases hPsum : ∑' x, P x = 0
      · simp [hPsum, ENNReal.zero_rpow_of_pos ha0]
      · have hQne : ∑' x, Q x ≠ 0 := by
          intro hQsum0
          exact hPsum (ENNReal.tsum_eq_zero.mpr fun x => by
            by_cases hPx : P x = 0
            · exact hPx
            · exact absurd (ENNReal.tsum_eq_zero.mp hQsum0 x) (hac x hPx))
        have hQlt : ∑' x, Q x ≠ ⊤ :=
          ne_top_of_le_ne_top (by rw [q.tsum_coe]; exact one_ne_top)
            (ENNReal.tsum_le_tsum fun x => by
              simp only [Q]; split_ifs <;> [exact le_rfl; exact zero_le])
        have hpw : ∀ x, ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) *
            (Q x) ^ ((a - 1) / a : ℝ) = P x := by
          intro x
          by_cases hPx : P x = 0
          · simp [hPx, ENNReal.zero_rpow_of_pos ha0,
              ENNReal.zero_rpow_of_pos (inv_pos.mpr ha0)]
          · have hQx : Q x ≠ 0 := hac x hPx
            have hyfx : y = f x := by by_contra h; exact hPx (if_neg h)
            have hPt : P x ≠ ⊤ := by
              change (if y = f x then p x else 0) ≠ ⊤
              rw [if_pos hyfx]; exact PMF.apply_ne_top p _
            have hQt : Q x ≠ ⊤ := by
              change (if y = f x then q x else 0) ≠ ⊤
              rw [if_pos hyfx]; exact PMF.apply_ne_top q _
            rw [ENNReal.mul_rpow_of_ne_top
                  (ENNReal.rpow_ne_top_of_nonneg ha0.le hPt)
                  (ENNReal.rpow_ne_top_of_ne_zero hQx hQt),
                ← ENNReal.rpow_mul, ← ENNReal.rpow_mul, hainv', ENNReal.rpow_one, mul_assoc,
                ← ENNReal.rpow_add ((1 - a) * a⁻¹) ((a - 1) / a) hQx hQt,
                show (1 - a) * a⁻¹ + (a - 1) / a = (0 : ℝ) from by field_simp; ring,
                ENNReal.rpow_zero, mul_one]
        have hholder : ∑' x, P x ≤
            (∑' x, P x ^ a * Q x ^ (1 - a)) ^ (a⁻¹ : ℝ) *
            (∑' x, Q x) ^ ((a - 1) / a : ℝ) := by
          have hH := ENNReal.inner_le_Lp_mul_Lq_tsum hconj
            (fun x => ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ))
            (fun x => (Q x) ^ ((a - 1) / a : ℝ))
          rw [show ∑' x, ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) *
                (Q x) ^ ((a - 1) / a : ℝ) = ∑' x, P x from tsum_congr hpw] at hH
          refine le_trans hH (mul_le_mul' ?_ (le_of_eq ?_))
          · rw [one_div]
            apply ENNReal.rpow_le_rpow _ (inv_nonneg.mpr ha0.le)
            exact ENNReal.tsum_le_tsum fun x => le_of_eq (by
              rw [← ENNReal.rpow_mul, hainv, ENNReal.rpow_one])
          · congr 1
            · exact tsum_congr fun x => by rw [← ENNReal.rpow_mul, hsinv, ENNReal.rpow_one]
            · rw [one_div, inv_div]
        have hpow : (∑' x, P x) ^ a ≤
            (∑' x, P x ^ a * Q x ^ (1 - a)) * (∑' x, Q x) ^ (a - 1 : ℝ) := by
          have := ENNReal.rpow_le_rpow hholder ha0.le
          rwa [ENNReal.mul_rpow_of_nonneg _ _ ha0.le, ← ENNReal.rpow_mul, ← ENNReal.rpow_mul,
            hainv, ENNReal.rpow_one,
            show (a - 1) / a * a = a - 1 from by field_simp] at this
        calc (∑' x, P x) ^ a * (∑' x, Q x) ^ (1 - a)
            ≤ (∑' x, P x ^ a * Q x ^ (1 - a)) * (∑' x, Q x) ^ (a - 1) *
              (∑' x, Q x) ^ (1 - a) := mul_le_mul_left hpow _
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              ((∑' x, Q x) ^ (a - 1) * (∑' x, Q x) ^ (1 - a)) := mul_assoc _ _ _
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              (∑' x, Q x) ^ ((a - 1) + (1 - a)) := by
              congr 1; exact (ENNReal.rpow_add _ _ hQne hQlt).symm
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              (∑' x, Q x) ^ (0 : ℝ) := by congr 2; ring
          _ = ∑' x, P x ^ a * Q x ^ (1 - a) := by rw [ENNReal.rpow_zero, mul_one]
          _ = ∑' x, if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0 := tsum_congr hif
    · push Not at hac
      obtain ⟨x₀, hPx₀, hQx₀⟩ := hac
      have hyfx₀ : y = f x₀ := by by_contra h; exact hPx₀ (if_neg h)
      have hpx₀ : p x₀ ≠ 0 := by
        simp only [P, if_pos hyfx₀] at hPx₀; exact hPx₀
      have hqx₀ : q x₀ = 0 := by simp only [Q, if_pos hyfx₀] at hQx₀; exact hQx₀
      suffices h : (∑' x, if y = f x then (p x) ^ a * (q x) ^ (1 - a) else 0) = ⊤ from
        h ▸ le_top
      apply ENNReal.tsum_eq_top_of_eq_top ⟨x₀, ?_⟩
      rw [if_pos hyfx₀, hqx₀]
      have h0top : (0 : ℝ≥0∞) ^ (1 - a) = ⊤ :=
        ENNReal.rpow_eq_top_iff.mpr (Or.inl ⟨rfl, h1a⟩)
      rw [h0top]
      have hpa_pos : 0 < (p x₀) ^ a :=
        ENNReal.rpow_pos (pos_iff_ne_zero.mpr hpx₀) (PMF.apply_ne_top p x₀)
      exact mul_eq_top.mpr (Or.inl ⟨hpa_pos.ne', rfl⟩)

/-- Data processing inequality for the multiplicative Rényi divergence:
`R_a(f∗p ‖ f∗q) ≤ R_a(p ‖ q)`. -/
theorem renyiDiv_map_le (a : ℝ) (ha : 1 < a) (f : α' → β) (p q : PMF α') :
    (f <$> p).renyiDiv a (f <$> q) ≤ p.renyiDiv a q := by
  simp only [renyiDiv_eq_rpow ha]
  exact ENNReal.rpow_le_rpow (renyiMGF_map_le a ha.le f p q)
    (inv_nonneg.mpr (sub_nonneg.mpr ha.le))

/-- Data processing inequality for the Rényi MGF under Markov kernels (post-processing). -/
theorem renyiMGF_bind_right_le (a : ℝ) (ha : 1 ≤ a) (f : α' → PMF β) (p q : PMF α') :
    (p.bind f).renyiMGF a (q.bind f) ≤ p.renyiMGF a q := by
  rcases eq_or_lt_of_le ha with rfl | ha'
  · simp only [PMF.renyiMGF, sub_self, ENNReal.rpow_zero, mul_one, ENNReal.rpow_one]
    rw [(p.bind f).tsum_coe, p.tsum_coe]
  · classical
    have ha0 : (0 : ℝ) < a := lt_trans zero_lt_one ha'
    have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha'
    have h1a : (1 : ℝ) - a < 0 := by linarith
    have hconj : a.HolderConjugate (a / (a - 1)) := Real.HolderConjugate.conjExponent ha'
    have hainv : a⁻¹ * a = (1 : ℝ) := inv_mul_cancel₀ ha0.ne'
    have hainv' : a * a⁻¹ = (1 : ℝ) := mul_inv_cancel₀ ha0.ne'
    have hsinv : (a - 1) / a * (a / (a - 1)) = (1 : ℝ) := by field_simp
    simp only [PMF.renyiMGF, PMF.bind_apply]
    have hfactor : ∀ (x : α') (y : β),
        (p x * (f x) y) ^ a * (q x * (f x) y) ^ (1 - a) =
        p x ^ a * q x ^ (1 - a) * (f x) y := by
      intro x y
      by_cases hfxy : (f x) y = 0
      · simp only [hfxy, mul_zero, ENNReal.zero_rpow_of_pos ha0, zero_mul, mul_zero]
      · rw [ENNReal.mul_rpow_of_ne_top (PMF.apply_ne_top p x) (PMF.apply_ne_top (f x) y),
            ENNReal.mul_rpow_of_ne_top (PMF.apply_ne_top q x) (PMF.apply_ne_top (f x) y),
            mul_mul_mul_comm,
            ← ENNReal.rpow_add a (1 - a) hfxy (PMF.apply_ne_top (f x) y),
            show a + (1 - a) = (1 : ℝ) from by ring, ENNReal.rpow_one]
    suffices per_fiber : ∀ y, (∑' x, p x * (f x) y) ^ a *
        (∑' x, q x * (f x) y) ^ (1 - a) ≤
        ∑' x, (p x * (f x) y) ^ a * (q x * (f x) y) ^ (1 - a) from
      calc ∑' y, (∑' x, p x * (f x) y) ^ a * (∑' x, q x * (f x) y) ^ (1 - a)
          ≤ ∑' y, ∑' x, (p x * (f x) y) ^ a * (q x * (f x) y) ^ (1 - a) :=
              ENNReal.tsum_le_tsum per_fiber
        _ = ∑' y, ∑' x, p x ^ a * q x ^ (1 - a) * (f x) y := by
            congr 1; ext y; congr 1; ext x; exact hfactor x y
        _ = ∑' x, ∑' y, p x ^ a * q x ^ (1 - a) * (f x) y := ENNReal.tsum_comm
        _ = ∑' x, p x ^ a * q x ^ (1 - a) * ∑' y, (f x) y := by
            congr 1; ext x; rw [ENNReal.tsum_mul_left]
        _ = ∑' x, p x ^ a * q x ^ (1 - a) := by
            congr 1; ext x; rw [(f x).tsum_coe, mul_one]
    intro y
    set P : α' → ℝ≥0∞ := fun x => p x * (f x) y
    set Q : α' → ℝ≥0∞ := fun x => q x * (f x) y
    have hPt : ∀ x, P x ≠ ⊤ := fun x =>
      ENNReal.mul_ne_top (PMF.apply_ne_top p x) (PMF.apply_ne_top (f x) y)
    have hQt : ∀ x, Q x ≠ ⊤ := fun x =>
      ENNReal.mul_ne_top (PMF.apply_ne_top q x) (PMF.apply_ne_top (f x) y)
    by_cases hac : ∀ x, P x ≠ 0 → Q x ≠ 0
    · by_cases hPsum : ∑' x, P x = 0
      · simp [hPsum, ENNReal.zero_rpow_of_pos ha0]
      · have hQne : ∑' x, Q x ≠ 0 := by
          intro hQsum0
          exact hPsum (ENNReal.tsum_eq_zero.mpr fun x => by
            by_cases hPx : P x = 0
            · exact hPx
            · exact absurd (ENNReal.tsum_eq_zero.mp hQsum0 x) (hac x hPx))
        have hQlt : ∑' x, Q x ≠ ⊤ :=
          ne_top_of_le_ne_top (by rw [q.tsum_coe]; exact one_ne_top)
            (ENNReal.tsum_le_tsum fun x => by
              exact mul_le_of_le_one_right (zero_le) (PMF.coe_le_one (f x) y))
        have hpw : ∀ x, ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) *
            (Q x) ^ ((a - 1) / a : ℝ) = P x := by
          intro x
          by_cases hPx : P x = 0
          · simp [hPx, ENNReal.zero_rpow_of_pos ha0,
              ENNReal.zero_rpow_of_pos (inv_pos.mpr ha0)]
          · have hQx : Q x ≠ 0 := hac x hPx
            rw [ENNReal.mul_rpow_of_ne_top
                  (ENNReal.rpow_ne_top_of_nonneg ha0.le (hPt x))
                  (ENNReal.rpow_ne_top_of_ne_zero hQx (hQt x)),
                ← ENNReal.rpow_mul, ← ENNReal.rpow_mul, hainv', ENNReal.rpow_one,
                mul_assoc,
                ← ENNReal.rpow_add ((1 - a) * a⁻¹) ((a - 1) / a) hQx (hQt x),
                show (1 - a) * a⁻¹ + (a - 1) / a = (0 : ℝ) from by field_simp; ring,
                ENNReal.rpow_zero, mul_one]
        have hholder : ∑' x, P x ≤
            (∑' x, P x ^ a * Q x ^ (1 - a)) ^ (a⁻¹ : ℝ) *
            (∑' x, Q x) ^ ((a - 1) / a : ℝ) := by
          have hH := ENNReal.inner_le_Lp_mul_Lq_tsum hconj
            (fun x => ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ))
            (fun x => (Q x) ^ ((a - 1) / a : ℝ))
          rw [show ∑' x, ((P x) ^ a * (Q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) *
                (Q x) ^ ((a - 1) / a : ℝ) = ∑' x, P x from tsum_congr hpw] at hH
          refine le_trans hH (mul_le_mul' ?_ (le_of_eq ?_))
          · rw [one_div]
            apply ENNReal.rpow_le_rpow _ (inv_nonneg.mpr ha0.le)
            exact ENNReal.tsum_le_tsum fun x => le_of_eq (by
              rw [← ENNReal.rpow_mul, hainv, ENNReal.rpow_one])
          · congr 1
            · exact tsum_congr fun x => by
                rw [← ENNReal.rpow_mul, hsinv, ENNReal.rpow_one]
            · rw [one_div, inv_div]
        have hpow : (∑' x, P x) ^ a ≤
            (∑' x, P x ^ a * Q x ^ (1 - a)) * (∑' x, Q x) ^ (a - 1 : ℝ) := by
          have := ENNReal.rpow_le_rpow hholder ha0.le
          rwa [ENNReal.mul_rpow_of_nonneg _ _ ha0.le, ← ENNReal.rpow_mul,
            ← ENNReal.rpow_mul, hainv, ENNReal.rpow_one,
            show (a - 1) / a * a = a - 1 from by field_simp] at this
        calc (∑' x, P x) ^ a * (∑' x, Q x) ^ (1 - a)
            ≤ (∑' x, P x ^ a * Q x ^ (1 - a)) * (∑' x, Q x) ^ (a - 1) *
              (∑' x, Q x) ^ (1 - a) := mul_le_mul_left hpow _
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              ((∑' x, Q x) ^ (a - 1) * (∑' x, Q x) ^ (1 - a)) := mul_assoc _ _ _
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              (∑' x, Q x) ^ ((a - 1) + (1 - a)) := by
              congr 1; exact (ENNReal.rpow_add _ _ hQne hQlt).symm
          _ = (∑' x, P x ^ a * Q x ^ (1 - a)) *
              (∑' x, Q x) ^ (0 : ℝ) := by congr 2; ring
          _ = ∑' x, P x ^ a * Q x ^ (1 - a) := by rw [ENNReal.rpow_zero, mul_one]
    · push Not at hac
      obtain ⟨x₀, hPx₀, hQx₀⟩ := hac
      suffices h : ∑' x, P x ^ a * Q x ^ (1 - a) = ⊤ from h ▸ le_top
      apply ENNReal.tsum_eq_top_of_eq_top ⟨x₀, ?_⟩
      rw [show Q x₀ = 0 from hQx₀]
      rw [ENNReal.rpow_eq_top_iff.mpr (Or.inl ⟨rfl, h1a⟩), mul_top]
      exact (ENNReal.rpow_pos (pos_iff_ne_zero.mpr hPx₀) (hPt x₀)).ne'

/-- Data processing inequality for the Rényi divergence under Markov kernels. -/
theorem renyiDiv_bind_right_le (a : ℝ) (ha : 1 < a) (f : α' → PMF β) (p q : PMF α') :
    (p.bind f).renyiDiv a (q.bind f) ≤ p.renyiDiv a q := by
  simp only [renyiDiv_eq_rpow ha]
  exact ENNReal.rpow_le_rpow (renyiMGF_bind_right_le a ha.le f p q)
    (inv_nonneg.mpr (sub_nonneg.mpr ha.le))

end DataProcessing

/-! ### Multiplicativity (Product Distributions) -/

universe u₁ in
/-- Multiplicativity of the Rényi MGF for independent product distributions:
`M_a(p₁⊗p₂ ‖ q₁⊗q₂) = M_a(p₁ ‖ q₁) · M_a(p₂ ‖ q₂)`. -/
theorem renyiMGF_prod {α' : Type u₁} {β : Type u₁}
    (a : ℝ) (p₁ q₁ : PMF α') (p₂ q₂ : PMF β) :
    (p₁.bind fun x => Prod.mk x <$> p₂).renyiMGF a
        (q₁.bind fun x => Prod.mk x <$> q₂) =
      p₁.renyiMGF a q₁ * p₂.renyiMGF a q₂ := by
  classical
  have hprod : ∀ (p : PMF α') (q : PMF β) (xy : α' × β),
      (p.bind fun a => Prod.mk a <$> q) xy = p xy.1 * q xy.2 := by
    intro p q ⟨x, y⟩
    simp only [PMF.bind_apply]
    change ∑' a', p a' * ((q.bind (pure ∘ Prod.mk a')) (x, y)) = p x * q y
    simp only [PMF.bind_apply, Function.comp_def, PMF.pure_apply, Prod.mk.injEq]
    have inner : ∀ a', (∑' b, q b * if x = a' ∧ y = b then 1 else 0) =
        if x = a' then q y else 0 := by
      intro a'
      by_cases hax : x = a'
      · subst hax; simp only [true_and, ite_true]
        conv_lhs => arg 1; ext b; rw [show (y = b) = (b = y) from propext eq_comm]
        simp [tsum_ite_eq]
      · simp only [hax, false_and, ite_false, mul_zero]; exact tsum_zero
    simp_rw [inner, mul_ite, mul_zero]
    conv_lhs => arg 1; ext a'; rw [show (x = a') = (a' = x) from propext eq_comm]
    simp [tsum_ite_eq]
  simp only [PMF.renyiMGF, hprod]
  simp_rw [ENNReal.mul_rpow_of_ne_top (PMF.apply_ne_top _ _) (PMF.apply_ne_top _ _)]
  simp_rw [mul_mul_mul_comm]
  rw [ENNReal.tsum_prod']
  simp_rw [ENNReal.tsum_mul_left]
  rw [ENNReal.tsum_mul_right]

universe u₁ in
/-- Multiplicativity of the Rényi divergence for independent product distributions:
`R_a(p₁⊗p₂ ‖ q₁⊗q₂) = R_a(p₁ ‖ q₁) · R_a(p₂ ‖ q₂)`. -/
theorem renyiDiv_prod {α' : Type u₁} {β : Type u₁}
    (a : ℝ) (ha : 1 < a) (p₁ q₁ : PMF α') (p₂ q₂ : PMF β) :
    (p₁.bind fun x => Prod.mk x <$> p₂).renyiDiv a
        (q₁.bind fun x => Prod.mk x <$> q₂) =
      p₁.renyiDiv a q₁ * p₂.renyiDiv a q₂ := by
  simp only [renyiDiv_eq_rpow ha, renyiMGF_prod,
    ENNReal.mul_rpow_of_nonneg _ _ (inv_nonneg.mpr (sub_nonneg.mpr ha.le))]

/-! ### Probability Preservation -/

/-- Pointwise probability preservation: for a single element `x`,
`p(x)^{a/(a-1)} / R_a(p ‖ q) ≤ q(x)`.

Proof: from `p(x)^a * q(x)^{1-a} ≤ M_a(p ‖ q)` (one term of the sum)
we get `p(x)^a ≤ M_a * q(x)^{a-1}`, then take `1/(a-1)` powers. -/
theorem renyiDiv_apply_bound (a : ℝ) (ha : 1 < a) (p q : PMF α) (x : α) :
    (p x) ^ (a / (a - 1) : ℝ) / p.renyiDiv a q ≤ q x := by
  rw [renyiDiv_eq_rpow ha]
  by_cases hpx : p x = 0
  · simp [hpx, ENNReal.zero_rpow_of_pos (div_pos (lt_trans zero_lt_one ha) (sub_pos.mpr ha))]
  · by_cases hqx : q x = 0
    · have h1a : 1 - a < 0 := by linarith
      have hqpow : (q x) ^ (1 - a) = ⊤ := by
        rw [ENNReal.rpow_eq_top_iff]; left; exact ⟨hqx, h1a⟩
      have hterm : (p x) ^ a * (q x) ^ (1 - a) = ⊤ := by
        rw [hqpow, mul_top]
        exact (ENNReal.rpow_pos (pos_iff_ne_zero.mpr hpx) (PMF.apply_ne_top p x)).ne'
      have hMGF : p.renyiMGF a q = ⊤ := by
        rw [PMF.renyiMGF]
        exact ENNReal.tsum_eq_top_of_eq_top ⟨x, hterm⟩
      have hR : (p.renyiMGF a q) ^ ((a - 1)⁻¹ : ℝ) = ⊤ := by
        rw [hMGF]; exact ENNReal.top_rpow_of_pos (inv_pos.mpr (sub_pos.mpr ha))
      simp [hqx, hR]
    · have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha
      have hqt := PMF.apply_ne_top q x
      have hle_mgf : (p x) ^ a * (q x) ^ (1 - a) ≤ p.renyiMGF a q :=
        ENNReal.le_tsum x
      have hle_rpow : ((p x) ^ a * (q x) ^ (1 - a)) ^ ((a - 1)⁻¹ : ℝ) ≤
          (p.renyiMGF a q) ^ ((a - 1)⁻¹ : ℝ) :=
        ENNReal.rpow_le_rpow hle_mgf (inv_nonneg.mpr ham1.le)
      have hlhs : ((p x) ^ a * (q x) ^ (1 - a)) ^ ((a - 1)⁻¹ : ℝ) =
          (p x) ^ (a / (a - 1)) * (q x) ^ ((1 - a) / (a - 1)) := by
        rw [ENNReal.mul_rpow_of_nonneg _ _ (inv_nonneg.mpr ham1.le),
            ← ENNReal.rpow_mul, ← ENNReal.rpow_mul]
        simp only [div_eq_mul_inv]
      have hexp : (1 - a) / (a - 1) = (-1 : ℝ) := by field_simp; ring
      rw [hlhs, hexp] at hle_rpow
      rw [ENNReal.rpow_neg_one, mul_comm, ENNReal.inv_mul_le_iff hqx hqt] at hle_rpow
      exact ENNReal.div_le_of_le_mul hle_rpow

/-- Probability preservation bound: for any event `E`,
`q(E) ≥ p(E)^{a/(a-1)} / R_a(p ‖ q)`.

This is the key lemma used in security reductions involving Rényi divergence:
if `R_a(p ‖ q)` is small, then events that are likely under `p` remain likely under `q`. -/
theorem renyiDiv_prob_bound (a : ℝ) (ha : 1 < a) (p q : PMF α) (E : α → Prop)
    [DecidablePred E] :
    (∑' x, if E x then p x else 0) ^ (a / (a - 1) : ℝ) / p.renyiDiv a q ≤
      ∑' x, if E x then q x else 0 := by
  have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha
  have ha0 : (0 : ℝ) < a := lt_trans zero_lt_one ha
  have has : (0 : ℝ) < a / (a - 1) := div_pos ha0 ham1
  by_cases hR : p.renyiDiv a q = ⊤
  · rw [hR, ENNReal.div_top]; exact zero_le
  · rw [renyiDiv_eq_rpow ha] at hR ⊢
    have hM : p.renyiMGF a q ≠ ⊤ := by
      intro hM; exact hR (by rw [hM]; exact ENNReal.top_rpow_of_pos (inv_pos.mpr ham1))
    have hac : ∀ x, p x ≠ 0 → q x ≠ 0 := by
      intro x hpx hqx
      exact hM (ENNReal.tsum_eq_top_of_eq_top ⟨x, by
        rw [ENNReal.rpow_eq_top_iff.mpr (Or.inl ⟨hqx, by linarith⟩), mul_top]
        exact (ENNReal.rpow_pos (pos_iff_ne_zero.mpr hpx) (PMF.apply_ne_top p x)).ne'⟩)
    apply ENNReal.div_le_of_le_mul
    set pE := ∑' x, if E x then p x else 0
    set qE := ∑' x, if E x then q x else 0
    set M := p.renyiMGF a q
    have hconj : a.HolderConjugate (a / (a - 1)) := Real.HolderConjugate.conjExponent ha
    have hainv : a⁻¹ * a = (1 : ℝ) := inv_mul_cancel₀ ha0.ne'
    have hainv' : a * a⁻¹ = (1 : ℝ) := mul_inv_cancel₀ ha0.ne'
    have hsinv : (a - 1) / a * (a / (a - 1)) = (1 : ℝ) := by field_simp
    have hexp : a⁻¹ * (a / (a - 1)) = (a - 1)⁻¹ := by field_simp
    -- Pointwise identity: ((p x)^a * (q x)^{1-a})^{1/a} * (q x)^{(a-1)/a} = p x
    have hpw : ∀ x, ((p x) ^ a * (q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) *
        (q x) ^ ((a - 1) / a : ℝ) = p x := by
      intro x
      by_cases hpx : p x = 0
      · simp only [hpx, ENNReal.zero_rpow_of_pos ha0, zero_mul,
          ENNReal.zero_rpow_of_pos (inv_pos.mpr ha0)]
      · have hqx : q x ≠ 0 := hac x hpx
        have hqt := PMF.apply_ne_top q x
        rw [ENNReal.mul_rpow_of_ne_top
              (ENNReal.rpow_ne_top_of_nonneg ha0.le (PMF.apply_ne_top p x))
              (ENNReal.rpow_ne_top_of_ne_zero hqx hqt),
            ← ENNReal.rpow_mul, ← ENNReal.rpow_mul, hainv', ENNReal.rpow_one, mul_assoc,
            ← ENNReal.rpow_add ((1 - a) * a⁻¹) ((a - 1) / a) hqx hqt,
            show (1 - a) * a⁻¹ + (a - 1) / a = (0 : ℝ) from by field_simp; ring,
            ENNReal.rpow_zero, mul_one]
    -- Hölder step: pE ≤ M^{1/a} * qE^{(a-1)/a}
    have hholder : pE ≤ M ^ (a⁻¹ : ℝ) * qE ^ ((a - 1) / a : ℝ) := by
      set F : α → ℝ≥0∞ := fun x =>
        if E x then ((p x) ^ a * (q x) ^ (1 - a)) ^ (a⁻¹ : ℝ) else 0
      set G : α → ℝ≥0∞ := fun x =>
        if E x then (q x) ^ ((a - 1) / a : ℝ) else 0
      have hH := ENNReal.inner_le_Lp_mul_Lq_tsum hconj F G
      have hFG : pE = ∑' x, F x * G x :=
        tsum_congr fun x => by
          simp only [F, G]
          split_ifs with hE
          · exact (hpw x).symm
          · simp
      have hFa : (∑' x, F x ^ a) ^ (1 / a : ℝ) ≤ M ^ (a⁻¹ : ℝ) := by
        rw [one_div]; gcongr
        apply ENNReal.tsum_le_tsum; intro x; simp only [F]
        split_ifs with hE
        · rw [← ENNReal.rpow_mul, hainv, ENNReal.rpow_one]
        · rw [ENNReal.zero_rpow_of_pos ha0]; exact zero_le
      have hGq : (∑' x, G x ^ (a / (a - 1) : ℝ)) ^ (1 / (a / (a - 1)) : ℝ) =
          qE ^ ((a - 1) / a : ℝ) := by
        congr 1
        · exact tsum_congr fun x => by
            simp only [G]
            split_ifs with hE
            · rw [← ENNReal.rpow_mul, hsinv, ENNReal.rpow_one]
            · exact ENNReal.zero_rpow_of_pos has
        · rw [one_div, inv_div]
      rw [hFG]
      exact le_trans hH (mul_le_mul' hFa (le_of_eq hGq))
    -- Raise to a/(a-1) power and simplify
    calc pE ^ (a / (a - 1) : ℝ)
        ≤ (M ^ (a⁻¹ : ℝ) * qE ^ ((a - 1) / a : ℝ)) ^ (a / (a - 1) : ℝ) :=
          ENNReal.rpow_le_rpow hholder has.le
      _ = M ^ ((a - 1)⁻¹ : ℝ) * qE := by
          rw [ENNReal.mul_rpow_of_nonneg _ _ has.le,
            ← ENNReal.rpow_mul, ← ENNReal.rpow_mul, hexp, hsinv, ENNReal.rpow_one]
      _ = qE * M ^ ((a - 1)⁻¹ : ℝ) := mul_comm _ _

/-! ### From Relative Error to Rényi Divergence -/

/-- If the pointwise relative error between two PMFs is bounded by `δ`,
then the Rényi MGF is bounded. Specifically, if for all `x`,
`p(x) ≤ (1 + δ) · q(x)`, then `M_a(p ‖ q) ≤ (1 + δ)^(a-1)`.

This is used to convert floating-point error bounds into Rényi divergence bounds. -/
theorem renyiMGF_le_of_pointwise_le (a : ℝ) (ha : 1 < a) (p q : PMF α)
    (δ : ℝ≥0∞) (hδ : ∀ x, p x ≤ (1 + δ) * q x) :
    p.renyiMGF a q ≤ (1 + δ) ^ (a - 1) := by
  unfold PMF.renyiMGF
  have ha0 : (0 : ℝ) < a := lt_trans zero_lt_one ha
  have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha
  suffices h : ∀ x, (p x) ^ a * (q x) ^ (1 - a) ≤ (1 + δ) ^ (a - 1) * p x by
    calc ∑' x, (p x) ^ a * (q x) ^ (1 - a)
        ≤ ∑' x, (1 + δ) ^ (a - 1) * p x := ENNReal.tsum_le_tsum h
      _ = (1 + δ) ^ (a - 1) * ∑' x, p x := ENNReal.tsum_mul_left
      _ = (1 + δ) ^ (a - 1) := by rw [p.tsum_coe, mul_one]
  intro x
  by_cases hpx : p x = 0
  · simp [hpx, ENNReal.zero_rpow_of_pos ha0]
  · have hqx : q x ≠ 0 := by
      intro h; exact hpx (le_antisymm (by simpa [h] using hδ x) (zero_le))
    have hqt := PMF.apply_ne_top q x
    set r := p x / q x with hr_def
    have hrq : r * q x = p x := ENNReal.div_mul_cancel hqx hqt
    have hr_le : r ≤ 1 + δ := ENNReal.div_le_of_le_mul (hδ x)
    calc (p x) ^ a * (q x) ^ (1 - a)
        = (r * q x) ^ a * (q x) ^ (1 - a) := by rw [hrq]
      _ = r ^ a * (q x) ^ a * (q x) ^ (1 - a) := by
          rw [ENNReal.mul_rpow_of_nonneg _ _ ha0.le]
      _ = r ^ a * ((q x) ^ a * (q x) ^ (1 - a)) := by rw [mul_assoc]
      _ = r ^ a * q x := by
          rw [← ENNReal.rpow_add _ _ hqx hqt]
          simp [show a + (1 - a) = (1 : ℝ) from by ring]
      _ = r ^ (1 + (a - 1)) * q x := by congr 1; congr 1; ring
      _ = (r ^ (1 : ℝ) * r ^ (a - 1)) * q x := by
          rw [ENNReal.rpow_add_of_nonneg _ _ one_pos.le ham1.le]
      _ = r * r ^ (a - 1) * q x := by rw [ENNReal.rpow_one]
      _ ≤ r * (1 + δ) ^ (a - 1) * q x := by gcongr
      _ = (1 + δ) ^ (a - 1) * (r * q x) := by ring
      _ = (1 + δ) ^ (a - 1) * p x := by rw [hrq]

/-- Rényi divergence bound from pointwise relative error. -/
theorem renyiDiv_le_of_pointwise_le (a : ℝ) (ha : 1 < a) (p q : PMF α)
    (δ : ℝ≥0∞) (hδ : ∀ x, p x ≤ (1 + δ) * q x) :
    p.renyiDiv a q ≤ 1 + δ := by
  rw [renyiDiv_eq_rpow ha]
  have ham1 : (0 : ℝ) < a - 1 := sub_pos.mpr ha
  calc (p.renyiMGF a q) ^ ((a - 1)⁻¹ : ℝ)
      ≤ ((1 + δ) ^ (a - 1)) ^ ((a - 1)⁻¹ : ℝ) :=
        ENNReal.rpow_le_rpow (renyiMGF_le_of_pointwise_le a ha p q δ hδ)
          (inv_nonneg.mpr ham1.le)
    _ = (1 + δ) ^ ((a - 1) * (a - 1)⁻¹) := by rw [ENNReal.rpow_mul]
    _ = (1 + δ) ^ (1 : ℝ) := by congr 1; exact mul_inv_cancel₀ ham1.ne'
    _ = 1 + δ := ENNReal.rpow_one _

/-! ### Divergence to TV Distance -/

/-- Max-divergence bounds TV distance: `‖p - q‖_TV ≤ 1 - 1 / D_∞(p ‖ q)`.

When `D = maxDiv p q = ⨆ x, p(x)/q(x)` is finite, we have `q(x) ≥ p(x)/D` pointwise,
so `∑ min(p(x), q(x)) ≥ 1/D`, giving `TV(p,q) = 1 - ∑ min(p(x),q(x)) ≤ 1 - 1/D`. -/
theorem etvDist_le_of_maxDiv (p q : PMF α) :
    p.etvDist q ≤ 1 - (p.maxDiv q)⁻¹ := by
  by_cases hD : p.maxDiv q = ⊤
  · rw [hD, ENNReal.inv_top, tsub_zero]; exact etvDist_le_one p q
  set D := p.maxDiv q with hDdef
  have hD1 : 1 ≤ D := maxDiv_one_le p q
  have hD0 : D ≠ 0 := (zero_lt_one.trans_le hD1).ne'
  have hDinv_le_one : D⁻¹ ≤ 1 := ENNReal.inv_le_one.mpr hD1
  have hDinv_ne_top : D⁻¹ ≠ ⊤ := ne_top_of_le_ne_top one_ne_top hDinv_le_one
  have h_le_D : ∀ x, p x / q x ≤ D :=
    fun x => hDdef ▸ le_iSup (fun y => p y / q y) x
  -- Pointwise bounds: p x / D ≤ q x and p x / D ≤ p x, hence ≤ p x ⊓ q x.
  have h_div_le_q : ∀ x, p x / D ≤ q x := by
    intro x
    by_cases hq : q x = 0
    · by_cases hp : p x = 0
      · simp [hp, hq]
      · exact absurd (top_unique
          (by simpa [hq, ENNReal.div_zero hp] using h_le_D x)) hD
    · have h := h_le_D x
      rw [ENNReal.div_le_iff hq (PMF.apply_ne_top q x)] at h
      rwa [ENNReal.div_le_iff hD0 hD, mul_comm]
  have h_div_le_p : ∀ x, p x / D ≤ p x := by
    intro x
    rw [ENNReal.div_le_iff hD0 hD]
    nth_rw 1 [← mul_one (p x)]
    gcongr
  have h_div_le_min : ∀ x, p x / D ≤ p x ⊓ q x :=
    fun x => le_inf (h_div_le_p x) (h_div_le_q x)
  -- Identity: |p x - q x| + 2 * (p x ⊓ q x) = p x + q x
  have h_absDiff_eq : ∀ x, ENNReal.absDiff (p x) (q x) + 2 * (p x ⊓ q x) = p x + q x := by
    intro x
    have h1 : p x - q x + (p x ⊓ q x) = p x := tsub_add_min
    have h2 : q x - p x + (q x ⊓ p x) = q x := tsub_add_min
    have h2' : q x - p x + (p x ⊓ q x) = q x := by rwa [inf_comm]
    rw [ENNReal.absDiff, two_mul]
    calc p x - q x + (q x - p x) + ((p x ⊓ q x) + (p x ⊓ q x))
        = (p x - q x + (p x ⊓ q x)) + (q x - p x + (p x ⊓ q x)) := by ac_rfl
      _ = p x + q x := by rw [h1, h2']
  -- ∑ (p x ⊓ q x) ≥ 1 / D.
  have h_div_ne_top : ∀ x, p x / D ≠ ⊤ := fun x =>
    ENNReal.div_ne_top (PMF.apply_ne_top p x) hD0
  have h_sum_min : D⁻¹ ≤ ∑' x, p x ⊓ q x := by
    calc D⁻¹
        = (∑' x, p x) * D⁻¹ := by rw [p.tsum_coe, one_mul]
      _ = ∑' x, p x * D⁻¹ := ENNReal.tsum_mul_right.symm
      _ = ∑' x, p x / D := by simp_rw [← div_eq_mul_inv]
      _ ≤ ∑' x, p x ⊓ q x := ENNReal.tsum_le_tsum h_div_le_min
  -- ∑ |p x - q x| + 2 * ∑ (p x ⊓ q x) = 2.
  have h_sum_split :
      (∑' x, ENNReal.absDiff (p x) (q x)) + 2 * (∑' x, p x ⊓ q x) = 2 := by
    rw [← ENNReal.tsum_mul_left, ← ENNReal.tsum_add]
    simp only [h_absDiff_eq]
    rw [ENNReal.tsum_add, p.tsum_coe, q.tsum_coe]
    norm_num
  have h_sum_min_ne_top : (∑' x, p x ⊓ q x) ≠ ⊤ :=
    ne_top_of_le_ne_top one_ne_top (by
      calc ∑' x, p x ⊓ q x ≤ ∑' x, p x := ENNReal.tsum_le_tsum (fun x => inf_le_left)
        _ = 1 := p.tsum_coe)
  -- ∑ |p x - q x| ≤ 2 - 2/D.
  have h_two_inv_ne_top : (2 : ℝ≥0∞) * D⁻¹ ≠ ⊤ :=
    ENNReal.mul_ne_top (by norm_num) hDinv_ne_top
  have h_two_inv_le_two : (2 : ℝ≥0∞) * D⁻¹ ≤ 2 := by
    calc (2 : ℝ≥0∞) * D⁻¹ ≤ 2 * 1 := by gcongr
      _ = 2 := mul_one _
  have h_sum_absDiff_le : (∑' x, ENNReal.absDiff (p x) (q x)) ≤ 2 - 2 * D⁻¹ := by
    rw [ENNReal.le_sub_iff_add_le_right h_two_inv_ne_top h_two_inv_le_two]
    calc (∑' x, ENNReal.absDiff (p x) (q x)) + 2 * D⁻¹
        ≤ (∑' x, ENNReal.absDiff (p x) (q x)) + 2 * (∑' x, p x ⊓ q x) := by
          gcongr
      _ = 2 := h_sum_split
  -- Conclude: etvDist = (∑ |p - q|) / 2 ≤ (2 - 2/D) / 2 = 1 - 1/D.
  unfold PMF.etvDist
  rw [ENNReal.div_le_iff_le_mul (Or.inl (by norm_num)) (Or.inl (by norm_num))]
  calc ∑' x, ENNReal.absDiff (p x) (q x)
      ≤ 2 - 2 * D⁻¹ := h_sum_absDiff_le
    _ = (1 - D⁻¹) * 2 := by
        rw [ENNReal.sub_mul (fun _ _ => by norm_num), one_mul, mul_comm 2 D⁻¹]




end PMF


Source
https://github.com/Verified-zkEVM/VCV-io/blob/446baa72bb7d4296d6f6b7015fd6c15ca9c678b7/ToMathlib/Probability/ProbabilityMassFunction/RenyiDivergence.lean yukon-proof-operation:1bc4d81237c163119325b56415ae64aba334176fa911d391ecd30491332eb322 [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246MWJjNGQ4MTIzN2MxNjMxMTkzMjViNTY0MTVhZTY0YWJhMzM0MTc2ZmE5MTFkMzkxZWNkMzA0OTEzMzJlYjMyMiIsImhhc2giOiJmYjEyMTQ1ZTY5MTlhYTZhYjc2ZTUzYTk3YTliZmRmZjYyN2Y2NDljMzZkOTYyMTBhY2EwNTVkNmU1MWEwYjM0Iiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl9mNTg4YThlMzU3MjA4NzZkZTcyNTk2M2EiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me