Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ToMathlib.ProbabilityTheory.FinRatPMF.part0

Definition
Yukon_2a2d046c1b983c45670d8b9f

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

better-codes

Source module ToMathlib.ProbabilityTheory.FinRatPMF.

Definition code
/-
Copyright (c) 2025 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.Probability.Distributions.Uniform
public import Mathlib.Data.DFinsupp.BigOperators
public import Mathlib.Data.FinEnum
public import Mathlib.Data.NNRat.BigOperators
public import Std.Data.HashMap.Lemmas
public import Definitions.Def_Yukon_2a6b3412af2af8cd7980168b



public import Mathlib.CategoryTheory.Monad.Types
public import Mathlib.Order.CompleteLattice.Basic
public import Init
public import Mathlib.Probability.ProbabilityMassFunction.Monad
meta import Definitions.Def_Yukon_2a6b3412af2af8cd7980168b
set_option backward.isDefEq.respectTransparency.types false
/-!
# Probability mass functions with finite support and non-negative rational weights

This is a special case of `PMF` that suffices for denotational semantics of `OracleComp` with finite
oracle specifications.

## Design

We use a two-layer approach:

* `FinRatPMF.Raw α` is an array-based representation storing pairs `(a, p)` of outcomes and
  probabilities. It has a computable `Monad` and `LawfulMonad` instance but non-canonical equality:
  two values representing the same distribution may differ in array order or duplicate entries.

* `FinRatPMF α` is the quotient of `FinRatPMF.Raw α` by distributional equality (`SameDist`).
  It has canonical equality (two values are equal iff they define the same distribution) and a
  `LawfulMonad` instance (necessarily `noncomputable` since `bind` must extract from the quotient).

For computation, use `FinRatPMF.Raw`. For reasoning about distributional equality, use `FinRatPMF`.
Both connect to Mathlib's `PMF` via `toPMF`.
-/

@[expose] public section

universe u

namespace FinRatPMF

/-! ## Raw representation -/

/-- Raw probability mass function with finite support and non-negative rational weights.

Stores an array of `(outcome, weight)` pairs whose weights sum to `1`. This representation is
computable but not canonical: many different `FinRatPMF.Raw` values can represent the same
probability distribution. -/
structure Raw (α : Type u) : Type u where
  data : Array (α × ℚ≥0)
  sum_eq_one : (data.toList.map Prod.snd).sum = 1

namespace Raw

variable {α β γ : Type u}

/-- View the raw array representation as a list, which is convenient for proofs. -/
def toList (p : Raw α) : List (α × ℚ≥0) := p.data.toList

def probOfList [DecidableEq α] (l : List (α × ℚ≥0)) (x : α) : ℚ≥0 :=
  (l.filter (fun a => a.1 = x) |>.map Prod.snd).sum

def supportOfList [DecidableEq α] (l : List (α × ℚ≥0)) : Finset α :=
  (l.filter (fun a => a.2 ≠ 0)).map Prod.fst |>.toFinset

private lemma sum_eq_zero_of_forall_eq_zero (l : List ℚ≥0)
    (h : ∀ q ∈ l, q = 0) : l.sum = 0 := by
  induction l with
  | nil => simp
  | cons q qs ih =>
    simp [h q (by simp), ih (by
      intro r hr
      exact h r (by simp [hr]))]

private lemma probOfList_ne_zero_of_mem [DecidableEq α] {l : List (α × ℚ≥0)} {x : α} {q : ℚ≥0}
    (hmem : (x, q) ∈ l) (hq : q ≠ 0) : probOfList l x ≠ 0 := by
  have hqmem : q ∈ (l.filter (fun a => a.1 = x)).map Prod.snd := by
    apply List.mem_map.2
    refine ⟨(x, q), ?_, rfl⟩
    simpa using hmem
  have hle : q ≤ probOfList l x := by
    simpa [probOfList] using
      (List.single_le_sum (fun _ _ => by exact zero_le) q hqmem)
  exact (lt_of_lt_of_le (show 0 < q from pos_iff_ne_zero.mpr hq) hle).ne'

private lemma probOfList_eq_zero_of_not_mem_supportOfList [DecidableEq α]
    (l : List (α × ℚ≥0)) {x : α} (hx : x ∉ supportOfList l) : probOfList l x = 0 := by
  simp only [supportOfList, List.mem_toFinset, List.mem_map, List.mem_filter] at hx
  unfold probOfList
  apply sum_eq_zero_of_forall_eq_zero
  intro q hq
  rcases List.mem_map.1 hq with ⟨a, ha, rfl⟩
  have ha' : a ∈ l.filter (fun b => b.1 = x) := ha
  simp only [List.mem_filter] at ha'
  have hzero : a.2 = 0 := by
    by_contra hne
    exact hx ⟨a, ⟨ha'.1, by simpa using hne⟩, by simpa using ha'.2⟩
  exact hzero

private lemma mem_supportOfList_iff [DecidableEq α] (l : List (α × ℚ≥0)) (x : α) :
    x ∈ supportOfList l ↔ probOfList l x ≠ 0 := by
  constructor
  · intro hx
    rcases List.mem_toFinset.1 hx with hx
    rcases List.mem_map.1 hx with ⟨a, ha, hax⟩
    rcases List.mem_filter.1 ha with ⟨ha, hne⟩
    subst x
    exact probOfList_ne_zero_of_mem ha (by simpa using hne)
  · intro hx
    by_contra hnot
    exact hx (probOfList_eq_zero_of_not_mem_supportOfList l hnot)

private lemma supportOfList_eq_keys [DecidableEq α] {l : List (α × ℚ≥0)}
    (h : ∀ a ∈ l, a.2 ≠ 0) :
    supportOfList l = (l.map Prod.fst).toFinset := by
  ext x
  constructor
  · intro hx
    rcases List.mem_toFinset.1 hx with hx
    rcases List.mem_map.1 hx with ⟨a, ha, hax⟩
    rcases List.mem_filter.1 ha with ⟨ha, _⟩
    exact List.mem_toFinset.2 (List.mem_map.2 ⟨a, ha, hax⟩)
  · intro hx
    rcases List.mem_toFinset.1 hx with hx
    rcases List.mem_map.1 hx with ⟨a, ha, hax⟩
    subst x
    exact List.mem_toFinset.2
      (List.mem_map.2 ⟨a, List.mem_filter.2 ⟨ha, by simpa using h a ha⟩, rfl⟩)

@[ext] lemma ext {p q : Raw α} (h : p.data = q.data) : p = q := by
  cases p
  cases q
  cases h
  simp

lemma ext_toList {p q : Raw α} (h : p.toList = q.toList) : p = q := by
  apply ext
  simpa [Raw.toList] using congrArg List.toArray h

/-! ### Bind sum auxiliary lemma -/

private lemma bind_sum_aux (l : List (α × ℚ≥0)) (g : α → Raw β) :
    ((l.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q)))).map Prod.snd).sum
    = (l.map (fun (a, p) => p * ((g a).toList.map Prod.snd).sum)).sum := by
  induction l with
  | nil => simp
  | cons hd tl ih =>
    simp only [List.flatMap_cons, List.map_append, List.sum_append, List.map_cons,
      List.sum_cons, List.map_map, Function.comp_def]
    rw [List.sum_map_mul_left]
    congr 1

/-! ### Monad operations -/

protected def pure (a : α) : Raw α := ⟨#[(a, 1)], by simp⟩

instance  _root_.FinRatPMF.Raw.instInhabited [Inhabited α] : Inhabited (Raw α) where
  default := Raw.pure default

instance  _root_.FinRatPMF.Raw.instRepr [Repr α] : Repr (Raw α) where
  reprPrec p _ := repr (p.toList.map fun (a, q) => (reprStr a, (q : ℚ)))

instance  _root_.FinRatPMF.Raw.instToStringOfRepr [Repr α] : ToString (Raw α) where
  toString p := reprStr (p.toList.map fun (a, q) => (reprStr a, (q : ℚ)))

protected def bind (f : Raw α) (g : α → Raw β) : Raw β :=
  ⟨(f.toList.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q)))).toArray, by
    change ((f.toList.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q)))).map
      Prod.snd).sum = 1
    rw [bind_sum_aux]
    simp only [Raw.toList]
    simp_rw [Raw.sum_eq_one, mul_one]
    exact f.sum_eq_one⟩

instance  _root_.FinRatPMF.Raw.instMonad : Monad Raw where
  pure := Raw.pure
  bind := Raw.bind

@[simp] lemma pure_toList (a : α) :
    (Pure.pure a : Raw α).toList = [(a, 1)] := rfl

@[simp] lemma bind_toList (f : Raw α) (g : α → Raw β) :
    (f >>= g).toList =
      f.toList.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q))) := by
  change
    ((f.toList.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q)))).toArray).toList
      = _
  rw [List.toList_toArray]

instance  _root_.FinRatPMF.Raw.instLawfulMonad : LawfulMonad Raw := LawfulMonad.mk'
  (id_map := fun x => by
    apply ext_toList
    simp [Functor.map, Raw.bind, Raw.pure, Raw.toList])
  (pure_bind := fun x f => by
    apply ext_toList
    simp)
  (bind_assoc := fun m f g => by
    apply ext_toList
    simp [List.flatMap_assoc, List.map_flatMap, List.flatMap_map, List.map_map,
      Function.comp_def, mul_assoc])
  (bind_pure_comp := fun f x => by
    cases x
    rfl)

private lemma sum_replicate_inv_length_eq_one (n : ℕ) (hn : n ≠ 0) :
    (List.replicate n ((n : ℚ≥0)⁻¹)).sum = 1 := by
  rw [List.sum_replicate, nsmul_eq_mul, mul_inv_cancel₀]
  exact_mod_cast hn

/-- Uniform distribution over a nonempty list, treating repeated entries as repeated tickets. -/
protected def uniformList (l : List α) (hl : l ≠ []) : Raw α :=
  let w : ℚ≥0 := (l.length : ℚ≥0)⁻¹
  ⟨(l.map fun a => (a, w)).toArray, by
    have hlen : l.length ≠ 0 := by
      intro hlen
      exact hl (List.eq_nil_iff_length_eq_zero.2 hlen)
    have hmap : List.map Prod.snd (List.map (fun a => (a, w)) l) = List.replicate l.length w := by
      simp [Function.comp_def]
    rw [show (((l.map (fun a => (a, w))).toArray.toList.map Prod.snd).sum) =
        (List.map Prod.snd (List.map (fun a => (a, w)) l)).sum by rw [List.toList_toArray],
      hmap]
    simpa [w] using sum_replicate_inv_length_eq_one l.length hlen⟩

/-- Uniform distribution over a finite inhabited type. -/
protected def uniform [FinEnum α] [Inhabited α] : Raw α :=
  Raw.uniformList (FinEnum.toList α) <| by
    intro hnil
    have hmem : default ∈ FinEnum.toList α := FinEnum.mem_toList default
    simp [hnil] at hmem

/-- Fair coin. -/
protected def coin : Raw Bool :=
  Raw.uniformList [true, false] (by simp)

/-- Bernoulli distribution with probability `p` of `true`. -/
protected def bernoulli (p : ℚ≥0) (hp : p ≤ 1) : Raw Bool :=
  ⟨#[(true, p), (false, 1 - p)], by
    simp [add_tsub_cancel_of_le hp]⟩

/-! ### Probability and support -/

/-- The probability assigned to `x` by the raw PMF: sum of weights for all entries with key `x`. -/
def prob [DecidableEq α] (p : Raw α) (x : α) : ℚ≥0 :=
  probOfList p.toList x

/-- `prob` is independent of the `DecidableEq` instance, since `decide (a = b)` gives the same
`Bool` for any `Decidable` instance on the same `Prop`. -/
lemma prob_eq_prob (inst1 inst2 : DecidableEq α) (p : Raw α) (x : α) :
    @prob _ inst1 p x = @prob _ inst2 p x := by
  unfold prob probOfList
  have hpred :
      (fun a : α × ℚ≥0 => @decide (a.1 = x) (inst1 a.1 x)) =
      fun a : α × ℚ≥0 => @decide (a.1 = x) (inst2 a.1 x) := by
    funext a
    cases inst1 a.1 x <;> cases inst2 a.1 x <;> simp_all
  simp [hpred]

/-- The finite support: the set of outcomes appearing in the array. -/
def support [DecidableEq α] (p : Raw α) : Finset α :=
  supportOfList p.toList

lemma prob_eq_zero_of_not_mem_support [DecidableEq α] (p : Raw α) {x : α}
    (hx : x ∉ p.support) : p.prob x = 0 := by
  simpa [prob, support] using probOfList_eq_zero_of_not_mem_supportOfList p.toList hx

lemma mem_support_iff [DecidableEq α] (p : Raw α) (x : α) :
    x ∈ p.support ↔ p.prob x ≠ 0 := by
  simpa [prob, support] using mem_supportOfList_iff p.toList x

private lemma filter_cons_sum [DecidableEq α] (hd : α × ℚ≥0) (tl : List (α × ℚ≥0)) (x : α) :
    ((hd :: tl).filter (fun a => a.1 = x) |>.map Prod.snd).sum =
    (if hd.1 = x then hd.2 else 0) +
    (tl.filter (fun a => a.1 = x) |>.map Prod.snd).sum := by
  simp only [List.filter_cons, decide_eq_true_eq]
  split <;> simp_all [List.map_cons, List.sum_cons]

private lemma list_prob_eq_zero [DecidableEq α] {l : List (α × ℚ≥0)} {x : α}
    (hx : x ∉ (l.map Prod.fst).toFinset) :
    (l.filter (fun a => a.1 = x) |>.map Prod.snd).sum = 0 := by
  suffices l.filter (fun a => a.1 = x) = [] by simp [this]
  rw [List.filter_eq_nil_iff]
  simp only [List.mem_toFinset, List.mem_map] at hx
  exact fun a ha => by simp only [decide_eq_true_eq]; intro heq; exact hx ⟨a, ha, heq ▸ rfl⟩

private lemma list_sum_prob_eq [DecidableEq α] (l : List (α × ℚ≥0)) :
    (l.map Prod.fst |>.toFinset).sum
      (fun x => (l.filter (fun a => a.1 = x) |>.map Prod.snd).sum) =
    (l.map Prod.snd).sum := by
  induction l with
  | nil => simp
  | cons hd tl ih =>
    simp only [List.map_cons, List.toFinset_cons, List.sum_cons]
    simp_rw [filter_cons_sum, Finset.sum_add_distrib]
    congr 1
    · simp
    · by_cases hm : hd.1 ∈ (tl.map Prod.fst).toFinset
      · rw [Finset.insert_eq_of_mem hm]; exact ih
      · rw [Finset.sum_insert hm, list_prob_eq_zero hm, zero_add]; exact ih

/-- Sum of `prob` over the support recovers the total weight. -/
lemma sum_prob_eq_sum [DecidableEq α] (p : Raw α) :
    p.support.sum p.prob = (p.toList.map Prod.snd).sum := by
  let s : Finset α := p.toList.map Prod.fst |>.toFinset
  have hs : p.support ⊆ s := by
    intro x hx
    rcases List.mem_toFinset.1 hx with hx
    rcases List.mem_map.1 hx with ⟨a, ha, hax⟩
    rcases List.mem_filter.1 ha with ⟨ha, _⟩
    exact List.mem_toFinset.2 (List.mem_map.2 ⟨a, ha, hax⟩)
  calc
    p.support.sum p.prob = s.sum p.prob :=
      Finset.sum_subset hs (by
        intro x _ hx
        exact prob_eq_zero_of_not_mem_support p hx)
    _ = (p.toList.map Prod.snd).sum := by
      simpa [s, prob, probOfList] using list_sum_prob_eq p.toList

lemma sum_prob_eq_one [DecidableEq α] (p : Raw α) : p.support.sum p.prob = 1 := by
  rw [sum_prob_eq_sum]
  simpa [Raw.toList] using p.sum_eq_one

@[simp] lemma prob_pure [DecidableEq α] (a x : α) :
    (Raw.pure a).prob x = if x = a then 1 else 0 := by
  unfold Raw.prob probOfList Raw.toList Raw.pure
  by_cases h : x = a
  · simp [h]
  · have h' : ¬ a = x := by simpa [eq_comm] using h
    simp [h, h']

@[simp] lemma support_pure [DecidableEq α] (a : α) :
    (Raw.pure a).support = {a} := by
  ext x
  by_cases h : x = a
  · subst h
    simp [mem_support_iff]
  · simp [mem_support_iff, prob_pure, h]

private lemma probOfList_map_const_eq_length_filter [DecidableEq α]
    (l : List α) (w : ℚ≥0) (x : α) :
    probOfList (l.map fun a => (a, w)) x = ((l.filter fun a => a = x).length : ℚ≥0) * w := by
  induction l with
  | nil => simp [probOfList]
  | cons a tl ih =>
    by_cases h : a = x
    · subst h
      rw [show probOfList (List.map (fun b => (b, w)) (a :: tl)) a =
          w + probOfList (List.map (fun b => (b, w)) tl) a by
            unfold probOfList
            simp]
      rw [ih]
      simp [add_mul, add_comm]
    · rw [show probOfList (List.map (fun b => (b, w)) (a :: tl)) x =
          probOfList (List.map (fun b => (b, w)) tl) x by
            unfold probOfList
            simp [h]]
      rw [ih]
      simp [h]

private lemma filter_eq_singleton_of_nodup [DecidableEq α] {l : List α} (hnd : l.Nodup)
    {x : α} (hx : x ∈ l) : l.filter (fun a => a = x) = [x] := by
  induction l with
  | nil => cases hx
  | cons a tl ih =>
    rw [List.nodup_cons] at hnd
    rcases hnd with ⟨hatl, hndtl⟩
    by_cases hax : a = x
    · subst hax
      have hnot : a ∉ tl := by
        simpa using hatl
      have hnil : tl.filter (fun y => y = a) = [] := by
        apply List.filter_eq_nil_iff.2
        intro y hy
        simp only [decide_eq_true_eq]
        intro hya
        exact hnot (hya.symm ▸ hy)
      simp [hnil]
    · have hx' : x ∈ tl := by
        cases hx with
        | head => exact False.elim (hax rfl)
        | tail _ hx' => exact hx'
      simp only [hax, decide_false, Bool.false_eq_true, not_false_eq_true, List.filter_cons_of_neg]
      exact ih hndtl hx'

/-- Point probabilities for `uniformList` on a duplicate-free list. -/
lemma prob_uniformList_of_nodup [DecidableEq α] {l : List α} (hl : l ≠ []) (hnd : l.Nodup)
    (x : α) :
    (Raw.uniformList l hl).prob x = if x ∈ l then (l.length : ℚ≥0)⁻¹ else 0 := by
  have htoList :
      (Raw.uniformList l hl).toList = l.map fun a => (a, ((l.length : ℚ≥0)⁻¹)) := by
    simp [Raw.uniformList, Raw.toList]
  rw [Raw.prob, htoList, probOfList_map_const_eq_length_filter]
  by_cases hx : x ∈ l
  · rw [if_pos hx, filter_eq_singleton_of_nodup hnd hx]
    simp
  · rw [if_neg hx]
    have hnil : l.filter (fun a => a = x) = [] := by
      apply List.filter_eq_nil_iff.2
      intro y hy
      simp only [decide_eq_true_eq]
      intro hyx
      exact hx (hyx ▸ hy)
    simp [hnil]

/-- Uniform distributions over duplicate-free lists have support exactly the listed elements. -/
lemma support_uniformList_of_nodup [DecidableEq α] {l : List α} (hl : l ≠ []) (hnd : l.Nodup) :
    (Raw.uniformList l hl).support = l.toFinset := by
  ext x
  rw [Raw.mem_support_iff, prob_uniformList_of_nodup hl hnd]
  by_cases hx : x ∈ l
  · simp [hx, hl]
  · simp [hx]

/-- Point probabilities of `Raw.uniform`. -/
@[simp] lemma prob_uniform [FinEnum α] [Inhabited α] (x : α) :
    (Raw.uniform (α := α)).prob x = (Fintype.card α : ℚ≥0)⁻¹ := by
  have hl : FinEnum.toList α ≠ [] := by
    intro hnil
    have hmem : default ∈ FinEnum.toList α := FinEnum.mem_toList default
    simp [hnil] at hmem
  rw [Raw.uniform, prob_uniformList_of_nodup hl FinEnum.nodup_toList,
    if_pos (FinEnum.mem_toList x)]
  congr 1

/-- `Raw.uniform` has full finite support. -/
@[simp] lemma support_uniform [DecidableEq α] [FinEnum α] [Inhabited α] :
    (Raw.uniform (α := α)).support = Finset.univ := by
  classical
  ext x
  simp only [Finset.mem_univ, iff_true, Raw.mem_support_iff]
  have hcard : (Fintype.card α : ℚ≥0) ≠ 0 := by
    exact_mod_cast (Fintype.card_ne_zero : Fintype.card α ≠ 0)
  have hprob : (Raw.uniform (α := α)).prob x = (Fintype.card α : ℚ≥0)⁻¹ := by
    calc
      (Raw.uniform (α := α)).prob x
          = @Raw.prob _ (FinEnum.decEq) (Raw.uniform (α := α)) x :=
              Raw.prob_eq_prob inferInstance (FinEnum.decEq) (Raw.uniform (α := α)) x
      _ = (Fintype.card α : ℚ≥0)⁻¹ := prob_uniform (α := α) x
  simp [hprob]

/-- Point probabilities of `Raw.coin`. -/
@[simp] lemma prob_coin (b : Bool) : Raw.coin.prob b = 2⁻¹ := by
  simpa [Raw.coin] using
    prob_uniformList_of_nodup (α := Bool) (l := [true, false]) (by simp)
      (by simp) b

@[simp] lemma support_coin : Raw.coin.support = {true, false} := by
  simpa [Raw.coin] using
    support_uniformList_of_nodup (α := Bool) (l := [true, false]) (by simp) (by simp)

@[simp] lemma prob_bernoulli_true (p : ℚ≥0) (hp : p ≤ 1) :
    (Raw.bernoulli p hp).prob true = p := by
  unfold Raw.bernoulli Raw.prob probOfList Raw.toList
  simp

@[simp] lemma prob_bernoulli_false (p : ℚ≥0) (hp : p ≤ 1) :
    (Raw.bernoulli p hp).prob false = 1 - p := by
  unfold Raw.bernoulli Raw.prob probOfList Raw.toList
  simp

lemma prob_le_one [DecidableEq α] (p : Raw α) (x : α) : p.prob x ≤ 1 := by
  by_cases hx : x ∈ p.support
  · calc
      p.prob x ≤ p.support.sum p.prob := Finset.single_le_sum (fun _ _ => by exact zero_le ) hx
      _ = 1 := sum_prob_eq_one p
  · simp [prob_eq_zero_of_not_mem_support p hx]

private lemma probOfList_append [DecidableEq α] (l₁ l₂ : List (α × ℚ≥0)) (x : α) :
    probOfList (l₁ ++ l₂) x = probOfList l₁ x + probOfList l₂ x := by
  unfold probOfList
  rw [List.filter_append, List.map_append, List.sum_append]

private lemma filter_map_mul_eq [DecidableEq α] (l : List (α × ℚ≥0)) (p : ℚ≥0) (x : α) :
    (l.map (fun (a, q) => (a, p * q))).filter (fun a => a.1 = x) =
      (l.filter (fun a => a.1 = x)).map (fun (a, q) => (a, p * q)) := by
  induction l with
  | nil => simp
  | cons hd tl ih =>
    by_cases h : hd.1 = x <;> simp [h, ih]

private lemma probOfList_map_mul [DecidableEq α] (l : List (α × ℚ≥0)) (p : ℚ≥0) (x : α) :
    probOfList (l.map fun (a, q) => (a, p * q)) x = p * probOfList l x := by
  unfold probOfList
  rw [filter_map_mul_eq]
  simpa [List.map_map, Function.comp_def] using
    List.sum_map_mul_left ((l.filter fun a => a.1 = x).map Prod.snd) id p

private lemma list_sum_prob_mul_eq [DecidableEq α] (l : List (α × ℚ≥0)) (w : α → ℚ≥0) :
    (l.map Prod.fst |>.toFinset).sum (fun x => probOfList l x * w x) =
    (l.map (fun (a, p) => p * w a)).sum := by
  induction l with
  | nil => simp [probOfList]
  | cons hd tl ih =>
    let s : Finset α := (tl.map Prod.fst).toFinset
    simp only [List.map_cons, List.toFinset_cons, List.sum_cons]
    calc
      (insert hd.1 s).sum (fun x => probOfList (hd :: tl) x * w x)
          = (insert hd.1 s).sum
              (fun x => (((if hd.1 = x then hd.2 else 0) + probOfList tl x) * w x)) := by
                refine Finset.sum_congr rfl ?_
                intro x hx
                have hprob :
                    probOfList (hd :: tl) x = (if hd.1 = x then hd.2 else 0) + probOfList tl x := by
                  simpa [probOfList] using filter_cons_sum hd tl x
                exact congrArg (fun q => q * w x) hprob
      _ = (insert hd.1 s).sum (fun x => (if hd.1 = x then hd.2 else 0) * w x) +
            (insert hd.1 s).sum (fun x => probOfList tl x * w x) := by
        simp_rw [add_mul]
        rw [Finset.sum_add_distrib]
      _ = hd.2 * w hd.1 + (List.map (fun x => x.2 * w x.1) tl).sum := by
        congr 1
        · calc
            (insert hd.1 s).sum (fun x => (if hd.1 = x then hd.2 else 0) * w x)
                = ∑ x ∈ insert hd.1 s, if hd.1 = x then hd.2 * w x else 0 := by
                    simp_rw [ite_mul, zero_mul]
            _ = hd.2 * w hd.1 := by simp
        · by_cases hm : hd.1 ∈ s
          · rw [Finset.insert_eq_of_mem hm]
            exact ih
          · have hzero : probOfList tl hd.1 = 0 := by
              simpa [probOfList] using list_prob_eq_zero hm
            rw [Finset.sum_insert hm, hzero, zero_mul, zero_add]
            exact ih

private lemma probOfList_bind_eq_sum [DecidableEq β]
    (l : List (α × ℚ≥0)) (g : α → Raw β) (y : β) :
    probOfList (l.flatMap (fun (a, p) => (g a).toList.map (fun (b, q) => (b, p * q)))) y =
      (l.map (fun (a, p) => p * (g a).prob y)).sum := by
  induction l with
  | nil => simp [probOfList]
  | cons hd tl ih =>
    rw [List.flatMap_cons, probOfList_append, ih, probOfList_map_mul]
    simp [Raw.prob, Raw.toList]

@[simp] lemma prob_bind [DecidableEq α] [DecidableEq β] (m : Raw α) (f : α → Raw β) (y : β) :
    (m >>= f).prob y = m.support.sum (fun a => m.prob a * (f a).prob y) := by
  let s : Finset α := m.toList.map Prod.fst |>.toFinset
  have hs : m.support ⊆ s := by
    intro x hx
    rcases List.mem_toFinset.1 hx with hx
    rcases List.mem_map.1 hx with ⟨a, ha, hax⟩
    rcases List.mem_filter.1 ha with ⟨ha, _⟩
    exact List.mem_toFinset.2 (List.mem_map.2 ⟨a, ha, hax⟩)
  calc
    (m >>= f).prob y = (m.toList.map (fun (a, p) => p * (f a).prob y)).sum := by
      rw [Raw.prob, bind_toList, probOfList_bind_eq_sum]
    _ = s.sum (fun a => m.prob a * (f a).prob y) := by
      symm
      simpa [s, Raw.prob, Raw.toList] using
        list_sum_prob_mul_eq m.toList (fun a => (f a).prob y)
    _ = m.support.sum (fun a => m.prob a * (f a).prob y) := by
      symm
      exact Finset.sum_subset hs (by
        intro x _ hx
        simp [prob_eq_zero_of_not_mem_support m hx])

lemma mem_support_bind_iff [DecidableEq α] [DecidableEq β] (m : Raw α) (f : α → Raw β) (y : β) :
    y ∈ (m >>= f).support ↔ ∃ x ∈ m.support, y ∈ (f x).support := by
  rw [mem_support_iff, prob_bind]
  constructor
  · intro hy
    have hpos : 0 < ∑ x ∈ m.support, m.prob x * (f x).prob y := pos_iff_ne_zero.mpr hy
    rcases Finset.sum_pos_iff.mp hpos with ⟨x, hx, hxpos⟩
    have hfy : (f x).prob y ≠ 0 := by
      by_contra hzero
      rw [hzero, mul_zero] at hxpos
      exact lt_irrefl _ hxpos
    exact ⟨x, hx, (mem_support_iff (f x) y).2 hfy⟩
  · rintro ⟨x, hx, hy⟩
    have hmx : m.prob x ≠ 0 := (mem_support_iff m x).1 hx
    have hfy : (f x).prob y ≠ 0 := (mem_support_iff (f x) y).1 hy
    have hpos : 0 < m.prob x * (f x).prob y :=
      mul_pos (pos_iff_ne_zero.mpr hmx) (pos_iff_ne_zero.mpr hfy)
    have hle :
        m.prob x * (f x).prob y ≤ ∑ a ∈ m.support, m.prob a * (f a).prob y :=
      Finset.single_le_sum
        (f := fun a => m.prob a * (f a).prob y) (fun _ _ => by exact zero_le) hx
    exact pos_iff_ne_zero.mp (lt_of_lt_of_le hpos hle)

@[simp] lemma support_bind [DecidableEq α] [DecidableEq β] (m : Raw α) (f : α → Raw β) :
    (m >>= f).support = m.support.biUnion (fun x => (f x).support) := by
  ext y
  simp [mem_support_bind_iff]

def addWeight [BEq α] [Hashable α] (m : Std.HashMap α ℚ≥0) (a : α × ℚ≥0) :
    Std.HashMap α ℚ≥0 :=
  m.insert a.1 (m.getD a.1 0 + a.2)

def accumulateWeights [BEq α] [Hashable α] (xs : Array (α × ℚ≥0)) :
    Std.HashMap α ℚ≥0 :=
  xs.foldl addWeight {}

private lemma getD_foldl_addWeight_eq_probOfList [DecidableEq α] [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (l : List (α × ℚ≥0)) (m : Std.HashMap α ℚ≥0) (x : α) :
    (l.foldl addWeight m).getD x 0 = m.getD x 0 + probOfList l x := by
  induction l generalizing m with
  | nil => simp [probOfList]
  | cons hd tl ih =>
    rw [List.foldl_cons, ih]
    unfold addWeight
    by_cases h : hd.1 = x
    · have hbeq : (hd.1 == x) = true := by simp [h]
      rw [Std.HashMap.getD_insert]
      simp [probOfList, h, add_assoc, add_left_comm, add_comm]
    · have hbeq : (hd.1 == x) = false := by simp [h]
      rw [Std.HashMap.getD_insert]
      simp [probOfList, h, hbeq]

private lemma getD_accumulateWeights_eq_prob [DecidableEq α] [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (xs : Array (α × ℚ≥0)) (x : α) :
    (accumulateWeights xs).getD x 0 = probOfList xs.toList x := by
  unfold accumulateWeights
  rw [← Array.foldl_toList (f := addWeight) (init := ({} : Std.HashMap α ℚ≥0)) (xs := xs)]
  simpa using getD_foldl_addWeight_eq_probOfList xs.toList ({} : Std.HashMap α ℚ≥0) x

private lemma pairwise_ne_keys_toList [BEq α] [Hashable α] [LawfulBEq α] [LawfulHashable α]
    (m : Std.HashMap α ℚ≥0) :
    m.toList.Pairwise (fun a b => a.1 ≠ b.1) := by
  refine (Std.HashMap.distinct_keys_toList (m := m)).imp ?_
  intro a b hab hEq
  simp [hEq] at hab

private lemma probOfList_eq_find?_getD [DecidableEq α] [BEq α] [LawfulBEq α]
    (l : List (α × ℚ≥0)) (x : α)
    (hpair : l.Pairwise (fun a b => a.1 ≠ b.1)) :
    probOfList l x = ((l.find? (fun a => a.1 == x)).map Prod.snd).getD 0 := by
  induction l with
  | nil => simp [probOfList]
  | cons a tl ih =>
    rw [List.pairwise_cons] at hpair
    rcases hpair with ⟨ha, hpair⟩
    by_cases h : a.1 = x
    · have hnil : tl.filter (fun b => b.1 = x) = [] := by
        apply List.filter_eq_nil_iff.2
        intro b hb
        simp only [decide_eq_true_eq]
        intro hb'
        exact ha _ hb (h.trans hb'.symm)
      have hbeq : (a.1 == x) = true := by simp [h]
      simp [probOfList, h, hnil]
    · have hbeq : (a.1 == x) = false := by simp [h]
      simpa [probOfList, h, hbeq] using ih hpair

private lemma probOfList_toList_eq_getD [DecidableEq α] [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (m : Std.HashMap α ℚ≥0) (x : α) :
    probOfList m.toList x = m.getD x 0 := by
  rw [probOfList_eq_find?_getD m.toList x (pairwise_ne_keys_toList m),
    Std.HashMap.getD_eq_getD_getElem?]
  cases hopt : m[x]? with
  | none =>
    have hnot : x ∉ m := by
      rw [Std.HashMap.mem_iff_isSome_getElem?]
      simp [hopt]
    have hfind : m.toList.find? (fun a => a.1 == x) = none :=
      (Std.HashMap.find?_toList_eq_none_iff_not_mem (m := m) (k := x)).2 hnot
    simp [hfind]
  | some q =>
    have hxmem : x ∈ m := by
      rw [Std.HashMap.mem_iff_isSome_getElem?]
      simp [hopt]
    have hkey : m.getKey? x = some x := Std.HashMap.getKey?_eq_some (m := m) hxmem
    have hfind : m.toList.find? (fun a => a.1 == x) = some (x, q) :=
      (Std.HashMap.find?_toList_eq_some_iff_getKey?_eq_some_and_getElem?_eq_some
        (m := m) (k := x) (k' := x) (v := q)).2 ⟨hkey, hopt⟩
    simp [hfind]

def normalizeMap [BEq α] [Hashable α] [LawfulBEq α] [LawfulHashable α] (p : Raw α) :
    Std.HashMap α ℚ≥0 :=
  (accumulateWeights p.data).filter (fun _ q => q ≠ 0)

private lemma probOfNormalizeMap_eq_prob [DecidableEq α] [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (p : Raw α) (x : α) :
    probOfList (normalizeMap p).toList x = p.prob x := by
  rw [probOfList_toList_eq_getD]
  unfold normalizeMap
  rw [Std.HashMap.getD_filter']
  have hacc : (accumulateWeights p.data).getD x 0 = p.prob x := by
    simpa [Raw.prob, Raw.toList] using getD_accumulateWeights_eq_prob p.data x
  rw [Std.HashMap.getD_eq_getD_getElem?] at hacc
  cases hopt : (accumulateWeights p.data)[x]? with
  | none =>
    simp [hopt] at hacc
    simp [hacc]
  | some q =>
    have hacc' : q = p.prob x := by simpa [hopt] using hacc
    by_cases hq : q = 0
    · have hprob : p.prob x = 0 := hacc'.symm.trans hq
      rw [Option.filter_some, if_neg (by simp [hq]), Option.getD_none]
      exact hprob.symm
    · have hprob : p.prob x ≠ 0 := by simpa [hacc'] using hq
      calc
        (Option.filter (fun q => decide (q ≠ 0)) (some q)).getD 0 = q := by
          rw [Option.filter_some]
          have hpred : decide (q ≠ 0) = true := by simp [hq]
          simp [hpred]
        _ = p.prob x := hacc'

private lemma snd_ne_zero_of_mem_normalizeMap_toList [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (p : Raw α) {a : α × ℚ≥0}
    (ha : a ∈ (normalizeMap p).toList) : a.2 ≠ 0 := by
  have hsome : (normalizeMap p)[a.1]? = some a.2 :=
    (Std.HashMap.mem_toList_iff_getElem?_eq_some (m := normalizeMap p)
      (k := a.1) (v := a.2)).1 ha
  unfold normalizeMap at hsome
  rw [Std.HashMap.getElem?_filter'] at hsome
  cases hacc : (accumulateWeights p.data)[a.1]? with
  | none => simp [hacc] at hsome
  | some q =>
    by_cases hq : q = 0
    · simp only [ne_eq, decide_not, hacc, hq, Option.filter_eq_some_iff, Option.some.injEq,
        Bool.not_eq_eq_eq_not, Bool.not_true, decide_eq_false_iff_not] at hsome
      exact False.elim (hsome.2 hsome.1.symm)
    · simp only [ne_eq, decide_not, hacc, Option.filter_eq_some_iff, Option.some.injEq,
        Bool.not_eq_eq_eq_not, Bool.not_true, decide_eq_false_iff_not] at hsome
      exact hsome.2

private lemma normalizeMap_keys_eq_support [DecidableEq α] [BEq α] [Hashable α]
    [LawfulBEq α] [LawfulHashable α] (p : Raw α) :
    ((normalizeMap p).toList.map Prod.fst).toFinset = p.support := by
  rw [← supportOfList_eq_keys (l := (normalizeMap p).toList)]
  · ext x
    rw [mem_supportOfList_iff, mem_support_iff, probOfNormalizeMap_eq_prob]
  · intro a ha
    exact snd_ne_zero_of_mem_normalizeMap_toList p ha

/-- Merge duplicate outcomes and discard zero-weight entries. This implementation is linear in the
number of raw entries up to hash-map operations, so it avoids the repeated `support/prob` rescans
that would make normalization quadratic. -/
protected def normalize [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α] [LawfulHashable α]
    (p : Raw α) : Raw α :=
  ⟨(normalizeMap p).toList.toArray, by
    have hkeys : ((normalizeMap p).toList.map Prod.fst).toFinset = p.support :=
      normalizeMap_keys_eq_support p
    calc
      (((normalizeMap p).toList.map Prod.snd).sum) =
          (((normalizeMap p).toList.map Prod.fst).toFinset.sum
            (probOfList (normalizeMap p).toList)) := by
        symm
        exact list_sum_prob_eq (normalizeMap p).toList
      _ = p.support.sum p.prob := by
        rw [hkeys]
        refine Finset.sum_congr rfl ?_
        intro x _
        exact probOfNormalizeMap_eq_prob p x
      _ = 1 := sum_prob_eq_one p⟩

@[simp] lemma normalize_toList [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α]
    [LawfulHashable α] (p : Raw α) :
    p.normalize.toList = (normalizeMap p).toList := by
  unfold Raw.normalize
  simp [Raw.toList]

@[simp] lemma prob_normalize [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α]
    [LawfulHashable α] (p : Raw α) (x : α) :
    p.normalize.prob x = p.prob x := by
  unfold Raw.prob
  rw [normalize_toList]
  exact probOfNormalizeMap_eq_prob p x

@[simp] lemma support_normalize [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α]
    [LawfulHashable α] (p : Raw α) :
    p.normalize.support = p.support := by
  ext x
  rw [mem_support_iff, mem_support_iff, prob_normalize]

/-- Convert to a `PMF` by mapping weights through `ℚ≥0 → ℝ≥0 → ℝ≥0∞`. -/
noncomputable def toPMF [DecidableEq α] (p : Raw α) : PMF α :=
  PMF.ofFinset (fun x => ((p.prob x : NNReal) : ENNReal)) p.support
    (by
      have hsum : p.support.sum p.prob = (1 : ℚ≥0) := by
        rw [sum_prob_eq_sum]
        simpa [Raw.toList] using p.sum_eq_one
      rw [← ENNReal.ofNNReal_finsetSum, ← NNRat.cast_sum (K := NNReal)]
      change (((p.support.sum p.prob : ℚ≥0) : NNReal) : ENNReal) = 1
      simpa using congrArg (fun q : ℚ≥0 => ((q : NNReal) : ENNReal)) hsum)
    (fun a ha => by simp [prob_eq_zero_of_not_mem_support p ha])

@[simp] lemma toPMF_apply [DecidableEq α] (p : Raw α) (x : α) :
    p.toPMF x = ((p.prob x : NNReal) : ENNReal) := rfl

@[simp] lemma toPMF_pure [DecidableEq α] (a : α) :
    (Raw.pure a).toPMF = PMF.pure a := by
  ext x
  rw [toPMF_apply, PMF.pure_apply, prob_pure]
  split_ifs <;> simp [*]

@[simp] lemma toPMF_uniform [FinEnum α] [Inhabited α] :
    (Raw.uniform (α := α)).toPMF = PMF.uniformOfFintype α := by
  ext x
  rw [toPMF_apply, PMF.uniformOfFintype_apply, prob_uniform]
  simp [NNRat.cast_inv]

@[simp] lemma toPMF_coin : Raw.coin.toPMF = PMF.uniformOfFintype Bool := by
  ext b
  rw [toPMF_apply, PMF.uniformOfFintype_apply, prob_coin]
  simp [NNRat.cast_inv]

@[simp] lemma toPMF_bind [DecidableEq α] [DecidableEq β] (m : Raw α) (f : α → Raw β) :
    (m >>= f).toPMF = m.toPMF >>= fun a => (f a).toPMF := by
  ext y
  rw [toPMF_apply]
  change (((m >>= f).prob y : NNReal) : ENNReal) =
      ∑' a, m.toPMF a * (f a).toPMF y
  rw [tsum_eq_sum (s := m.support)]
  · simp_rw [Raw.toPMF_apply, ← ENNReal.coe_mul, ← NNRat.cast_mul]
    rw [← ENNReal.ofNNReal_finsetSum, ← NNRat.cast_sum (K := NNReal), Raw.prob_bind]
  · intro x hx
    simp [Raw.toPMF_apply, prob_eq_zero_of_not_mem_support m hx]

noncomputable def toPMFHom : Raw →ᵐ PMF where
  toFun _ p := @Raw.toPMF _ (Classical.decEq _) p
  toFun_pure' := by
    intro α x
    letI := Classical.decEq α
    exact Raw.toPMF_pure (α := α) x
  toFun_bind' := by
    intro α β x y
    letI := Classical.decEq α
    letI := Classical.decEq β
    exact Raw.toPMF_bind (α := α) (β := β) x y

end Raw

/-! ## Distributional equality and quotient -/

variable {α β γ : Type u}

/-- Two raw PMFs represent the same distribution if they assign the same probability to every
outcome. Uses classical decidable equality since this is a `Prop`. -/
def SameDist (p q : Raw α) : Prop :=
  ∀ x : α, @Raw.prob _ (Classical.decEq _) p x =
            @Raw.prob _ (Classical.decEq _) q x

lemma SameDist.refl (p : Raw α) : SameDist p p := fun _ => rfl

lemma SameDist.symm {p q : Raw α} (h : SameDist p q) : SameDist q p :=
  fun x => (h x).symm

lemma SameDist.trans {p q r : Raw α} (hpq : SameDist p q) (hqr : SameDist q r) :
    SameDist p r :=
  fun x => (hpq x).trans (hqr x)

lemma SameDist.prob_eq [DecidableEq α] {p q : Raw α} (h : SameDist p q) (x : α) :
    p.prob x = q.prob x := by
  simpa [Raw.prob_eq_prob (Classical.decEq _) inferInstance p x,
    Raw.prob_eq_prob (Classical.decEq _) inferInstance q x] using h x

lemma SameDist.support_eq [DecidableEq α] {p q : Raw α} (h : SameDist p q) :
    p.support = q.support := by
  ext x
  rw [Raw.mem_support_iff, Raw.mem_support_iff, h.prob_eq x]

lemma SameDist.bind_congr {p q : Raw α}
    {f g : α → Raw β} (hpq : SameDist p q) (hfg : ∀ x, SameDist (f x) (g x)) :
    SameDist (p >>= f) (q >>= g) := by
  intro y
  rw [show @Raw.prob _ (Classical.decEq β) (p >>= f) y =
      (@Raw.support _ (Classical.decEq α) p).sum
        (fun x => @Raw.prob _ (Classical.decEq α) p x *
          @Raw.prob _ (Classical.decEq β) (f x) y) by
        exact @Raw.prob_bind _ _ (Classical.decEq α) (Classical.decEq β) p f y]
  rw [show @Raw.prob _ (Classical.decEq β) (q >>= g) y =
      (@Raw.support _ (Classical.decEq α) q).sum
        (fun x => @Raw.prob _ (Classical.decEq α) q x *
          @Raw.prob _ (Classical.decEq β) (g x) y) by
        exact @Raw.prob_bind _ _ (Classical.decEq α) (Classical.decEq β) q g y]
  rw [show @Raw.support _ (Classical.decEq α) p = @Raw.support _ (Classical.decEq α) q by
        exact @SameDist.support_eq _ (Classical.decEq α) p q hpq]
  refine Finset.sum_congr rfl ?_
  intro x hx
  rw [hpq x, hfg x y]

lemma SameDist.map_congr {p q : Raw α}
    (hpq : SameDist p q) (f : α → β) :
    SameDist (f <$> p) (f <$> q) := by
  change SameDist (p.bind (fun x => Raw.pure (f x))) (q.bind (fun x => Raw.pure (f x)))
  exact SameDist.bind_congr (β := β) hpq fun x => SameDist.refl (Raw.pure (f x))

instance  _root_.FinRatPMF.instIsEquivRawSameDist : IsEquiv (Raw α) SameDist where
  refl := SameDist.refl
  symm := @SameDist.symm _
  trans := @SameDist.trans _

instance Raw.instSetoid : Setoid (Raw α) where
  r := SameDist
  iseqv := ⟨SameDist.refl, SameDist.symm, SameDist.trans⟩

namespace Raw

lemma sameDist_normalize [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α]
    [LawfulHashable α] (p : Raw α) : SameDist p p.normalize := by
  intro x
  rw [Raw.prob_eq_prob (Classical.decEq _) inferInstance p x,
    Raw.prob_eq_prob (Classical.decEq _) inferInstance p.normalize x,
    prob_normalize]

lemma sameDist_normalize_normalize [DecidableEq α] [BEq α] [Hashable α] [LawfulBEq α]
    [LawfulHashable α] (p : Raw α) : SameDist p.normalize.normalize p.normalize := by
  intro x
  rw [Raw.prob_eq_prob (Classical.decEq _) inferInstance p.normalize.normalize x,
    Raw.prob_eq_prob (Classical.decEq _) inferInstance p.normalize x,
    prob_normalize]

end Raw

end FinRatPMF

/-- Probability mass function with finite support and rational weights, with canonical equality.

Defined as the quotient of `FinRatPMF.Raw` by distributional equality. Two values are equal iff
they assign the same probability to every outcome. -/
def FinRatPMF (α : Type u) : Type u := Quotient (α := FinRatPMF.Raw α) inferInstance

namespace FinRatPMF

variable {α β γ : Type u}

/-- Construct from a raw PMF. -/
def mk (p : Raw α) : FinRatPMF α := Quotient.mk _ p

/-- `FinRatPMF` equality is distributional equality. -/
lemma eq_iff {p q : Raw α} : mk p = mk q ↔ SameDist p q :=
  Quotient.eq

/-! ### Monad operations -/

/-- `bind` lifts `Raw.bind` across the quotient in the first argument. The codomain remains
noncomputable because the Kleisli function returns quotient values, so we still choose a raw
representative for each branch. -/
noncomputable instance  _root_.FinRatPMF.instMonad : Monad FinRatPMF where
  pure a := mk (Raw.pure a)
  bind ma f := Quotient.liftOn ma
    (fun p => mk (Raw.bind p (fun a => Quotient.out (f a))))
    (by
      classical
      intro p q hpq
      apply Quotient.sound
      refine SameDist.bind_congr hpq ?_
      intro a
      exact SameDist.refl (Quotient.out (f a))
    )

lemma bind_eq_out (ma : FinRatPMF α) (f : α → FinRatPMF β) :
    ma >>= f = mk (Raw.bind (Quotient.out ma) (fun a => Quotient.out (f a))) := by
  classical
  refine Quotient.inductionOn ma ?_
  intro p
  apply Quotient.sound
  refine SameDist.bind_congr ?_ ?_
  · exact SameDist.symm <| Quotient.exact (Quotient.out_eq (mk p : FinRatPMF α))
  · intro a
    exact SameDist.refl (Quotient.out (f a))

@[simp] lemma bind_mk (p : Raw α) (f : α → FinRatPMF β) :
    (mk p >>= f) = mk (Raw.bind p (fun a => Quotient.out (f a))) := by
  classical
  trans mk (Raw.bind (Quotient.out (mk p : FinRatPMF α)) (fun a => Quotient.out (f a)))
  · exact bind_eq_out (mk p) f
  · apply Quotient.sound
    refine SameDist.bind_congr ?_ ?_
    · exact Quotient.exact (Quotient.out_eq (mk p : FinRatPMF α))
    · intro a
      exact SameDist.refl (Quotient.out (f a))

private lemma out_bind_sameDist (ma : FinRatPMF α) (f : α → FinRatPMF β) :
    SameDist (Quotient.out (ma >>= f))
      (Raw.bind (Quotient.out ma) (fun a => Quotient.out (f a))) :=
  Quotient.exact ((Quotient.out_eq (ma >>= f)).trans (bind_eq_out ma f))

/-! ### Connection to `PMF` -/

/-- Convert a `FinRatPMF` to a `PMF`. Well-defined since `SameDist` implies equal `toPMF`. -/
noncomputable def toPMF (p : FinRatPMF α) : PMF α := by
  classical
  refine Quotient.lift (fun raw => @Raw.toPMF _ (Classical.decEq _) raw) ?_ p
  intro a b hab
  refine PMF.ext fun x => ?_
  rw [Raw.toPMF_apply, Raw.toPMF_apply]
  exact congrArg (fun q : ℚ≥0 => ((q : NNReal) : ENNReal)) (hab x)

@[simp] lemma toPMF_mk (p : Raw α) : toPMF (mk p) = @Raw.toPMF _ (Classical.decEq _) p := by
  classical
  unfold toPMF mk
  rw [Quotient.lift_mk]

@[simp] lemma toPMF_pure (a : α) : toPMF (pure a : FinRatPMF α) = PMF.pure a := by
  classical
  rw [show (pure a : FinRatPMF α) = mk (Raw.pure a) by rfl, toPMF_mk, Raw.toPMF_pure]

lemma toPMF_out (p : FinRatPMF α) :
    toPMF p = @Raw.toPMF _ (Classical.decEq _) (Quotient.out p) := by
  classical
  refine Quotient.inductionOn p ?_
  intro q
  refine PMF.ext fun x => ?_
  change (toPMF (mk q : FinRatPMF α)) x =
    ((@Raw.toPMF _ (Classical.decEq _) (Quotient.out (mk q : FinRatPMF α)) : PMF α) x)
  rw [toPMF_mk, Raw.toPMF_apply, Raw.toPMF_apply]
  exact congrArg (fun r : ℚ≥0 => ((r : NNReal) : ENNReal))
    ((SameDist.symm <| Quotient.exact (Quotient.out_eq (mk q : FinRatPMF α))) x)

@[simp] lemma toPMF_bind (ma : FinRatPMF α) (f : α → FinRatPMF β) :
    toPMF (ma >>= f) = toPMF ma >>= fun a => toPMF (f a) := by
  classical
  calc
    toPMF (ma >>= f)
        = @Raw.toPMF _ (Classical.decEq _)
            (Raw.bind (Quotient.out ma) (fun a => Quotient.out (f a))) := by
              rw [bind_eq_out, toPMF_mk]
    _ = @Raw.toPMF _ (Classical.decEq _) (Quotient.out ma) >>=
          fun a => @Raw.toPMF _ (Classical.decEq _) (Quotient.out (f a)) :=
            Raw.toPMF_bind _ _
    _ = toPMF ma >>= fun a => toPMF (f a) := by
          rw [← toPMF_out ma]
          congr 1
          funext a
          rw [← toPMF_out (f a)]

noncomputable def toPMFHom : FinRatPMF →ᵐ PMF where
  toFun _ p := toPMF p
  toFun_pure' := by
    intro α x
    exact toPMF_pure x
  toFun_bind' := by
    intro α β x y
    exact toPMF_bind x y

lemma toPMF_injective : Function.Injective (toPMF (α := α)) := by
  classical
  intro p q hpq
  revert hpq
  refine Quotient.inductionOn₂ p q ?_
  intro a b hpq
  change toPMF (mk a) = toPMF (mk b) at hpq
  rw [toPMF_mk, toPMF_mk] at hpq
  apply Quotient.sound
  intro x
  have hfun :
      (@Raw.toPMF _ (Classical.decEq _) a : PMF α) x =
      (@Raw.toPMF _ (Classical.decEq _) b : PMF α) x :=
    congrFun (congrArg DFunLike.coe hpq) x
  rw [Raw.toPMF_apply, Raw.toPMF_apply] at hfun
  have key' :
      ((@Raw.prob _ (Classical.decEq _) a x : ℚ≥0) : NNReal) =
      ((@Raw.prob _ (Classical.decEq _) b x : ℚ≥0) : NNReal) :=
    congrArg ENNReal.toNNReal hfun
  calc @Raw.prob _ (Classical.decEq _) a x
      = a.prob x := Raw.prob_eq_prob _ _ _ _
    _ = b.prob x := by exact_mod_cast key'
    _ = @Raw.prob _ (Classical.decEq _) b x :=
        (Raw.prob_eq_prob _ _ _ _).symm

noncomputable instance  _root_.FinRatPMF.instLawfulMonad : LawfulMonad FinRatPMF := LawfulMonad.mk'
  (id_map := fun x => by
    apply toPMF_injective
    calc
      toPMF (id <$> x) = toPMF x >>= fun a => PMF.pure a := by
        rw [show id <$> x = x >>= fun a => pure (id a) by rfl, toPMF_bind]
        simp
      _ = toPMF x := by
            change toPMF x >>= pure = toPMF x
            exact bind_pure (x := toPMF x))
  (pure_bind := fun x f => by
    apply toPMF_injective
    calc
      toPMF (pure x >>= f) = PMF.pure x >>= fun a => toPMF (f a) := by
        rw [toPMF_bind, toPMF_pure]
      _ = toPMF (f x) :=
            pure_bind (m := PMF) x (fun a => toPMF (f a)))
  (bind_assoc := fun m f g => by
    apply toPMF_injective
    calc
      toPMF ((m >>= f) >>= g)
          = (toPMF m >>= fun a => toPMF (f a)) >>= fun b => toPMF (g b) := by
              rw [toPMF_bind, toPMF_bind]
      _ = toPMF m >>= fun a => toPMF (f a) >>= fun b => toPMF (g b) := by simp [bind_assoc]
      _ = toPMF (m >>= fun a => f a >>= g) := by
            rw [toPMF_bind]
            congr 1
            ext a
            rw [toPMF_bind])
  (bind_pure_comp := fun f x => by
    apply toPMF_injective
    calc
      toPMF (x >>= fun a => pure (f a))
          = toPMF x >>= fun a => PMF.pure (f a) := by
              rw [toPMF_bind]
              simp
      _ = f <$> toPMF x :=
            bind_pure_comp (m := PMF) f (toPMF x)
      _ = toPMF (f <$> x) := by
            rw [show f <$> x = x >>= fun a => pure (f a) by rfl, toPMF_bind]
            simp [map_eq_bind_pure_comp]
            rfl)

instance instDecidableSameDist [DecidableEq α] (p q : Raw α) : Decidable (SameDist p q) := by
  let s := p.support ∪ q.support
  classical
  by_cases hs : ∀ x ∈ s, p.prob x = q.prob x
  · refine isTrue ?_
    intro x
    by_cases hx : x ∈ s
    · simpa [Raw.prob_eq_prob (Classical.decEq _) inferInstance p x,
        Raw.prob_eq_prob (Classical.decEq _) inferInstance q x] using hs x hx
    · have hpx : p.prob x = 0 := Raw.prob_eq_zero_of_not_mem_support p (by
        intro hxp
        exact hx (Finset.mem_union.2 <| Or.inl hxp))
      have hqx : q.prob x = 0 := Raw.prob_eq_zero_of_not_mem_support q (by
        intro hxq
        exact hx (Finset.mem_union.2 <| Or.inr hxq))
      rw [Raw.prob_eq_prob (Classical.decEq _) inferInstance p x,
        Raw.prob_eq_prob (Classical.decEq _) inferInstance q x, hpx, hqx]
  · refine isFalse ?_
    intro hpq
    apply hs
    intro x hx
    exact SameDist.prob_eq hpq x

instance  _root_.FinRatPMF.instBEqRawOfDecidableEq [DecidableEq α] : BEq (Raw α) where
  beq p q := decide (SameDist p q)

@[simp] lemma beq_iff_sameDist [DecidableEq α] (p q : Raw α) :
    (p == q) = true ↔ SameDist p q := by
  change decide (SameDist p q) = true ↔ SameDist p q; simp

end FinRatPMF


Source
https://github.com/Verified-zkEVM/VCV-io/blob/446baa72bb7d4296d6f6b7015fd6c15ca9c678b7/ToMathlib/ProbabilityTheory/FinRatPMF.lean yukon-proof-operation:4fcbf60fdc521e09e403c921147d3eab0b27eef6a0bd2efcee9915f845311b9f [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246NGZjYmY2MGZkYzUyMWUwOWU0MDNjOTIxMTQ3ZDNlYWIwYjI3ZWVmNmEwYmQyZWZjZWU5OTE1Zjg0NTMxMWI5ZiIsImhhc2giOiI3NDQ2ODlkZTllNGIzOTAyYTZjZTgyYzFiZDE1MjQ2OWRhMDg4NTI3NTY0MWY0YzAxZmQ5OGJhMWVjZWQyYzEyIiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl8yYTJkMDQ2YzFiOTgzYzQ1NjcwZDhiOWYiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

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