YukonModule.VCVio.EvalDist.Prod.part0
DefinitionYukon_2e7e800d480cc4c5ab2a0a15better-codes
Source module VCVio.EvalDist.Prod.
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, Quang Dao
-/
module
public import Definitions.Def_Yukon_641302f1e500c2a544b42adc
public import Definitions.Def_Yukon_ac1fabbdddd4e4a4c0618520
public import Mathlib.Topology.Algebra.InfiniteSum.ENNReal
public import Init
public import Mathlib.Probability.Distributions.Uniform
public import Mathlib.Data.Finset.Card
public import Mathlib.Data.Vector.Defs
public import Mathlib.CategoryTheory.Monad.Types
public import Mathlib.Order.CompleteLattice.Basic
public import Mathlib.Probability.ProbabilityMassFunction.Monad
public import Batteries.Control.AlternativeMonad
meta import Definitions.Def_Yukon_ac1fabbdddd4e4a4c0618520
meta import Definitions.Def_Yukon_641302f1e500c2a544b42adc
set_option backward.isDefEq.respectTransparency.types false
/-!
# Evaluation Distributions of Computations with `Prod`
Lemmas about `evalDist` and `support` involving `Prod`, ported to generic `[MonadLiftT m SPMF]`.
-/
@[expose] public section
open ENNReal Prod
universe u v
variable {m : Type u → Type v} [Monad m] [LawfulMonad m] [MonadLiftT m SPMF]
[LawfulMonadLiftT m SPMF] {α β γ δ : Type u}
omit [Monad m] [LawfulMonadLiftT m SPMF] in
omit [LawfulMonad m] in
lemma probOutput_prod_mk_eq_probEvent (mx : m (α × β)) (x : α) (y : β) :
Pr[= (x, y) | mx] = Pr[ fun z => z.1 = x ∧ z.2 = y | mx] := by grind
@[grind =]
lemma probOutput_fst_map_eq_tsum (mx : m (α × β)) (x : α) :
Pr[= x | Prod.fst <$> mx] = ∑' y, Pr[= (x, y) | mx] := by
classical
simp only [probOutput_map_eq_tsum_ite, ENNReal.tsum_prod']
refine (tsum_eq_single x fun a ha => by simp [Ne.symm ha]).trans (by simp)
@[grind =]
lemma probOutput_fst_map_eq_sum [Fintype β] (mx : m (α × β)) (x : α) :
Pr[= x | Prod.fst <$> mx] = ∑ y, Pr[= (x, y) | mx] := by
rw [probOutput_fst_map_eq_tsum, tsum_fintype]
@[grind =]
lemma probOutput_snd_map_eq_tsum (mx : m (α × β)) (y : β) :
Pr[= y | Prod.snd <$> mx] = ∑' x, Pr[= (x, y) | mx] := by
classical
simp only [probOutput_map_eq_tsum_ite, ENNReal.tsum_prod']
refine tsum_congr fun _ => (tsum_eq_single y fun b hb => by simp [Ne.symm hb]).trans (by simp)
@[grind =]
lemma probOutput_snd_map_eq_sum [Fintype α] (mx : m (α × β)) (y : β) :
Pr[= y | Prod.snd <$> mx] = ∑ x, Pr[= (x, y) | mx] := by
rw [probOutput_snd_map_eq_tsum, tsum_fintype]
@[grind =]
lemma probOutput_fst_map_eq_probEvent (mx : m (α × β)) (x : α) :
Pr[= x | Prod.fst <$> mx] = Pr[ fun z => z.1 = x | mx] := by grind
/-- Unlike `probEvent_map` this unfolds the function composition automatically. -/
@[simp high, grind =]
lemma probEvent_fst_map (mx : m (α × β)) (p : α → Prop) :
Pr[ p | Prod.fst <$> mx] = Pr[ fun x => p x.1 | mx] := by grind
@[grind =]
lemma probOutput_snd_map_eq_probEvent (mx : m (α × β)) (y : β) :
Pr[= y | Prod.snd <$> mx] = Pr[ fun z => z.2 = y | mx] := by grind
/-- Unlike `probEvent_map` this unfolds the function composition automatically. -/
@[simp high, grind =]
lemma probEvent_snd_map (mx : m (α × β)) (p : β → Prop) :
Pr[ p | Prod.snd <$> mx] = Pr[ fun y => p y.2 | mx] := by grind
omit [Monad m] [LawfulMonadLiftT m SPMF] in
omit [LawfulMonad m] in
@[simp, grind =]
lemma probEvent_fst_eq_snd (mx : m (α × α)) :
Pr[ fun z => z.1 = z.2 | mx] = ∑' x : α, Pr[= (x, x) | mx] := by
classical
rw [probEvent_eq_tsum_ite, ENNReal.tsum_prod']
simp
section prod_mk
variable (mx : m α) (my : m β) (f : α → γ) (g : β → δ)
/- `@[grind norm]` (not `@[grind =]`): `Seq.seq`'s thunk argument makes the LHS an invalid
E-matching pattern, but `grind`'s simp-based normalization phase needs no pattern indexing. This
lets bare `grind` factor an independent applicative product (and e.g. close equiprobability of a
uniform product), which E-matching alone cannot. -/
@[simp high, grind norm]
lemma probOutput_seq_map_prod_mk_eq_mul (z : α × β) :
Pr[= z | Prod.mk <$> mx <*> my] = Pr[= z.1 | mx] * Pr[= z.2 | my] :=
probOutput_seq_map_eq_mul_of_injective2 mx my Prod.mk Prod.mk.injective2 z.1 z.2
omit [MonadLiftT m SPMF] [LawfulMonadLiftT m SPMF] in
@[simp high]
lemma support_seq_map_prod_mk [MonadLiftT m SetM] [LawfulMonadLiftT m SetM] :
support (Prod.mk <$> mx <*> my) = support mx ×ˢ support my := by
simp [Set.ext_iff]
omit [MonadLiftT m SPMF] [LawfulMonadLiftT m SPMF] in
lemma finSupport_seq_map_prod_mk [MonadLiftT m SetM] [LawfulMonadLiftT m SetM]
[HasEvalFinset m] [DecidableEq α] [DecidableEq β] :
finSupport (Prod.mk <$> mx <*> my) = Finset.product (finSupport mx) (finSupport my) := by
simp
@[simp]
lemma probOutput_seq_map_prod_mk_map_eq_mul (z : γ × δ) :
Pr[= z | (f ·, g ·) <$> mx <*> my] = Pr[= z.1 | f <$> mx] * Pr[= z.2 | g <$> my] := by
have hseq : (f ·, g ·) <$> mx <*> my = Prod.mk <$> (f <$> mx) <*> (g <$> my) := by
simp [seq_eq_bind_map, Functor.map_map]
rw [hseq, probOutput_seq_map_prod_mk_eq_mul]
@[simp]
lemma probOutput_seq_map_prod_mk_map_eq_mul' (z : γ × δ) :
Pr[= z | (fun y x => (f x, g y)) <$> my <*> mx] =
Pr[= z.1 | f <$> mx] * Pr[= z.2 | g <$> my] := by
rw [← probOutput_seq_map_swap]
simp
@[simp]
lemma probOutput_bind_map_prod_mk_eq_mul (z : γ × δ) :
Pr[= z | do let x ← mx; (f x, g ·) <$> my] = Pr[= z.1 | f <$> mx] * Pr[= z.2 | g <$> my] := by
simpa [monad_norm] using probOutput_seq_map_prod_mk_map_eq_mul mx my f g z
@[simp]
lemma probOutput_bind_map_prod_mk_eq_mul'
(mx : m α) (my : m β) (f : α → γ) (g : β → δ) (z : γ × δ) :
Pr[= z | do let y ← my; (f ·, g y) <$> mx] = Pr[= z.1 | f <$> mx] * Pr[= z.2 | g <$> my] := by
simpa [monad_norm] using probOutput_seq_map_prod_mk_map_eq_mul' mx my f g z
omit [MonadLiftT m SPMF] [LawfulMonadLiftT m SPMF] in
@[simp high]
lemma support_seq_map_prod_mk_eq_sprod [MonadLiftT m SetM] [LawfulMonadLiftT m SetM] :
support ((f ·, g ·) <$> mx <*> my) = (f '' support mx) ×ˢ (g '' support my) := by
simp [Set.ext_iff]; grind
omit [MonadLiftT m SPMF] [LawfulMonadLiftT m SPMF] in
lemma finSupport_seq_map_prod_mk_eq_product [MonadLiftT m SetM] [LawfulMonadLiftT m SetM]
[HasEvalFinset m] [DecidableEq α] [DecidableEq β]
[DecidableEq γ] [DecidableEq δ] : finSupport ((f ·, g ·) <$> mx <*> my) =
((finSupport mx).image f).product ((finSupport my).image g) := by
simp [Finset.ext_iff]; grind
lemma probOutput_bind_bind_prod_mk_eq_mul
(mx : m α) (my : m β) (f : α → γ) (g : β → δ) (z : γ × δ) :
Pr[= z | do let x ← mx; let y ← my; return (f x, g y)] =
Pr[= z.1 | f <$> mx] * Pr[= z.2 | g <$> my] := by simp
lemma probOutput_bind_bind_prod_mk_eq_mul'
(mx : m α) (my : m β) (f : α → γ) (g : β → δ) (x : γ) (y : δ) :
Pr[= (x, y) | do let a ← mx; let b ← my; return (f a, g b)] =
Pr[= x | f <$> mx] * Pr[= y | g <$> my] := by simp
/-- Two conditionally independent executions dominate the square of the
corresponding single-execution output probability. -/
lemma sq_probOutput_bind_le_probOutput_bind_prod
(source : m α) (kernel : α → m β) (y : β) :
Pr[= y | source >>= kernel] ^ 2 ≤
Pr[= (y, y) | source >>= fun x => do
let a ← kernel x
let b ← kernel x
pure (a, b)] := by
have hfactor (x : α) :
Pr[= (y, y) | do
let a ← kernel x
let b ← kernel x
pure (a, b)] = Pr[= y | kernel x] * Pr[= y | kernel x] := by
rw [probOutput_bind_bind_prod_mk_eq_mul']
simp only [show (fun a : β ↦ a) = id from rfl, id_map]
rw [probOutput_bind_eq_tsum source kernel y,
probOutput_bind_eq_tsum source (fun x ↦ do
let a ← kernel x
let b ← kernel x
pure (a, b)) (y, y)]
refine (ENNReal.sq_tsum_le_tsum_sq
(fun x ↦ Pr[= x | source]) (fun x ↦ Pr[= y | kernel x])
(tsum_probOutput_le_one (mx := source))).trans_eq ?_
refine tsum_congr fun x ↦ ?_
rw [hfactor]
simp [sq]
@[simp]
lemma probOutput_prod_mk_fst_map [DecidableEq β] (mx : m α) (y : β) (z : α × β) :
Pr[= z | (·, y) <$> mx] = if z.2 = y then Pr[= z.1 | mx] else 0 :=
calc Pr[= z | (·, y) <$> mx]
_ = Pr[= z | Prod.mk <$> mx <*> pure y] := by simp; rfl
_ = if z.2 = y then Pr[= z.1 | mx] else 0 := by simp only [probOutput_seq_map_prod_mk_eq_mul,
probOutput_pure, mul_ite, mul_one, mul_zero]
@[simp]
lemma probOutput_prod_mk_snd_map [DecidableEq α] (my : m β) (x : α) (z : α × β) :
Pr[= z | (x, ·) <$> my] = if z.1 = x then Pr[= z.2 | my] else 0 :=
calc Pr[= z | (x, ·) <$> my]
_ = Pr[= z | Prod.mk <$> pure x <*> my] := by simp [seq_eq_bind_map]; rfl
_ = if z.1 = x then Pr[= z.2 | my] else 0 := by simp only [probOutput_seq_map_prod_mk_eq_mul,
probOutput_pure, ite_mul, one_mul, zero_mul]
end prod_mk
Source