Source lean/Determinize/Proof/FiniteModel/Sampling.lean
import Determinize.Proof.FiniteModel.Contextsimport Determinize.Proof.Primitives.DiscreteRationalnamespace Determinize.Proof.FiniteModelopen Spec.Paper Spec.FiniteModel Determinize.Finite MeasureTheorynoncomputable def outcomeMeasure (outcomes : List (Rat × Rat)) : Measure ℝ :=  (outcomes.map fun (p, x) ↦ ENNReal.ofReal (p : ℝ) • Measure.dirac (x : ℝ)).sumtheorem outcomeMeasure_univ (outcomes : List (Rat × Rat))    (nonnegative : ∀ outcome ∈ outcomes, 0 ≤ outcome.1) :    outcomeMeasure outcomes Set.univ = ENNReal.ofReal ((outcomes.map Prod.fst).sum : ℝ) := by  induction outcomes with  | nil => simp [outcomeMeasure]  | cons entry rest ih =>    have hp : 0 ≤ (entry.1 : ℝ) := by exact_mod_cast nonnegative entry (by simp)    have hr : ∀ q ∈ rest, 0 ≤ q.1 := fun q hq ↦ nonnegative q (by simp [hq])    have hs : 0 ≤ ((rest.map Prod.fst).sum : ℝ) := by      exact_mod_cast List.sum_nonneg (by simpa using hr)    simp only [outcomeMeasure, List.map_cons, List.sum_cons, Measure.add_apply,      Measure.smul_apply, Measure.dirac_apply_of_mem (Set.mem_univ _), smul_eq_mul, mul_one]    simp only [outcomeMeasure] at ih    rw [ih hr, Rat.cast_add, ENNReal.ofReal_add hp hs]/-- Exact probabilities and the entire paper sampling law, not just its mean. -/def FiniteLawMatches (op : Op) (kind : DistributionAction) (arguments : List Rat)    (outcomes : List (Rat × Rat)) : Prop :=  (∀ outcome ∈ outcomes, 0 ≤ outcome.1) ∧  (outcomes.map Prod.fst).sum = 1 ∧  reduce (primitiveExpr (kind, op) (arguments.map fun (q : Rat) ↦ .real (q : ℝ))) =    .sample (kind, op) (outcomeMeasure outcomes) .realprivate theorem finiteLawMatches_singleton (op : Op) (kind : DistributionAction)    (arguments : List Rat)    (mean : Rat)    (law : reduce (primitiveExpr (kind, op) (arguments.map fun (q : Rat) ↦ .real (q : ℝ))) =      .sample (kind, op) (Measure.dirac (mean : ℝ)) .real) :    FiniteLawMatches op kind arguments [(1, mean)] := by  refine ⟨by simp, by simp, ?_⟩  simpa [outcomeMeasure] using lawtheorem finiteLawMatches_bernoulli_sample {affinity : Affinity} (p : Rat) (nonnegative : 0 ≤ p)    (bounded : p ≤ 1) :    FiniteLawMatches .bernoulli (.sample affinity) [p] [(1 - p, 0), (p, 1)] := by  have h0 : (0 : ℝ) ≤ p := by exact_mod_cast nonnegative  have h1 : (p : ℝ) ≤ 1 := by exact_mod_cast bounded  refine ⟨?_, ?_, ?_⟩  · simp [nonnegative, sub_nonneg.mpr bounded]  · simp  · simp [primitiveExpr, reduce, Expr.isValue, realValue?, bernoulliFiber, h0, h1, outcomeMeasure]theorem finiteLawMatches_bernoulli_mean (p : Rat) (nonnegative : 0 ≤ p) (bounded : p ≤ 1) :    FiniteLawMatches .bernoulli .mean [p] [(1, p)] := by  apply finiteLawMatches_singleton  have h0 : (0 : ℝ) ≤ p := by exact_mod_cast nonnegative  have h1 : (p : ℝ) ≤ 1 := by exact_mod_cast bounded  simp [primitiveExpr, reduce, Expr.isValue, realValue?, bernoulliFiber, h0, h1]theorem realListValue?_fold (p : List Rat) :    realListValue? ((p.map fun q ↦ .real (q : ℝ)).foldr Expr.cons .nil) =        some (p.map Rat.cast) := by  induction p <;> simp_all [realListValue?, realValue?]theorem isValue_list_fold (p : List Rat) :    ((p.map fun q ↦ .real (q : ℝ)).foldr Expr.cons .nil).isValue = true := by  induction p <;> simp_all [Expr.isValue]theorem finiteLawMatches_discrete_sample (affinity : Affinity) (p : List Rat)    (d : Checking.FiniteDistribution) (completed : d.probabilities = p ++ [1 - p.sum]) :    FiniteLawMatches (.discrete p.length) (.sample affinity) p      (d.probabilities.zipIdx.map fun (p, i) ↦ (p, (i : Rat))) := by  refine ⟨?_, ?_, ?_⟩  · intro outcome member    obtain ⟨entry, entryMember, rfl⟩ := List.mem_map.mp member    exact d.nonnegative _ (List.fst_mem_of_mem_zipIdx entryMember)  · simpa [List.map_map, Function.comp_def, List.zipIdx_map_fst] using d.total  · simp only [primitiveExpr, reduce, isValue_list_fold, ↓reduceIte, realListValue?_fold,      List.length_map, DiscreteLaws.completed_sample affinity p d completed]    simp [Checking.FiniteDistribution.measure, outcomeMeasure, List.map_map, Function.comp_def]theorem finiteLawMatches_discrete_mean (p : List Rat) (d : Checking.FiniteDistribution)    (completed : d.probabilities = p ++ [1 - p.sum]) :    FiniteLawMatches (.discrete p.length) .mean p [(1, d.mean)] := by  apply finiteLawMatches_singleton  simp only [primitiveExpr, reduce, isValue_list_fold, ↓reduceIte, realListValue?_fold,    List.length_map, DiscreteLaws.completed_mean p d completed]theorem remainderDistribution_probabilities (p : List Rat) (d : Checking.FiniteDistribution)    (checked : Checking.remainderDistribution p = .ok d) :    d.probabilities = p ++ [1 - p.sum] := by  unfold Checking.remainderDistribution Checking.finiteDistribution at checked  split at checked  · split at checked    · cases checked; rfl    · cases checked  · cases checkedtheorem finiteLawMatches_uniform_mean (a b : Rat) (domain : a ≤ b) :    FiniteLawMatches .uniform .mean [a, b] [(1, (a + b) / 2)] := by  apply finiteLawMatches_singleton  have h : (a : ℝ) ≤ b := by exact_mod_cast domain  simp [primitiveExpr, reduce, Expr.isValue, realValue?, uniformFiber, h]theorem finiteLawMatches_gaussian_mean (a v : Rat) (domain : 0 ≤ v) :    FiniteLawMatches .gaussian .mean [a, v] [(1, a)] := by  apply finiteLawMatches_singleton  have h : (0 : ℝ) ≤ v := by exact_mod_cast domain  simp [primitiveExpr, reduce, Expr.isValue, realValue?, gaussianFiber, h]theorem finiteLawMatches_poisson_mean (a : Rat) (domain : 0 ≤ a) :    FiniteLawMatches .poisson .mean [a] [(1, a)] := by  apply finiteLawMatches_singleton  have h : (0 : ℝ) ≤ a := by exact_mod_cast domain  simp [primitiveExpr, reduce, Expr.isValue, realValue?, poissonFiber, h]theorem finiteLawMatches_exponential_mean (a : Rat) (domain : 0 < a) :    FiniteLawMatches .exponential .mean [a] [(1, 1 / a)] := by  apply finiteLawMatches_singleton  have h : (0 : ℝ) < a := by exact_mod_cast domain  simp [primitiveExpr, reduce, Expr.isValue, realValue?, exponentialFiber, h]theorem finiteLawMatches_beta_mean (a b : Rat) (ha : 0 < a) (hb : 0 < b) :    FiniteLawMatches .beta .mean [a, b] [(1, a / (a + b))] := by  apply finiteLawMatches_singleton  have h0 : (0 : ℝ) < a := by exact_mod_cast ha  have h1 : (0 : ℝ) < b := by exact_mod_cast hb  simp [primitiveExpr, reduce, Expr.isValue, realValue?, betaFiber, h0, h1]theorem finiteLawMatches_gamma_mean (a b : Rat) (ha : 0 < a) (hb : 0 < b) :    FiniteLawMatches .gamma .mean [a, b] [(1, a / b)] := by  apply finiteLawMatches_singleton  have h0 : (0 : ℝ) < a := by exact_mod_cast ha  have h1 : (0 : ℝ) < b := by exact_mod_cast hb  simp [primitiveExpr, reduce, Expr.isValue, realValue?, gammaFiber, h0, h1]/-- Successful executable finite laws preserve exact mass and the complete realsampling measure. Unsupported or invalid calls cannot satisfy the premise. -/theorem finiteLaw_sound (op : Op) (kind : DistributionAction) (arguments : List Rat)    (outcomes : List (Rat × Rat)) (success : finiteLaw op kind arguments = .ok outcomes) :    FiniteLawMatches op kind arguments outcomes := by  cases op with  | discrete n =>    by_cases arity : arguments.length = n    · cases checked : Checking.remainderDistribution arguments with      | error message =>        simp [finiteLaw, arity, checked, Except.mapError, bind, Except.bind] at success      | ok d =>        have completed := remainderDistribution_probabilities arguments d checked        subst n        cases kind with        | sample affinity =>          simp only [finiteLaw, BEq.rfl, ↓reduceIte, bind, Except.bind, Except.mapError, checked,            beq_iff_eq, reduceCtorEq, pure, Except.pure, Except.ok.injEq] at success          subst outcomes          exact finiteLawMatches_discrete_sample affinity arguments d completed        | mean =>          simp only [finiteLaw, BEq.rfl, ↓reduceIte, bind, Except.bind, Except.mapError, checked,            pure, Except.pure, Except.ok.injEq] at success          subst outcomes          exact finiteLawMatches_discrete_mean arguments d completed    · simp [finiteLaw, arity, bind, Except.bind, throw] at success  | _ =>    rcases arguments with _ | ⟨a, _ | ⟨b, _ | ⟨c, rest⟩⟩⟩ <;>      cases kind <;>      simp only [finiteLaw, supportedDraw] at success    all_goals split_ifs at success <;> simp_all only [Bool.false_eq_true, not_true_eq_false,      not_false_eq_true, beq_iff_eq, reduceCtorEq, bind, Except.bind, throw, BEq.rfl, pure,      Except.pure, not_le, Except.ok.injEq, one_div, not_lt, Bool.and_eq_true, decide_eq_true_eq,      not_and]    all_goals subst outcomes    all_goals try { simpa only [one_div] using finiteLawMatches_exponential_mean a (by assumption) }    all_goals aesop (add safe apply [finiteLawMatches_bernoulli_sample,      finiteLawMatches_bernoulli_mean, finiteLawMatches_uniform_mean,      finiteLawMatches_gaussian_mean, finiteLawMatches_poisson_mean,        finiteLawMatches_exponential_mean,      finiteLawMatches_beta_mean, finiteLawMatches_gamma_mean])theorem isProbabilityMeasure_outcomeMeasure (op : Op) (kind : DistributionAction)    (arguments : List Rat)    (outcomes : List (Rat × Rat)) (success : finiteLaw op kind arguments = .ok outcomes) :    IsProbabilityMeasure (outcomeMeasure outcomes) where  measure_univ := by    have law := finiteLaw_sound op kind arguments outcomes success    rw [outcomeMeasure_univ outcomes law.1, law.2.1]    simptheorem isValue_primitiveExpr (site : DistributionAction × Op) (arguments : List Expr) :    (primitiveExpr site arguments).isValue = false := by  rcases site with ⟨kind, op⟩  cases op <;>    rcases arguments with _ | ⟨a, _ | ⟨b, _ | ⟨c, rest⟩⟩⟩ <;>    rfltheorem reduce_stackExpr_primitiveExpr (site : DistributionAction × Op) (arguments : List Rat)    (outcomes : List (Rat × Rat)) (success : finiteLaw site.2 site.1 arguments = .ok outcomes)    (stack : List Frame) (shape : ∀ frame ∈ stack, FrameShape frame) :    reduce (stackExpr stack (primitiveExpr site (arguments.map fun (q : Rat) ↦ .real (q : ℝ)))) =      .sample site (outcomeMeasure outcomes) (fun x ↦ stackExpr stack (.real x)) := by  rw [(reduce_stackExpr stack shape _ (isValue_primitiveExpr _ _)).2,    (finiteLaw_sound _ _ _ _ success).2.2]  rfltheorem step_deliver_draw (site : DistributionAction × Op) (arguments : List Rat) (x : Rat)    (environment : List Value) (stack : List Frame) (outcomes : List (Rat × Rat))    (success : finiteLaw site.2 site.1 (arguments ++ [x]) = .ok outcomes) :    step (.deliver (.number x) (.draw site [] environment arguments :: stack)) =      .ok (.next (.sample site (arguments ++ [x]))        (outcomes.map fun (p, y) ↦ (p, .deliver (.number y) stack))) := by  change (finiteLaw site.2 site.1 (arguments ++ [x]) >>= fun outcomes ↦    pure (Step.next (.sample site (arguments ++ [x]))      (outcomes.map fun (p, y) ↦ (p, .deliver (.number y) stack)))) = _  rw [success]  rfltheorem reduce_stateExpr_draw (site : DistributionAction × Op) (arguments : List Rat) (x : Rat)    (environment : List Value) (stack : List Frame) (outcomes : List (Rat × Rat))    (success : finiteLaw site.2 site.1 (arguments ++ [x]) = .ok outcomes)    (shape : ∀ frame ∈ stack, FrameShape frame) :    reduce (stateExpr (.deliver (.number x) (.draw site [] environment arguments :: stack))) =      .sample site (outcomeMeasure outcomes) (fun y ↦ stackExpr stack (.real y)) := by  simpa only [stateExpr, stackExpr, List.foldl_cons, frameExpr, valueExpr,    List.map_append, List.map_cons, List.map_nil] using    reduce_stackExpr_primitiveExpr site (arguments ++ [x]) outcomes success stack shapetheorem valueExpr_probabilities (value : Value) (p : List Rat)    (read : value.probabilities? = some p) :    valueExpr value = (p.map fun q ↦ .real (q : ℝ)).foldr Expr.cons .nil := by  cases value with  | cons head tail =>    cases head <;> simp only [Value.probabilities?] at read <;> try contradiction    cases tailEq : tail.probabilities? with    | none => simp [tailEq] at read    | some ps =>      simp [tailEq] at read      subst p      simp [valueExpr, valueExpr_probabilities tail ps tailEq]  | nil => cases read; simp [valueExpr]  | _ => cases readtermination_by sizeOf valuetheorem reduce_stateExpr_discrete (kind : DistributionAction) (value : Value) (p : List Rat)    (read : value.probabilities? = some p) (stack : List Frame) (outcomes : List (Rat × Rat))    (success : finiteLaw (.discrete p.length) kind p = .ok outcomes)    (shape : ∀ frame ∈ stack, FrameShape frame) :    reduce (stateExpr (.deliver value (.discrete kind :: stack))) =      .sample (kind, .discrete p.length) (outcomeMeasure outcomes)        (fun y ↦ stackExpr stack (.real y)) := by  simpa only [stateExpr, stackExpr, List.foldl_cons, frameExpr,    valueExpr_probabilities value p read, primitiveExpr] using    reduce_stackExpr_primitiveExpr (kind, .discrete p.length) p outcomes success stack shapeend Determinize.Proof.FiniteModel