Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ToMathlib.ProbabilityTheory.SPMF.part0

Definition
Yukon_0169f95fdb4d5928b3998f5a

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

better-codes

Source module ToMathlib.ProbabilityTheory.SPMF. 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/VCV-io/blob/446baa72bb7d4296d6f6b7015fd6c15ca9c678b7/ToMathlib/ProbabilityTheory/SPMF.lean

Definition code
/-
Copyright (c) 2025 Devon Tuma. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Devon Tuma
-/
module

public import Mathlib.Probability.ProbabilityMassFunction.Monad
public import Batteries.Control.AlternativeMonad
public import Definitions.Def_Yukon_2a6b3412af2af8cd7980168b

public import Definitions.Def_Yukon_ec6e56db18cc5472c07c58c9



public import Mathlib.Probability.Distributions.Uniform
public import Mathlib.Data.Vector.Defs
public import Mathlib.Data.Finset.Card
public import Init
public import Mathlib.CategoryTheory.Monad.Types
public import Mathlib.Order.CompleteLattice.Basic
meta import Definitions.Def_Yukon_2a6b3412af2af8cd7980168b
meta import Definitions.Def_Yukon_ec6e56db18cc5472c07c58c9
set_option backward.isDefEq.respectTransparency.types false
/-!
# Sub-Probability Distributions

This file defines a type `SPMF` as a `PMF` extended with the option to fail.
The probability of failure is the missing mass to make the `PMF` sum to `1`.
-/

@[expose] public section

open ENNReal

attribute [simp] PMF.coe_le_one PMF.apply_ne_top

universe u v w

variable {α β γ : Type u}

namespace PMF

/-- A PMF that is zero at all points except `a` equals `PMF.pure a`. -/
lemma eq_pure_of_forall_ne_eq_zero {γ : Type*} (p : PMF γ) (a : γ)
    (h : ∀ x, x ≠ a → p x = 0) : p = PMF.pure a := by
  ext x; by_cases hx : x = a
  · subst hx; simp only [PMF.pure_apply, if_true]
    rw [← p.tsum_coe]; exact (tsum_eq_single x (fun b hb => h b hb)).symm
  · simp [PMF.pure_apply, hx, h x hx]

/-- `PMF.bind` respects equality on the support. -/
protected lemma bind_congr {γ δ : Type*} (p : PMF γ) (f g : γ → PMF δ)
    (h : ∀ x, p x ≠ 0 → f x = g x) : p.bind f = p.bind g := by
  ext y; simp only [PMF.bind_apply]; congr 1; ext x
  by_cases hx : p x = 0 <;> simp [hx, h x]

/-- If `PMF.map f c = PMF.pure b` and `f a ≠ b`, then `c a = 0`. -/
lemma map_eq_pure_zero {γ δ : Type*} (f : γ → δ) (c : PMF γ) (b : δ)
    (h : PMF.map f c = PMF.pure b) (a : γ) (ha : f a ≠ b) : c a = 0 := by
  have key := congr_fun (congrArg DFunLike.coe h) (f a)
  simp only [map_apply, pure_apply, ha, ↓reduceIte, ENNReal.tsum_eq_zero, ite_eq_right_iff] at key
  exact key a rfl

end PMF

/-- A subprobability mass function is a function `α → ℝ≥0∞` such that values have an infinite
sum at most `1` represented by applying an `OptionT` transformer to the `PMF` monad.
The new `failure`/`none` value holds the "missing" mass to reach the total sum of `1`. -/
def SPMF : Type u → Type u := OptionT PMF

/-- View a distribution on `Option α` as a subdistribution on `α`,
where `none` is corresponds to the missing mass. -/
protected def SPMF.mk (p : PMF (Option α)) : SPMF α := OptionT.mk p

/-- View a subdistribution on `α` as a distribution on `Option α`. -/
protected def SPMF.toPMF (p : SPMF α) : PMF (Option α) := OptionT.run p

namespace SPMF

@[simp] lemma run_eq_toPMF (p : SPMF α) : p.run = p.toPMF := rfl

@[simp] lemma toPMF_mk (p : PMF (Option α)) : (SPMF.mk p).toPMF = p := rfl

@[simp] lemma mk_toPMF (p : SPMF α) : SPMF.mk p.toPMF = p := rfl

/-- Expose the induced monad instance on `SPMF`. -/
noncomputable instance  _root_.SPMF.instAlternativeMonad : AlternativeMonad SPMF := OptionT.instAlternativeMonadOfMonad PMF
noncomputable instance  _root_.SPMF.instLawfulAlternative : LawfulAlternative SPMF := OptionT.instLawfulAlternativeOfLawfulMonad PMF
noncomputable instance  _root_.SPMF.instLawfulMonad : LawfulMonad SPMF := OptionT.instLawfulMonad

/-- Expose the lifting operations from `PMF` to `SPMF` given by `OptionT.lift`. -/
noncomputable instance  _root_.SPMF.instMonadLiftPMF : MonadLift PMF SPMF where monadLift := OptionT.lift
instance  _root_.SPMF.instLawfulMonadLiftPMF : LawfulMonadLift PMF SPMF := OptionT.instLawfulMonadLift

/-- Apply an `SPMF α` to an element of `α`. -/
instance  _root_.SPMF.instFunLikeENNReal : FunLike (SPMF α) α ENNReal where
  coe p x := OptionT.run p (some x)
  coe_injective _ _ h := OptionT.ext (PMF.ext_forall_ne none fun | some x, _ => congr_fun h x)

@[aesop safe norm, grind =] -- TODO: decide if this should be a simp
lemma apply_eq_toPMF_some (p : SPMF α) (x : α) : p x = p.toPMF (some x) := rfl

@[grind =]
lemma liftM_eq_map (p : PMF α) : (liftM p : SPMF α) = SPMF.mk (p.map Option.some) := rfl

@[simp, grind =]
lemma lift_pure (x : α) : (liftM (PMF.pure x) : SPMF α) = pure x := by
  simp [← PMF.monad_pure_eq_pure]

@[simp, grind =]
lemma toPMF_liftM (p : PMF α) : (liftM p : SPMF α).toPMF = p := rfl

@[simp, grind =]
lemma liftM_apply (p : PMF α) (x : α) : (liftM p : SPMF α) x = p x := by
  simp only [apply_eq_toPMF_some, toPMF_liftM, PMF.monad_pure_eq_pure, PMF.monad_bind_eq_bind,
    PMF.bind_apply, PMF.pure_apply, Option.some.injEq, mul_ite, mul_one, mul_zero]
  refine (tsum_eq_single x ?_).trans ?_ <;> aesop

@[simp, grind =]
lemma toPMF_pure (x : α) : (pure x : SPMF α).toPMF = PMF.pure (some x) := rfl

lemma failure_eq_mk : (failure : SPMF α) = SPMF.mk (PMF.pure none) := rfl

@[simp, grind =]
lemma toPMF_failure : (failure : SPMF α).toPMF = PMF.pure none := rfl

@[simp, grind =]
lemma failure_apply (x : α) : (failure : SPMF α) x = 0 := by aesop

section zero

noncomputable instance  _root_.SPMF.instZero : Zero (SPMF α) where zero := failure

lemma zero_def : (0 : SPMF α) = failure := rfl

@[simp, grind =]
lemma toPMF_zero : (0 : SPMF α).toPMF = PMF.pure none := rfl

@[simp, grind =]
lemma zero_apply (x : α) : (0 : SPMF α) x = 0 := by aesop

end zero

@[simp, grind =]
lemma toPMF_bind (p : SPMF α) (q : α → SPMF β) :
    (p >>= q).toPMF = Option.elimM p.toPMF (PMF.pure none) (fun x => (q x).toPMF) := by
  simp only [SPMF, ← run_eq_toPMF, OptionT.run_bind, PMF.monad_pure_eq_pure]

@[simp, grind =]
lemma toPMF_map (p : SPMF α) (f : α → β) : (f <$> p).toPMF = Option.map f <$> p.toPMF := by
  simp [SPMF, ← run_eq_toPMF]

@[simp, grind =]
lemma mk_pure_some (x : α) : SPMF.mk (PMF.pure (some x)) = pure x := rfl

@[simp, grind =]
lemma tsum_toPMF_some_add_toPMF_none (p : SPMF α) :
    (∑' x, p.toPMF (some x)) + p.toPMF none = 1 := by
  rw [add_comm, ← tsum_option _ ENNReal.summable, p.toPMF.tsum_coe]

@[simp, grind =]
lemma run_none_add_tsum_run_some (p : SPMF α) :
    p.toPMF none + (∑' x, p.toPMF (some x)) = 1 := by
  rw [← tsum_option _ ENNReal.summable, p.toPMF.tsum_coe]

lemma tsum_run_some_eq_one_sub (p : SPMF α) :
    ∑' x, p.toPMF (some x) = 1 - p.toPMF none := by
  rw [← tsum_toPMF_some_add_toPMF_none p]
  refine ENNReal.eq_sub_of_add_eq' (by simp) rfl

@[grind =]
lemma toPMF_none_eq_one_sub_tsum (p : SPMF α) :
    p.toPMF none = 1 - ∑' x, p.toPMF (some x) := by
  rw [← run_none_add_tsum_run_some p]
  refine ENNReal.eq_sub_of_add_eq' (by simp) rfl

@[simp, grind .] lemma apply_ne_top (p : SPMF α) (x : α) : p x ≠ ⊤ := by aesop

@[simp] lemma tsum_run_some_ne_top (p : SPMF α) : ∑' x, p.toPMF (some x) ≠ ⊤ :=
  ne_top_of_le_ne_top one_ne_top (p.tsum_run_some_eq_one_sub ▸ tsub_le_self)

@[ext]
lemma ext {p q : SPMF α} (h : ∀ x : α, p x = q x) : p = q := by
  simp only [apply_eq_toPMF_some] at h
  refine PMF.ext fun
    | some x => h x
    | none =>  calc p.toPMF none
        _ = 1 - ∑' x, p.toPMF (some x) := by grind
        _ = 1 - ∑' x, q.toPMF (some x) := by simp [h]
        _ = q.toPMF none := by grind

open Classical in
lemma eq_liftM_iff_forall (p : SPMF α) (q : PMF α) :
    p = liftM q ↔ ∀ x, p x = q x := by
  simp [SPMF.ext_iff]

@[simp] lemma pure_apply [DecidableEq α] (x y : α) :
    (pure x : SPMF α) y = if y = x then 1 else 0 := by aesop

@[simp] lemma pure_apply_self (x : α) :
    (pure x : SPMF α) x = 1 := by aesop

@[simp] lemma pure_apply_eq_zero_iff (x y : α) :
    (pure x : SPMF α) y = 0 ↔ y ≠ x := by aesop

@[simp] lemma bind_apply_eq_tsum (p : SPMF α) (q : α → SPMF β) (y : β) :
    (p >>= q) y = ∑' x, p x * q x y := by
  erw [PMF.bind_apply, tsum_option _ ENNReal.summable]
  simp
  rfl

section support

/-- The set of outputs with non-zero probability mass. -/
protected def support {α : Type*} (p : SPMF α) : Set α :=
  Function.support (p : α → ℝ≥0∞)

lemma support_def (p : SPMF α) :
    SPMF.support p = Function.support p := rfl

@[grind =]
lemma support_eq_preimage_some (p : SPMF α) :
    p.support = some ⁻¹' p.toPMF.support := by
  ext x
  simp only [Set.mem_preimage, PMF.mem_support_iff, SPMF.support,
    Function.mem_support, apply_eq_toPMF_some]

@[simp, grind =]
lemma mem_support_iff (p : SPMF α) (x : α) : x ∈ p.support ↔ p x ≠ 0 := by aesop

@[simp, grind =]
lemma support_liftM (p : PMF α) : (liftM p : SPMF α).support = p.support := by aesop

@[simp, grind =]
lemma support_pure (x : α) : (pure x : SPMF α).support = {x} := by aesop

@[simp, grind =]
lemma support_bind (p : SPMF α) (q : α → SPMF β) :
    (p >>= q).support = ⋃ x ∈ p.support, (q x).support := by
  ext y
  simp only [SPMF.mem_support_iff, bind_apply_eq_tsum, Set.mem_iUnion, exists_prop, ne_eq]
  rw [ENNReal.tsum_eq_zero, not_forall]
  constructor
  · rintro ⟨x, hx⟩
    rw [mul_eq_zero, not_or] at hx
    exact ⟨x, hx.1, hx.2⟩
  · rintro ⟨x, hpx, hqxy⟩
    exact ⟨x, by rw [mul_eq_zero, not_or]; exact ⟨hpx, hqxy⟩⟩

end support

section gap

/-- Gap between the total mass of `p : SPMF` and `1`, so `∑ x, p x + p.gap = 1`.
TODO: use this to simplify the API around failure and needing `toPMF`/`run`. -/
def gap (p : SPMF α) : ℝ≥0∞ := p.toPMF none

@[grind =]
lemma gap_eq_toPMF_none (p : SPMF α) : p.gap = p.toPMF none := rfl

@[grind =]
lemma gap_eq_one_sub_tsum (p : SPMF α) : p.gap = 1 - ∑' x : α, p x := by grind

@[grind =]
lemma toReal_gap_eq_one_sub_sum_toReal [Fintype α] (p : SPMF α) :
    p.gap.toReal = 1 - ∑ x : α, (p x).toReal := by
  simp only [gap_eq_one_sub_tsum, tsum_fintype]
  rw [ENNReal.toReal_sub_of_le]
  · simp only [toReal_one, _root_.sub_right_inj]
    rw [ENNReal.toReal_sum]
    simp
  · refine le_of_le_of_eq ?_ (run_none_add_tsum_run_some p)
    simp [SPMF.apply_eq_toPMF_some]
  · simp

end gap

@[simp] lemma map_mk (p : PMF (Option α)) (f : α → β) :
    f <$> SPMF.mk p = SPMF.mk (Option.map f <$> p) := by aesop

theorem bind_eq_pmf_bind {p : SPMF α} {f : α → SPMF β} :
    (p >>= f) = PMF.bind p (fun a => match a with | some a' => f a' | none => PMF.pure none) := by
  simp [bind, OptionT.bind, OptionT.mk]
  rfl

@[simp] lemma PMF.map_some_apply_some (p : PMF α) (x : α) : (some <$> p) (some x) = p x := by
  simp [PMF.monad_map_eq_map]

/-- `pure a` in `SPMF` equals `PMF.pure (some a)` as a PMF on `Option α`. -/
protected lemma pure_eq_pure_some (a : α) :
    (pure a : SPMF α) = SPMF.mk (PMF.pure (some a)) := rfl

@[simp, grind =]
lemma toPMF_inj (p q : SPMF α) : p.toPMF = q.toPMF ↔ p = q := by aesop

/-- The functor map for SPMF equals `PMF.map (Option.map f)`. -/
protected lemma fmap_eq_map (f : α → β) (c : SPMF α) :
    (f <$> c : SPMF β) = (PMF.map (Option.map f) c) :=
  show (f <$> c : SPMF β) = SPMF.mk (PMF.map (Option.map f) c.toPMF)
  by rw [← SPMF.toPMF_inj, SPMF.toPMF_map, SPMF.toPMF_mk, PMF.monad_map_eq_map]

end SPMF


Source
https://github.com/Verified-zkEVM/VCV-io/blob/446baa72bb7d4296d6f6b7015fd6c15ca9c678b7/ToMathlib/ProbabilityTheory/SPMF.lean yukon-proof-operation:8696ce32fea3c6b246cf414ecc66cf3984d31632032865c2000ed86cb0d3d930 [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246ODY5NmNlMzJmZWEzYzZiMjQ2Y2Y0MTRlY2M2NmNmMzk4NGQzMTYzMjAzMjg2NWMyMDAwZWQ4NmNiMGQzZDkzMCIsImhhc2giOiI4YWVjNGQwY2M4ZDc5MTIyZDgzZWU1ZjI4YmEzYjljNjM0NmFlNmVjOTQ2ZTRkNDZkZDgxNDMzNjc2YTZjYWFlIiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl8wMTY5Zjk1ZmRiNGQ1OTI4YjM5OThmNWEiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

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