YukonModule.ArkLib.Data.Probability.Instances.part0
DefinitionYukon_73cb364285b0db29404203c2better-codes
Source module ArkLib.Data.Probability.Instances. Reviewed historical port from Lean 4.32.2 to 4.33.1: compatible proof bodies, equivalent notation expansion, and omission of unused tooling/declarations. Retained statements and mathematical definitions preserve the original meaning. Original source: https://github.com/Verified-zkEVM/ArkLib/blob/e65197892890b8fd9b0dc05b8980273cf1d595cc/ArkLib/Data/Probability/Instances.lean
Definition code
/-
Copyright (c) 2024-2025 ArkLib Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao, Chung Thai Nguyen, Katerina Hristova
-/
import Mathlib.Probability.ProbabilityMassFunction.Monad
import Definitions.Def_Yukon_58cc714fb61020bdf4d3e0f8
import Definitions.Def_Yukon_8cbc36bf7c5db72d14564b22
import Definitions.Def_Yukon_be2502e9fa82964be2b26d94
import Definitions.Def_Yukon_8ee29ebdbfe642c7cc9f0456
import Definitions.Def_Yukon_ad19032865816a17e8b4a4b6
import Mathlib.Algebra.MvPolynomial.SchwartzZippel
import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Data.ENNReal.Inv
import Mathlib.Data.ENat.Basic
import Mathlib.Data.ENat.Defs
import Mathlib.Data.Nat.Cast.Order.Field
import Mathlib.Algebra.CharP.Defs
import Mathlib.Data.NNReal.Basic
import Mathlib.Data.NNReal.Defs
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Finsupp.Basic
import Mathlib.Data.Nat.Digits.Defs
import Mathlib.Data.Nat.Bitwise
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Tactic.IntervalCases
import Mathlib.Order.Interval.Finset.Nat
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Algebra.Ring.Regular
import Mathlib.Algebra.Order.Star.Basic
import Init
import Mathlib.RingTheory.SimpleRing.Principal
import Mathlib.Probability.Distributions.Uniform
import Mathlib.Data.Rat.Star
import Mathlib.Probability.Notation
import Mathlib.Algebra.BigOperators.Finsupp.Fin
import Mathlib.Data.Finsupp.Fin
import Mathlib.Algebra.MvPolynomial.Equiv
import Mathlib.RingTheory.MvPolynomial.Basic
import Mathlib.RingTheory.Polynomial.Basic
import Mathlib.Algebra.Group.Action.Pointwise.Finset
import Mathlib.Algebra.Polynomial.Roots
import Mathlib.Algebra.MvPolynomial.Degrees
set_option backward.isDefEq.respectTransparency.types false
/-! # Probability Instances
Basic probability instances and probability computations for `PMF`: uniform sampling,
the Schwartz-Zippel bound in probability form, and collision bounds for linear forms.
## References
* [Arnon, G., Boneh, D., and Fenzi, G., *Open Problems in List Decoding and Correlated
Agreement*][ABF26]
-/
open ProbabilityTheory Filter NNReal Finset Function Real
open scoped BigOperators ProbabilityTheory
-- TODO(dtumad): Move most of the stuff in this file to VCV and generalize as possible
section
variable {α : Type*}
instance _root_.instIsEmptyPMF_arkLib [IsEmpty α] : IsEmpty (PMF α) := by
refine Subtype.isEmpty_of_false ?_
intro f h
have : Fintype α := Fintype.ofIsEmpty
have one_eq_zero := HasSum.unique h (hasSum_fintype f)
aesop
-- @[simp]
-- theorem PMF.eq_pure_iff_ge_one {α : Type*} {p : PMF α} {a : α} : p = pure a ↔ p a ≥ 1 := by
-- constructor <;> intro h
-- · sorry
-- · ext b
-- simp only [pure, PMF.pure_apply]
-- by_cases hb : b = a
-- · simp [hb]; exact le_antisymm (PMF.coe_le_one p a) h
-- · simp [hb]; sorry
end
namespace Probability
section ProbabilityTools
/-- Unrolls `Pr_{ let x ← D }[P x]` into a sum of the form
`∑' x, Pr[x] * (if P x then 1 else 0)`. -/
theorem prob_tsum_form_singleton {α : Type} (D : PMF α) (P : α → Prop) [DecidablePred P] :
(((do { let x ← D; return (P x) }) True) : ENNReal) = ∑' x, (D x) * (if P x then 1 else 0) :=
ProbabilityTheory.Pr_eq_tsum_indicator D P
theorem prob_tsum_form_split_first {α : Type} (D : PMF α) (D_rest : α → PMF Prop) :
(do let x ← D; D_rest x) True = ∑' x, (D x) * (D_rest x True) := by
-- These are definitionally the same!
exact PMF.bind_apply D D_rest True
open Classical in
/-- Unrolls `Pr_{ let x ← D; let y ← D }[P x y]` into a sum of the form
`∑' (x × y), (if P x y then 1 else 0)`. -/
theorem prob_tsum_form_doubleton {α β : Type}
(D₁ : PMF α) (D₂ : PMF β)
(P : α → β → Prop) [∀ x, DecidablePred (P x)] : -- Need decidability for inner P
(((do { let x ← D₁; let y ← D₂; return (P x y) }) True) : ENNReal)
= ∑' xy : α × β, (D₁ xy.1) * (D₂ xy.2) * (if P xy.1 xy.2 then (1 : ENNReal) else 0) := by
let D_rest := fun (x : α) => (do
let y ← D₂
return (P x y)
)
conv_lhs =>
apply prob_tsum_form_split_first (D := D₁) (D_rest := D_rest)
simp_rw [D_rest]
simp_rw [prob_tsum_form_singleton]
conv_lhs => enter [1, x]; rw [←ENNReal.tsum_mul_left]
-- ⊢ (∑' (x : α), ... = ∑' (x : γ) (i : δ), ...
rw [←ENNReal.tsum_prod]
congr 1
funext xy
rw [←mul_assoc]
theorem prob_uniform_eq_card_filter_div_card {F : Type} [Fintype F] [Nonempty F]
(P : F → Prop) [DecidablePred P] :
(((do { let r ←$ᵖ F; return ( P r ) }) True) : ENNReal) =
((Finset.filter (α := F) P Finset.univ).card : ℝ≥0) / (Fintype.card F : ℝ≥0) := by
classical
-- Expand Pr_ using the same approach as Notation.lean
simp only [Bind.bind, PMF.bind, PMF.uniformOfFintype_apply, pure, PMF.pure_apply, eq_iff_iff,
mul_ite, mul_one, mul_zero, ENNReal.coe_natCast]
simp only [DFunLike.coe, true_iff]
-- ⊢ (∑' (a : F), if P a then (↑(Fintype.card F))⁻¹ else 0)
-- = ↑(#(filter P univ)) / ↑(Fintype.card F)
rw [tsum_eq_sum (α := ENNReal) (β := F) (f := fun a => if P a then (↑(Fintype.card F))⁻¹ else 0)
(s := Finset.filter P Finset.univ) (hf := fun b => by
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
intro hb
simp only [hb, if_false]
)] -- rewrite the infinite sum as a sum
-- ⊢ (∑ b with P b, if P b then (↑(Fintype.card F))⁻¹ else 0) = ↑(#(filter P univ)) / ↑q
rw [Finset.sum_ite] -- simplify the if-then-else inside the sum
simp only [Finset.sum_const_zero, add_zero] -- remove the second sum of 0s
rw [Finset.sum_const] -- simplify the left sum of the constants
-- Rewrite nsmul (scalar multiplication by ℕ) as standard multiplication using Nat.cast
rw [nsmul_eq_mul'] -- Use nsmul_eq_mul' which handles the coercion to ℝ≥0
-- ⊢ (↑(Fintype.card F))⁻¹ * ↑(#({x ∈ filter P univ | P x})) = ↑(#(filter P univ)) / ↑q
rw [mul_comm]
conv_lhs => rw [←div_eq_mul_inv]
-- ⊢ ↑(#({x ∈ filter P univ | P x})) / ↑(Fintype.card F) = ↑(#(filter P univ)) / ↑(Fintype.card F)
have h_card_eq: {x ∈ filter P univ | P x} = filter P univ := by
ext x
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
-- ⊢ P x ∧ P x ↔ P x
rw [and_self_iff]
rw [h_card_eq]
lemma _root_.Fintype.card_fun_fin_one_eq {F : Type} [Fintype F] [Nonempty F] :
Fintype.card (Fin 1 → F) = Fintype.card F := by
rw [Fintype.card_fun]
simp only [Fintype.card_unique, pow_one]
theorem prob_uniform_singleton_finFun_eq {F : Type} [Fintype F] [Nonempty F]
(P : F → Prop) :
(((do { let r ← $ᵖ (Fin 1 → F); return (
P (r 0) ) }) True) : ENNReal) = (((do { let r ←$ᵖ F; return ( P r ) }) True) : ENNReal) := by
classical
-- 1. Unfold both sides using the definition of probability for uniform distributions
rw [prob_uniform_eq_card_filter_div_card (F := F)]
rw [prob_uniform_eq_card_filter_div_card (F := Fin 1 → F)]
-- 2. Handle the denominators: Show card(F) = card(Fin 1 → F)
-- Fintype.card_fun_fin_one proves that `Fintype.card (Fin 1 → F) = Fintype.card F`
rw [Fintype.card_fun_fin_one_eq]
-- 3. Handle the numerators: Show the cardinalities of the two filter sets are equal.
congr 1 -- This tells Lean the denominators match, so just prove the numerators are equal
-- Define the equivalence `e` that maps `(r : Fin 1 → F)` to `r 0`
let e : (Fin 1 → F) ≃ F := Equiv.funUnique (Fin 1) F
-- Define the two sets we are comparing
let s₁ := Finset.filter (fun (r : Fin 1 → F) => P (r 0)) Finset.univ
let s₂ := Finset.filter P Finset.univ
-- Show that s₂ is just the image of s₁ under the map `e`
have h_map_eq : s₂ = Finset.map e.toEmbedding s₁ := by
ext x -- ⊢ x ∈ s₂ ↔ x ∈ Finset.map e.toEmbedding s₁
simp only [mem_filter, mem_univ, true_and, Fin.isValue, mem_map_equiv, s₂, s₁]
-- ⊢ P x ↔ P (e.symm x 0)
rfl
simp only [ENNReal.coe_natCast, Fin.isValue, Nat.cast_inj]
have h_card_eq : s₂.card = s₁.card := by
rw [h_map_eq]
rw [Finset.card_map e.toEmbedding]
rw [h_card_eq]
theorem prob_split_uniform_sampling_of_prod {γ δ : Type}
-- Fintype & Nonempty assumptions for all types
[Fintype γ] [Fintype δ] [Nonempty γ] [Nonempty δ]
-- The predicate on the original (combined) type
(P : γ × δ → Prop)
:
-- LHS: Probability over the combined space
(((do { let r ← $ᵖ (γ × δ); return ( P r ) }) True) : ENNReal) =
-- RHS: Probability over the sequential, split spaces
(((do { let x ← $ᵖ γ; let y ← $ᵖ δ; return ( P (x, y) ) }) True) : ENNReal) := by
classical
rw [prob_tsum_form_singleton]
let D_rest := fun (x : γ) => (do
let y ← $ᵖ δ
return (P (x, y))
)
conv_rhs =>
apply prob_tsum_form_split_first (D := $ᵖ γ) (D_rest := D_rest)
simp_rw [D_rest]
simp_rw [prob_tsum_form_singleton]
conv_rhs => enter [1, x]; rw [←ENNReal.tsum_mul_left]
rw [←ENNReal.tsum_prod]
congr
funext xy
simp only [PMF.uniformOfFintype_apply, Fintype.card_prod, Nat.cast_mul, mul_ite, mul_one,
mul_zero, Prod.mk.eta]
by_cases hP : P xy
· simp only [hP, ↓reduceIte]
rw [ENNReal.mul_inv_rev_ENNReal (ha := Fintype.card_ne_zero)]
· simp only [hP, ↓reduceIte]
/--
Proves that a `do` block sampling two independent uniform distributions
is equal to the single uniform distribution over the product type.
-/
theorem do_two_uniform_sampling_eq_uniform_prod {α β : Type} [Fintype α] [Fintype β]
[Nonempty α] [Nonempty β] :
(do
let x ← $ᵖ α;
let y ← $ᵖ β
pure (x, y)
) = $ᵖ (α × β) := by
apply PMF.ext
intro xy
rcases xy with ⟨x, y⟩
have h_rhs : ($ᵖ (α × β)) (x, y) = (Fintype.card (α × β) : ENNReal)⁻¹ := by
rw [PMF.uniformOfFintype_apply]
simp only [PMF.uniformOfFintype_apply, Fintype.card_prod, Nat.cast_mul]
dsimp only [Bind.bind, PMF.bind_apply]
simp only [PMF.uniformOfFintype_apply]
rw [ENNReal.tsum_mul_left]
rw [←ENNReal.tsum_prod]
rw [ENNReal.tsum_mul_left]
rw [←mul_assoc]
rw [ENNReal.mul_inv_rev_ENNReal (ha := Fintype.card_ne_zero)]
conv_rhs =>
rw [←mul_one (a := ((Fintype.card α : ENNReal) * (Fintype.card β : ENNReal) : ENNReal)⁻¹)]
congr 1
simp only [Prod.mk.eta]
dsimp only [pure, PMF.pure_apply]
-- ⊢ ∑' (i : F × (Fin ϑ → F)), (pure i) (x, y) = 1
rw [tsum_eq_single ((x, y) : α × β)]
· -- ⊢ (if (x, y) = (x, y) then 1 else 0) = 1
simp only [ite_true]
· -- Goal 2: Prove all other terms are 0
intro i h_ne
simp only [ite_eq_right_iff, one_ne_zero, imp_false]
exact id (Ne.symm h_ne)
/-- The probability that a property `P` holds for a uniformly random `r : F` equals
`ENNReal.ofReal` of the real-valued density `|{x : F // P x}| / |F|`. This is the
`ENNReal.ofReal`-of-a-real-number form of `prob_uniform_eq_card_filter_div_card`, useful when the
surrounding goal is stated over `ℝ` rather than `ℝ≥0`. -/
theorem prob_uniform_eq_ofReal {F : Type} [Fintype F] [Nonempty F]
(P : F → Prop) [DecidablePred P] :
(((do { let r ←$ᵖ F; return (P r) }) True) : ENNReal) = ENNReal.ofReal
(((Finset.filter (α := F) P Finset.univ).card : ℝ) / (Fintype.card F : ℝ)) := by
convert prob_uniform_eq_card_filter_div_card P using 1
rw [ENNReal.ofReal_div_of_pos] <;> norm_num
exact Fintype.card_pos
/--
**Generic Probability Splitting Lemma (via Equivalence)**
This lemma proves that a single probability statement over a uniform
distribution on a type `α` can be rewritten as a sequential probability
statement over two smaller, independent distributions `γ` and `δ`,
given an equivalence `e : α ≃ γ × δ`.
This is a formal "change of variables" for probabilities, and it's
the generic version of `prob_split_randomness_apply`.
It allows us to "split" one `let` into two.
-/
theorem prob_split_uniform_sampling_of_equiv_prod {α γ δ : Type}
-- Fintype & Nonempty assumptions for all types
[Fintype α] [Fintype γ] [Fintype δ]
[Nonempty α] [Nonempty γ] [Nonempty δ]
-- The equivalence that splits α into γ × δ
(e : α ≃ γ × δ)
-- The predicate on the original (combined) type
(P : α → Prop)
:
-- LHS: Probability over the combined space
(((do { let r ← $ᵖ α; return ( P r ) }) True) : ENNReal) =
-- RHS: Probability over the sequential, split spaces
(((do { let x ← $ᵖ γ; let y ← $ᵖ δ; return ( P (e.symm (x, y)) ) }) True) : ENNReal) := by
classical
-- 1. Unroll the LHS (a single `let`) using `prStx_unfold_final`
-- LHS = ∑' r, Pr[r] * (if P r then 1 else 0)
rw [prob_tsum_form_singleton]
let D_rest := fun (x : γ) => (do
let y ← $ᵖ δ
return (P (e.symm (x, y)))
)
conv_rhs =>
apply prob_tsum_form_split_first (D := $ᵖ γ) (D_rest := D_rest)
simp_rw [D_rest]
simp only [PMF.uniformOfFintype_apply, mul_ite, mul_one, mul_zero]
simp_rw [prob_tsum_form_singleton]
-- ⊢ (∑' (x : α), ... = ∑' (x : γ), (↑(Fintype.card γ))⁻¹ * ∑' (x_1 : δ), ...
conv_rhs => enter [1, x]; rw [←ENNReal.tsum_mul_left]
-- ⊢ (∑' (x : α), ... = ∑' (x : γ) (i : δ), ...
rw [←ENNReal.tsum_prod]
-- ⊢ (∑' (x : α), ...) = (∑' (p : γ × δ), ...)
conv_lhs =>
rw [tsum_eq_sum (α := ENNReal) (β := α) (f :=
fun x => if P x then (↑(Fintype.card α))⁻¹ else 0) (s := Finset.univ) (hf := fun b => by
simp only [mem_univ, not_true_eq_false, ite_eq_right_iff, ENNReal.inv_eq_zero,
IsEmpty.forall_iff]
)]
conv_rhs =>
rw [tsum_eq_sum (α := ENNReal) (β := γ × δ) (f := fun x =>
(↑(Fintype.card γ))⁻¹ * (($ᵖ δ) x.2 * if P (e.symm x) then 1 else 0)
) (s := Finset.univ) (hf := fun b => by
simp only [mem_univ, not_true_eq_false, IsEmpty.forall_iff]
)]
-- ⊢ (∑ b : α, .. = ..) = (∑ b : γ × δ, ..)
have hcard_of_equiv: (Fintype.card α) = (Fintype.card (γ × δ)) := Fintype.card_congr e
rw [Finset.sum_equiv (s := Finset.univ (α := α)) (t := Finset.univ (α := γ × δ))
(f := fun x => if P x then (↑(Fintype.card α))⁻¹ else 0)
(g := fun x => (↑(Fintype.card γ))⁻¹ * (($ᵖ δ) x.2 * if P (e.symm x) then 1 else 0))
(e := e) (hst := fun i => by
simp only [mem_univ]
) (hfg := fun i => by
simp only [mem_univ, PMF.uniformOfFintype_apply, Equiv.symm_apply_apply, mul_ite, mul_one,
mul_zero, forall_const]
by_cases hP : P i
· simp only [hP, ↓reduceIte]
rw [hcard_of_equiv]
rw [ENNReal.mul_inv_rev_ENNReal (ha := Fintype.card_ne_zero)]
rw [Fintype.card_prod]; rw [Nat.cast_mul]
· simp only [hP, ↓reduceIte]
)]
/-- Rewrites the probability over the large `r` space as a sequential
probability, sampling `r_last` *first*, then `r_init`.
-/
theorem prob_split_last_uniform_sampling_of_finFun {ϑ : ℕ} {F : Type} [Fintype F] [Nonempty F]
(P : F → (Fin ϑ → F) → Prop)
:
(((do { let r ← $ᵖ (Fin (ϑ + 1) → F); return ( P (r (Fin.last ϑ)) (fun i ↦ r i.castSucc) ) }) True) : ENNReal) =
(((do { let r_last ← $ᵖ F; let r_init ← $ᵖ (Fin ϑ → F); return ( P r_last r_init ) }) True) : ENNReal) := by
classical
rw [prob_tsum_form_doubleton]
let e : (Fin (ϑ + 1) → F) ≃ F × (Fin ϑ → F) := equivFinFunSplitLast
conv_lhs =>
rw [prob_split_uniform_sampling_of_equiv_prod (e := e)]
rw [prob_tsum_form_doubleton]
congr 1
funext xy
congr 1
have hEquiv_r_last : e.symm (xy.1, xy.2) (Fin.last ϑ) = xy.1 := by
simp only [equivFinFunSplitLast, Prod.mk.eta, Equiv.coe_fn_symm_mk, Fin.snoc_last, e]
have hEquiv_r_init : ∀ i: Fin ϑ, e.symm (xy.1, xy.2) i.castSucc = xy.2 i := by
simp only [equivFinFunSplitLast, Prod.mk.eta, Equiv.coe_fn_symm_mk, Fin.snoc_castSucc,
implies_true, e]
simp_rw [hEquiv_r_last, hEquiv_r_init]
/--
Helper lemma for probability marginalization.
`Pr_{ (x, y) ← D₁ × D₂ }[ P x ] = Pr_{ x ← D₁ }[ P x ]`
-/
theorem prob_marginalization_first_of_prod {α β : Type} [Fintype α] [Fintype β]
[Nonempty α] [Nonempty β] (P : α → Prop) :
(((do { let r ← $ᵖ (α × β); return ( P r.1 ) }) True) : ENNReal) = (((do { let x ← $ᵖ α; return ( P x ) }) True) : ENNReal) := by
classical
rw [prob_split_uniform_sampling_of_prod]
let D_rest := fun (x : α) => (do
let y ← $ᵖ β
pure (P (x, y).1)
)
conv_lhs =>
apply prob_tsum_form_split_first (D := $ᵖ α) (D_rest := D_rest)
simp_rw [prob_tsum_form_singleton]
congr 1
funext x
congr 1
unfold D_rest
-- ⊢ (D_rest x) True = if P x then 1 else 0
simp only [Bind.bind, pure, PMF.bind_const, PMF.pure_apply, eq_iff_iff, true_iff]
/--
**Monotonicity of Probability**
If event `A` (defined by predicate `f`) implies event `B` (defined by
predicate `g`) for all outcomes `r`, then the probability of `A`
is less than or equal to the probability of `B`.
-/
theorem Pr_le_Pr_of_implies {α : Type} (D : PMF α)
(f g : α → Prop)
(h_imp : ∀ r, f r → g r) :
(((do { let r ← D; return ( f r ) }) True) : ENNReal) ≤ (((do { let r ← D; return ( g r ) }) True) : ENNReal) := by
classical
-- 1. Unroll both probability statements into their sum forms
rw [prob_tsum_form_singleton D f]
rw [prob_tsum_form_singleton D g]
-- Goal: ⊢ (∑' r, D r * if f r then 1 else 0) ≤ (∑' r, D r * if g r then 1 else 0)
-- 2. Apply tsum_le_tsum: We need to show term-wise inequality
apply ENNReal.tsum_le_tsum
-- 3. Show the term-wise inequality for each r
intro r
-- Goal: ⊢ D r * (if f r then 1 else 0) ≤ D r * (if g r then 1 else 0)
-- Use `mul_le_mul_left'` which requires proving D r ≠ 0 and D r ≠ ∞
-- Or simpler: use `mul_le_mul_of_nonneg_left` which only requires D r ≥ 0
apply mul_le_mul_of_nonneg_left
-- 4. Prove the inequality between the `ite` terms using the implication
· by_cases hf : f r
· simp only [hf, ↓reduceIte, h_imp, le_refl]
· simp only [hf, ↓reduceIte, zero_le]
-- 5. Prove the factor `D r` is non-negative
· exact zero_le -- Probabilities are always non-negative
theorem Pr_multi_let_equiv_single_let {α β : Type}
(D₁ : PMF α) (D₂ : PMF β) -- Assuming D₂ is independent for simplicity
(P : α → β → Prop) :
-- LHS: Multi-let probability
(((do { let x ← D₁; let y ← D₂; return ( P x y ) }) True) : ENNReal)
=
-- RHS: Single-let probability over the combined distribution
let D_combined : PMF (α × β) := do { let x ← D₁; let y ← D₂; pure (x, y) }
(((do { let r ← D_combined; return ( P r.1 r.2 ) }) True) : ENNReal) := by
classical
dsimp only [Lean.Elab.WF.paramLet] -- Expose LHS do block
simp only [bind_pure_comp, _root_.map_bind, Functor.map_map]
/--
**Law of Total Probability (Partitioning an Event)**
The probability of an event `f r` occurring can be calculated by
summing the probabilities of two disjoint cases:
1. `f r` occurs AND `g r` occurs.
2. `f r` occurs AND `g r` does NOT occur.
Good to be used with `Pr_multi_let_equiv_single_let`
-/
theorem Pr_add_split_by_complement {α : Type} (D : PMF α)
(f g : α → Prop) :
(((do { let r ← D; return ( f r ) }) True) : ENNReal) =
(D >>= (fun r => pure (g r ∧ f r))) True + (((do { let r ← D; return ( ¬(g r) ∧ f r ) }) True) : ENNReal) := by
classical
-- 1. Unroll all three probability statements into their tsum forms
rw [prob_tsum_form_singleton D f]
rw [prob_tsum_form_singleton D (fun r => g r ∧ f r)]
rw [prob_tsum_form_singleton D (fun r => ¬(g r) ∧ f r)]
-- 2. Combine the two sums on the RHS using ENNReal.tsum_add
-- Need to prove summability for both, which is true in ENNReal
rw [← ENNReal.tsum_add]
congr 1
funext r
rw [←mul_add]
congr 1
by_cases hg : g r
· simp only [hg, true_and, not_true_eq_false, false_and, ↓reduceIte, add_zero]
· simp only [hg, false_and, ↓reduceIte, not_false_eq_true, true_and, zero_add]
example : -- Pr_split_two_complements
let f := fun (x, _) => x = true
let g := fun (_, y) => y = true
(((do { let x ← $ᵖ Bool; let y ← $ᵖ Bool; return ( f (x, y) ) }) True) : ENNReal) =
(((do { let x ← $ᵖ Bool; let y ← $ᵖ Bool; return ( g (x, y) ∧ f (x, y) ) }) True) : ENNReal) +
(((do { let x ← $ᵖ Bool; let y ← $ᵖ Bool; return ( ¬(g (x, y)) ∧ f (x, y) ) }) True) : ENNReal) := by
let D : PMF (Bool × Bool) := do
let x ← $ᵖ Bool
let y ← $ᵖ Bool
pure (x, y)
set f := fun ((x, y) : (Bool × Bool)) => x = true
set g := fun ((x, y) : (Bool × Bool)) => y = true
simp only
rw [Pr_multi_let_equiv_single_let (D₁ := $ᵖ Bool) (D₂ := $ᵖ Bool)]
rw [Pr_multi_let_equiv_single_let (D₁ := $ᵖ Bool) (D₂ := $ᵖ Bool)]
rw [Pr_multi_let_equiv_single_let (D₁ := $ᵖ Bool) (D₂ := $ᵖ Bool)]
rw [Pr_add_split_by_complement (D := D) (f := f) (g := g)]
/--
`Pr_{r ← D}[ P_out ∧ P(r) ] = (if P_out then Pr_{r ← D}[ P(r) ] else 0)`
-/
theorem prob_const_and_prop_eq_ite {α : Type} (D : PMF α)
(P_out : Prop) [Decidable P_out]
(P : α → Prop) :
(((do { let r ← D; return ( P_out ∧ P r ) }) True) : ENNReal) = if P_out then (((do { let r ← D; return ( P r ) }) True) : ENNReal) else 0 := by
classical
by_cases h_P_out : P_out
· -- Case 1: P_out is True
simp only [h_P_out, if_true, true_and]
· -- Case 2: P_out is False
simp only [h_P_out, if_false, false_and]
rw [prob_tsum_form_singleton]
simp only [if_false, mul_zero, tsum_zero]
/-- Congruence lemma for Probability: If P(x) ↔ Q(x) for all x, then Pr[P] = Pr[Q]. -/
lemma Pr_congr {α : Type} {D : PMF α} {P Q : α → Prop}
(h : ∀ x, P x ↔ Q x) : (((do { let x ← D; return ( P x ) }) True) : ENNReal) = (((do { let x ← D; return ( Q x ) }) True) : ENNReal) := by
congr 2; funext x;
congr 1; exact propext (h x)
/--
**Union Bound (binary form)**
The probability of a disjunction of two events is at most the sum of their individual
probabilities.
-/
theorem Pr_or_le {α : Type} (D : PMF α) (f g : α → Prop) :
(((do { let r ← D; return ( f r ∨ g r ) }) True) : ENNReal) ≤ (((do { let r ← D; return ( f r ) }) True) : ENNReal) + (((do { let r ← D; return ( g r ) }) True) : ENNReal) := by
classical
rw [prob_tsum_form_singleton, prob_tsum_form_singleton, prob_tsum_form_singleton,
← ENNReal.tsum_add]
apply ENNReal.tsum_le_tsum
intro r
rw [← mul_add]
refine mul_le_mul_of_nonneg_left ?_ zero_le
by_cases hf : f r <;> by_cases hg : g r <;> simp [hf, hg]
/--
**Union Bound (over a finite index set)**
The probability that `∃ i, f i r` holds is at most the sum, over `i`, of the probabilities that
`f i r` holds.
-/
theorem Pr_exists_le {α ι : Type} [Fintype ι] (D : PMF α) (f : ι → α → Prop) :
(((do { let r ← D; return ( ∃ i, f i r ) }) True) : ENNReal) ≤ ∑ i, (((do { let r ← D; return ( f i r ) }) True) : ENNReal) := by
classical
have key : ∀ (s : Finset ι),
(((do { let r ← D; return ( ∃ i ∈ s, f i r ) }) True) : ENNReal) ≤ ∑ i ∈ s, (((do { let r ← D; return ( f i r ) }) True) : ENNReal) := by
intro s
induction s using Finset.induction with
| empty =>
have h0 : (((do { let r ← D; return ( ∃ i ∈ (∅ : Finset ι), f i r ) }) True) : ENNReal)
= (((do { let r ← D; return ( (False : Prop) ) }) True) : ENNReal) :=
Pr_congr (fun r => by simp)
rw [Finset.sum_empty, h0, prob_tsum_form_singleton]
simp
| insert a s ha ih =>
have hcongr : (((do { let r ← D; return ( ∃ i ∈ insert a s, f i r ) }) True) : ENNReal) =
(((do { let r ← D; return ( f a r ∨ ∃ i ∈ s, f i r ) }) True) : ENNReal) :=
Pr_congr (fun r => by
constructor
· rintro ⟨i, hi, hfi⟩
rcases Finset.mem_insert.mp hi with rfl | hi
· exact Or.inl hfi
· exact Or.inr ⟨i, hi, hfi⟩
· rintro (hfa | ⟨i, hi, hfi⟩)
· exact ⟨a, Finset.mem_insert_self a s, hfa⟩
· exact ⟨i, Finset.mem_insert_of_mem hi, hfi⟩)
rw [hcongr]
calc (((do { let r ← D; return ( f a r ∨ ∃ i ∈ s, f i r ) }) True) : ENNReal)
≤ (((do { let r ← D; return ( f a r ) }) True) : ENNReal) + (((do { let r ← D; return ( ∃ i ∈ s, f i r ) }) True) : ENNReal) := Pr_or_le D _ _
_ ≤ (((do { let r ← D; return ( f a r ) }) True) : ENNReal) + ∑ i ∈ s, (((do { let r ← D; return ( f i r ) }) True) : ENNReal) := by gcongr
_ = ∑ i ∈ insert a s, (((do { let r ← D; return ( f i r ) }) True) : ENNReal) := by rw [Finset.sum_insert ha]
simpa using key Finset.univ
/--
**Marginal Bound for Sequential Sampling**
If, for every fixed outcome `b` of the second sample, the probability over the first sample is
bounded by a constant `c` (not depending on `b`), then the same bound holds for the probability
over the full sequential sample.
-/
theorem Pr_seq_le_of_forall_le {α β : Type} (Da : PMF α) (Db : PMF β) (Q : α → β → Prop)
{c : ENNReal} (h : ∀ b, (((do { let a ← Da; return (Q a b) }) True) : ENNReal) ≤ c) :
(((do { let b ← Db; let a ← Da; return ( Q a b ) }) True) : ENNReal) ≤ c := by
classical
let D_rest : β → PMF Prop := fun b => (do let a ← Da; return (Q a b))
calc (((do { let b ← Db; let a ← Da; return ( Q a b ) }) True) : ENNReal)
= ∑' b, Db b * (D_rest b) True := prob_tsum_form_split_first Db D_rest
_ ≤ ∑' b, Db b * c := by
apply ENNReal.tsum_le_tsum
intro b
exact mul_le_mul_of_nonneg_left (h b) zero_le
_ = c := by rw [ENNReal.tsum_mul_right, PMF.tsum_coe, one_mul]
/-- **Schwartz-Zippel**, in probability form at an arbitrary degree bound: for a nonzero
`n`-variate polynomial `P` of total degree at most `d` over a finite domain `R`,
`Pr_{r ←$ᵖ R^n} [eval r P = 0] ≤ d / |R|` .
The full-carrier case of `prob_eval_zero_univ_le_div`; `Fintype.fieldOfDomain` supplies the
field structure. `MvPolynomial.schwartz_zippel_sum_degreeOf` gives a tighter coordinatewise
bound where that shape is wanted. -/
lemma prob_schwartz_zippel_mv_polynomial_of_totalDegree_le
{R : Type} [CommRing R] [IsDomain R] [Fintype R]
{n d : ℕ}
(P : MvPolynomial (Fin n) R) (h_nonzero : P ≠ 0) (h_deg : P.totalDegree ≤ d) :
(((do { let r ←$ᵖ (Fin n → R); return ( MvPolynomial.eval r P = 0 ) }) True) : ENNReal) ≤
(d : ℝ≥0) / (Fintype.card R : ℝ≥0) := by
classical
letI : Field R := Fintype.fieldOfDomain R
exact prob_eval_zero_univ_le_div P h_nonzero h_deg
/-- **Schwartz-Zippel**, in probability form at the degree bound `n`: the `d := n`
specialisation of `prob_schwartz_zippel_mv_polynomial_of_totalDegree_le`. -/
lemma prob_schwartz_zippel_mv_polynomial {R : Type} [CommRing R] [IsDomain R] [Fintype R]
{n : ℕ}
(P : MvPolynomial (Fin n) R) (h_nonzero : P ≠ 0) (h_deg : P.totalDegree ≤ n) :
(((do { let r ←$ᵖ (Fin n → R); return ( MvPolynomial.eval r P = 0 ) }) True) : ENNReal) ≤
(n : ℝ≥0) / (Fintype.card R : ℝ≥0) :=
prob_schwartz_zippel_mv_polynomial_of_totalDegree_le P h_nonzero h_deg
/-- The polynomial identity lemma in individual-degree form: for a nonzero `m`-variate
polynomial `P` of individual degree `< d` in each variable,
`Pr_{r ←$ᵖ R^m} [eval r P = 0] ≤ m * (d - 1) / |R|` .
Obtained from `prob_schwartz_zippel_mv_polynomial_of_totalDegree_le` and
`MvPolynomial.totalDegree_le_of_degreeOf_lt`.
At `d = 0` the hypothesis `∀ i, P.degreeOf i < 0` is unsatisfiable for `m ≥ 1`, and for
`m = 0` it is vacuous with both sides `0`, a nonzero constant never vanishing. -/
lemma prob_polynomial_identity_le {R : Type} [CommRing R] [IsDomain R] [Fintype R]
{m d : ℕ} (P : MvPolynomial (Fin m) R)
(h_nonzero : P ≠ 0) (h_indiv_deg : ∀ i, P.degreeOf i < d) :
(((do { let r ←$ᵖ (Fin m → R); return ( MvPolynomial.eval r P = 0 ) }) True) : ENNReal) ≤
((m * (d - 1) : ℕ) : ℝ≥0) / (Fintype.card R : ℝ≥0) := by
have h_total_deg : P.totalDegree ≤ m * (d - 1) :=
MvPolynomial.totalDegree_le_of_degreeOf_lt P h_indiv_deg
exact prob_schwartz_zippel_mv_polynomial_of_totalDegree_le P h_nonzero h_total_deg
/-- Pushforward of `PMF.uniformOfFintype α` under a map `f : α → β` whose fibers
over the image all have the same cardinality `k > 0` is the uniform distribution
on the image of `f`.
Useful when `f` is an affine-linear surjection: every fiber is a translate of
the kernel and hence has constant cardinality. The proximity-gap proofs use this
to bridge the coefficient-parameterised sampling of an affine span to the
uniform sampling of the affine-span finset. -/
theorem _root_.PMF.map_uniformOfFintype_of_fiber_const
{α β : Type*} [Fintype α] [Nonempty α] [DecidableEq β]
(f : α → β) {k : ℕ} (hk : 0 < k)
(hfib : ∀ b ∈ Finset.univ.image f,
((Finset.univ : Finset α).filter (f · = b)).card = k) :
(PMF.uniformOfFintype α).map f =
PMF.uniformOfFinset (Finset.univ.image f)
(Finset.image_nonempty.mpr Finset.univ_nonempty) := by
classical
-- Total count = k * |image|.
have h_card : Fintype.card α = k * (Finset.univ.image f).card := by
rw [show Fintype.card α = (Finset.univ : Finset α).card from rfl,
Finset.card_eq_sum_card_image f Finset.univ,
Finset.sum_const_nat hfib]
ring
have h_k_ne : (k : ENNReal) ≠ 0 := Nat.cast_ne_zero.mpr hk.ne'
have h_k_lt_top : (k : ENNReal) ≠ ⊤ := ENNReal.natCast_ne_top _
-- PMF extensionality.
ext b
rw [PMF.map_apply, PMF.uniformOfFinset_apply]
simp_rw [PMF.uniformOfFintype_apply]
-- LHS: ∑' a, if b = f a then (Fintype.card α)⁻¹ else 0
rw [tsum_fintype, Finset.sum_ite, Finset.sum_const_zero, add_zero,
Finset.sum_const, nsmul_eq_mul]
by_cases hb : b ∈ Finset.univ.image f
· -- b ∈ image: filter (b = f ·) has card k.
rw [if_pos hb]
have h_filter_card : (Finset.univ.filter (fun a => b = f a)).card = k := by
have h_swap :
Finset.univ.filter (fun a => b = f a) =
Finset.univ.filter (fun a => f a = b) := by
ext a
simp [eq_comm]
rw [h_swap]
exact hfib b hb
rw [h_filter_card, h_card]
-- Goal: ↑k * (↑(k * |image|))⁻¹ = (↑|image|)⁻¹
push_cast
rw [ENNReal.mul_inv (Or.inl h_k_ne) (Or.inl h_k_lt_top),
← mul_assoc, ENNReal.mul_inv_cancel h_k_ne h_k_lt_top, one_mul]
· -- b ∉ image: filter is empty.
rw [if_neg hb]
have h_empty : Finset.univ.filter (fun a => b = f a) = ∅ := by
ext a
simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty,
iff_false]
intro h
apply hb
exact h ▸ Finset.mem_image_of_mem f (Finset.mem_univ a)
rw [h_empty, Finset.card_empty]
simp
/-! ## Collision bounds
Bounds of the form `≤ 1/|F|`, of the shape required by the pairwise-collision hypothesis of
`Probability.exists_large_image_of_pairwise_collision_bound`.
* `Pr_map_eq` — change of variables for a `PMF.map`, reducing a probability over a
pushforward distribution to one over the sampling it is pushed forward from.
* `prob_dotProduct_eq_zero_le` — a nonzero `F`-linear form vanishes with probability
`≤ 1/|F|`.
* `prob_uniform_le_inv_of_card_le_one` — a predicate with at most one satisfying value has
uniform-sampling probability `≤ 1/|F|`.
-/
/-- Change of variables: the probability of an event `Q` under a pushforward distribution
`p.map g` is the probability of the pulled-back event `Q ∘ g` under `p`. -/
theorem Pr_map_eq {α β : Type} (p : PMF α) (g : α → β) (Q : β → Prop) :
(((do { let b ← p.map g; return ( Q b ) }) True) : ENNReal) = (((do { let a ← p; return ( Q (g a) ) }) True) : ENNReal) := by
classical
rw [prob_tsum_form_singleton, prob_tsum_form_singleton]
rw [PMF.map]
simp only [PMF.bind_apply, Function.comp_apply, PMF.pure_apply]
rw [show (∑' (x : β), (∑' (a : α), p a * if x = g a then 1 else 0) * if Q x then 1 else 0)
= ∑' (x : β) (a : α), (p a * if x = g a then 1 else 0) * if Q x then 1 else 0 from by
simp_rw [ENNReal.tsum_mul_right]]
rw [ENNReal.tsum_comm]
congr 1
ext a
rw [tsum_eq_single (g a)]
· simp [mul_comm]
· intro b hb
simp [hb]
/-- A nonzero `F`-linear form vanishes with probability exactly `1/|F|`: for nonzero
`d : Fin k → F`, the form `v ↦ ∑ j, d j * v j` has as kernel a hyperplane of `|F| ^ (k-1)`
points out of `|F| ^ k`. -/
theorem prob_dotProduct_eq_zero_eq_inv_card {F : Type} [Field F] [Fintype F] {k : ℕ}
(d : Fin k → F) (hd : d ≠ 0) :
(((do { let v ←$ᵖ (Fin k → F); return ( (∑ j, d j * v j = 0) ) }) True) : ENNReal)
= (Fintype.card F : ENNReal)⁻¹ := by
classical
-- The `F`-linear form `v ↦ ∑ⱼ dⱼ · vⱼ`.
set L : (Fin k → F) →ₗ[F] F := ∑ j, d j • LinearMap.proj j with hL
have hLapply : ∀ v, L v = ∑ j, d j * v j := by
intro v
simp only [hL, LinearMap.coe_sum, Finset.sum_apply, LinearMap.smul_apply,
LinearMap.proj_apply, smul_eq_mul]
-- `L` is surjective: pick a coordinate `j₀` with `dⱼ₀ ≠ 0`.
obtain ⟨j₀, hj₀⟩ : ∃ j, d j ≠ 0 := by
by_contra h
exact hd (funext fun j ↦ not_not.mp (fun hj ↦ h ⟨j, hj⟩))
have hsurj : Function.Surjective L := by
intro c
refine ⟨Pi.single j₀ (c / d j₀), ?_⟩
rw [hLapply, Finset.sum_eq_single j₀]
· rw [Pi.single_eq_same, mul_div_cancel₀ _ hj₀]
· intro b _ hb
rw [Pi.single_eq_of_ne hb, mul_zero]
· intro h; exact absurd (Finset.mem_univ j₀) h
-- Rank–nullity (via the first isomorphism theorem) gives the kernel cardinality.
have hquot : Nat.card ((Fin k → F) ⧸ LinearMap.ker L) = Fintype.card F := by
rw [Nat.card_congr (L.quotKerEquivOfSurjective hsurj).toEquiv, Nat.card_eq_fintype_card]
have hcard : Fintype.card (Fin k → F)
= Fintype.card (LinearMap.ker L) * Fintype.card F := by
have := Submodule.card_eq_card_quotient_mul_card (LinearMap.ker L)
rw [hquot] at this
rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card]
exact this
-- The event set `{v | ∑ⱼ dⱼ · vⱼ = 0}` is exactly the kernel of `L`.
have hfilter : (Finset.univ.filter (fun v : Fin k → F ↦ ∑ j, d j * v j = 0)).card
= Fintype.card (LinearMap.ker L) := by
rw [Fintype.card_congr (Equiv.subtypeEquivRight (fun x ↦ by
rw [LinearMap.mem_ker, hLapply])),
Fintype.card_subtype (fun v : Fin k → F ↦ ∑ j, d j * v j = 0)]
rw [prob_uniform_eq_card_filter_div_card, hfilter, hcard]
push_cast
have hkne : (Fintype.card (LinearMap.ker L) : ENNReal) ≠ 0 := by
simp only [ne_eq, Nat.cast_eq_zero, Fintype.card_ne_zero, not_false_eq_true]
have hF : (Fintype.card F : ENNReal) ≠ 0 := by
have : Nonempty F := ⟨0⟩
simp only [ne_eq, Nat.cast_eq_zero, Fintype.card_ne_zero, not_false_eq_true]
rw [eq_comm, ← one_div,
ENNReal.div_eq_div_iff (mul_ne_zero hkne hF)
(ENNReal.mul_ne_top (by simp) (by simp)) hF (by simp)]
ring
/-- `≤`-form of `prob_dotProduct_eq_zero_eq_inv_card`: a nonzero `F`-linear form vanishes
with probability at most `1/|F|` over a uniformly random argument. -/
theorem prob_dotProduct_eq_zero_le {F : Type} [Field F] [Fintype F] {k : ℕ}
(d : Fin k → F) (hd : d ≠ 0) :
(((do { let v ←$ᵖ (Fin k → F); return ( (∑ j, d j * v j = 0) ) }) True) : ENNReal)
≤ (Fintype.card F : ENNReal)⁻¹ :=
le_of_eq (prob_dotProduct_eq_zero_eq_inv_card d hd)
/-- A predicate with at most one satisfying value holds with probability at most `1/|F|`
under uniform sampling from `F`. -/
theorem prob_uniform_le_inv_of_card_le_one {F : Type} [Fintype F] [Nonempty F]
(P : F → Prop) [DecidablePred P] (h : (Finset.univ.filter P).card ≤ 1) :
(((do { let r ←$ᵖ F; return ( P r ) }) True) : ENNReal) ≤ (Fintype.card F : ENNReal)⁻¹ := by
rw [prob_uniform_eq_card_filter_div_card]
rw [show (Fintype.card F : ENNReal)⁻¹ = (1 : ENNReal) / (Fintype.card F : ENNReal) from
(one_div _).symm]
push_cast
gcongr
exact_mod_cast h
end ProbabilityTools
section UniformProductBound
/-- For a uniformly random `xs : Fin t → ι` into a finite nonempty type, the probability that
every coordinate lands in a fixed `A : Finset ι` is `(|A| / |ι|) ^ t`: the satisfying
functions are exactly `Fintype.piFinset (fun _ ↦ A)`, of cardinality `|A| ^ t`. -/
theorem prob_uniform_pi_mem_finset_eq {ι : Type} [Fintype ι] [Nonempty ι]
(A : Finset ι) (t : ℕ) :
(((do { let xs ←$ᵖ (Fin t → ι); return ( ∀ i, xs i ∈ A ) }) True) : ENNReal) =
((A.card : ENNReal) / (Fintype.card ι : ENNReal)) ^ t := by
classical
rw [prob_uniform_eq_card_filter_div_card]
have hfilter : Finset.filter (fun xs : Fin t → ι ↦ ∀ i, xs i ∈ A) Finset.univ =
Fintype.piFinset (fun _ : Fin t ↦ A) := by
ext xs
simp [Fintype.mem_piFinset]
rw [hfilter, Fintype.card_piFinset]
simp only [Finset.prod_const, Finset.card_univ, Fintype.card_fin, Fintype.card_fun]
push_cast
rw [div_eq_mul_inv, div_eq_mul_inv, mul_pow, ENNReal.inv_pow]
/-- `≤`-form of `prob_uniform_pi_mem_finset_eq`. -/
theorem prob_uniform_pi_mem_finset_le {ι : Type} [Fintype ι] [Nonempty ι]
(A : Finset ι) (t : ℕ) :
(((do { let xs ←$ᵖ (Fin t → ι); return ( ∀ i, xs i ∈ A ) }) True) : ENNReal) ≤
((A.card : ENNReal) / (Fintype.card ι : ENNReal)) ^ t :=
le_of_eq (prob_uniform_pi_mem_finset_eq A t)
end UniformProductBound
end Probability
Source