Source lean/Determinize/Proof/Examples.lean
import Determinize.Theoremsnamespace Determinize.Proof.Examplesopen MeasureTheory Determinize.Spec.Paper Determinize.Spec.Tracesdef uniform (affinity : Affinity) : Expr := .uniform (.sample affinity) (.real 0) (.real 1)theorem typed_uniform (affinity : Affinity) : Typed context (uniform affinity) (.float affinity) :=  .uniform .real .realdef nestedAffine : Expr := .uniform (.sample .E) (uniform .E) (.add (.real 2) (.real 3))def nestedGeneral : Expr := .gaussian (.sample .E) (.real 0) (uniform .G)def reciprocal : Expr :=  .letE (uniform .E)    (.letE (uniform .G)      (.add (.bvar 1)        (.div (.real 1) (.bvar 0))))example : Typed [] nestedAffine (.float .E) := .uniform (typed_uniform .E) (.add .real .real)example : Typed [] nestedGeneral (.float .E) := .gaussian .real (typed_uniform .G)theorem typed_reciprocal : Typed [] reciprocal (.float .E) :=  .letE (typed_uniform .E) (.letE (typed_uniform .G)    (.add (.bvar (.tail .head)) (.div .real (.bvar .head))))example : reduce nestedGeneral =    .sample (.sample .G, .uniform) (uniformFiber (.sample .G) 0 1)      (fun value ↦ .gaussian (.sample .E) (.real 0) (.real value)) := by  simp [nestedGeneral, uniform, reduce, Expr.isValue, realValue?, Action.wrap, Function.comp_def]example : reduce nestedGeneral.determinize =    .sample (.sample .G, .uniform) (uniformFiber (.sample .G) 0 1)      (fun value ↦ .gaussian .mean (.real 0) (.real value)) := by  simp [nestedGeneral, uniform, Expr.determinize, DistributionAction.determinize, reduce,    Expr.isValue,    realValue?, Action.wrap, Function.comp_def]example : reduce nestedAffine =    .sample (.sample .E, .uniform) (uniformFiber (.sample .E) 0 1)      (fun value ↦ .uniform (.sample .E) (.real value) (.add (.real 2) (.real 3))) := by  simp [nestedAffine, uniform, reduce, Expr.isValue, realValue?, Action.wrap, Function.comp_def]-- A literal takes either affinity, so a product of literals types at both affinities.example : Typed [] (.mul (.real 2) (.real 1)) (.float .E) := .mul .real .realexample : Typed [] (.mul (.real 2) (.real 1)) (.float .G) := .mul .real .real-- The general-affinity factor of an expectation-affinity product stands on the left: an-- expectation-affinity draw may be scaled from the left, not from the right, and not squared.example : Typed [] (.mul (.real 2) (uniform .E)) (.float .E) := .mul .real (typed_uniform .E)private theorem not_typed_uniformE_G : ¬ Typed context (uniform .E) (.float .G) := by  intro typed  generalize he : uniform .E = expression at typed  generalize ht : Ty.float .G = ty at typed  induction typed  case sub h sub ih =>    cases sub <;> cases ht    exact ih he rfl  all_goals cases ht <;> simp [uniform] at heprivate theorem not_typed_mul_uniformE (right : Expr) :    ¬ Typed context (.mul (uniform .E) right) ty := by  intro typed  generalize he : Expr.mul (uniform .E) right = expression at typed  induction typed  case sub h sub ih => exact ih he  case mul left right ihl ihr =>    cases he    exact not_typed_uniformE_G left  all_goals cases heexample : ¬ Typed [] (.mul (uniform .E) (.real 2)) (.float .E) := not_typed_mul_uniformE _example : ¬ Typed [] (.mul (uniform .E) (uniform .E)) (.float .E) := not_typed_mul_uniformE _private theorem domainSafe_of_next {expression next : Expr}    (reduction : reduce expression = .next next) (safe : DomainSafe next) :    DomainSafe expression := by  intro fuel  cases fuel with  | zero => trivial  | succ fuel =>    rw [DomainSafeAt]    split    · trivial    · rw [reduction]      exact safe fuelprivate theorem domainSafe_of_sample {expression : Expr} {fiber : Measure ℝ}    {continuation : ℝ → Expr}    (reduction : reduce expression = .sample site fiber continuation) (mass : fiber Set.univ = 1)    (safe : ∀ᵐ value ∂fiber, DomainSafe (continuation value)) : DomainSafe expression := by  intro fuel  cases fuel with  | zero => trivial  | succ fuel =>    rw [DomainSafeAt]    split    · trivial    · rw [reduction]      exact ⟨mass, safe.mono (fun _ h ↦ h fuel)⟩private theorem domainSafe_real (value : ℝ) : DomainSafe (.real value) := by  intro fuel  cases fuel <;> simp [DomainSafeAt, Expr.isValue]private theorem domainSafe_let_uniform (affinity : Affinity) (body : Expr)    (safe : ∀ᵐ value ∂uniformFiber (.sample affinity) 0 1,      DomainSafe (body.substHead (.real value))) :    DomainSafe (.letE (uniform affinity) body) := by  let μ := uniformFiber (.sample affinity) 0 1  have reduction : reduce (.letE (uniform affinity) body) =      .sample (.sample affinity, .uniform) μ        (fun value ↦ .letE (.real value) body) := by    simp [uniform, reduce, Expr.isValue, realValue?, Action.wrap, Function.comp_def, μ]  apply domainSafe_of_sample reduction  · simp [μ, uniformFiber, uniformMeasure, Real.volume_Icc]  · filter_upwards [safe] with value valueSafe    exact domainSafe_of_next (by simp [reduce, Expr.isValue]) valueSafetheorem domainSafe_reciprocal : DomainSafe reciprocal := by  apply domainSafe_let_uniform .E  apply Filter.Eventually.of_forall  intro x  simp only [Expr.substHead, Expr.substAt, Expr.mapVars, Expr.shift, uniform, zero_add, ↓reduceIte,    zero_ne_one, not_lt_zero]  change DomainSafe (.letE (uniform .G)    (.add (.real x) (.div (.real 1) (.bvar 0))))  apply domainSafe_let_uniform .G  have nonzero : ∀ᵐ y ∂uniformFiber (.sample .G) 0 1, y ≠ 0 := by    simpa [uniformFiber, uniformMeasure] using      (ae_restrict_of_ae (s := Set.Icc (0 : ℝ) 1) (volume.ae_ne (0 : ℝ)))  filter_upwards [nonzero] with y nonzero  simp only [Expr.substHead, Expr.substAt, Expr.mapVars, ↓reduceIte, Expr.shift]  apply domainSafe_of_next (next := .add (.real x) (.real (1 / y)))  · simp [reduce, Expr.isValue, realValue?, Action.wrap, nonzero]  apply domainSafe_of_next (next := .real (x + 1 / y))  · simp [reduce, Expr.isValue, realValue?]  exact domainSafe_real _/-- This concrete trace result requires no global integrability premise. -/example : Determinize.Proof.Traces.MeanOnTraces reciprocal reciprocal.determinize :=  (Traces.meanOnTraces_determinize .E reciprocal typed_reciprocal domainSafe_reciprocal).2/-- A general-affinity draw scales an expectation-affinity draw from the left. -/def scaledSample : Expr := .letE (uniform .G) (.mul (.bvar 0) (uniform .E))theorem typed_scaledSample : Typed [] scaledSample (.float .E) :=  .letE (typed_uniform .G) (.mul (.bvar .head) (typed_uniform .E))theorem domainSafe_scaledSample : DomainSafe scaledSample := by  apply domainSafe_let_uniform .G  apply Filter.Eventually.of_forall  intro y  simp only [Expr.substHead, Expr.substAt, Expr.mapVars, ↓reduceIte, Expr.shift, uniform]  change DomainSafe (.mul (.real y) (uniform .E))  let μ := uniformFiber (.sample .E) 0 1  refine domainSafe_of_sample (site := (.sample .E, .uniform)) (fiber := μ)    (continuation := fun value ↦ .mul (.real y) (.real value)) ?_ ?_ ?_  · simp [uniform, reduce, Expr.isValue, realValue?, Action.wrap, Function.comp_def, μ]  · simp [μ, uniformFiber, uniformMeasure, Real.volume_Icc]  · apply Filter.Eventually.of_forall    intro value    apply domainSafe_of_next (next := .real (y * value))    · simp [reduce, Expr.isValue, realValue?]    exact domainSafe_real _example : Determinize.Proof.Traces.MeanOnTraces scaledSample scaledSample.determinize :=  (Traces.meanOnTraces_determinize .E scaledSample typed_scaledSample domainSafe_scaledSample).2def loopFunction : Expr :=  .fix    (.app (.bvar 1) (.bvar 0))def loop : Expr := .app loopFunction .unitexample : Typed [] loop (.float .E) :=  .app (.fix (.app (.bvar (.tail .head)) (.bvar .head))) .unittheorem reduce_loop : reduce loop = .next loop := by  simp [loop, loopFunction, reduce, Expr.isValue, Expr.substTwo, Expr.substAt, Expr.shift,    Expr.mapVars]example : DomainSafe loop := by  intro fuel  induction fuel with  | zero => trivial  | succ fuel ih =>    rw [DomainSafeAt, ite_eq_right (by simp [loop, Expr.isValue]), reduce_loop]    exact ihexample : traceAndOutputLaw loop = 0 := by  have h (depth : Nat) : traceAndOutputLawAt depth loop = 0 := by    induction depth with    | zero => simp [loop, traceAndOutputLawAt]    | succ depth ih =>      rw [Traces.exact_succ_next depth loop loop (by simp [loop, Expr.isValue]) reduce_loop, ih]  simp [traceAndOutputLaw, h]def affineMean : Expr :=  .letE (uniform .E) (.uniform .mean (.bvar 0) (.add (.bvar 0) (.real 2)))theorem typed_affineMean : Typed [] affineMean (.float .E) :=  .letE (typed_uniform .E) (.uniformMean (.bvar .head) (.add (.bvar .head) .real))theorem domainSafe_affineMean : DomainSafe affineMean := by  apply domainSafe_let_uniform .E  apply Filter.Eventually.of_forall  intro x  simp only [Expr.substHead, Expr.substAt, Expr.mapVars, Expr.shift]  apply domainSafe_of_next (next := .uniform .mean (.real x) (.real (x + 2)))  · simp [reduce, Expr.isValue, realValue?, Action.wrap]  apply domainSafe_of_sample (site := (.mean, .uniform)) (fiber := uniformFiber .mean x (x + 2))    (continuation := Expr.real)  · simp [reduce, Expr.isValue, realValue?]  · simp [uniformFiber]  · exact Filter.Eventually.of_forall domainSafe_realexample : Determinize.Proof.Traces.MeanOnTraces affineMean affineMean.determinize :=  (Traces.meanOnTraces_determinize .E affineMean typed_affineMean domainSafe_affineMean).2example : bigStepMeasure affineMean.determinize Set.univ = bigStepMeasure affineMean Set.univ :=  Determinize.Theorems.output_mass_preservation affineMean typed_affineMean    domainSafe_affineMeandef meanDenominator : Expr := .div (uniform .E) (.uniform .mean (.real 1) (.real 3))example : Typed [] meanDenominator (.float .E) :=  .div (typed_uniform .E) (.uniformMean .real .real)example (affinity : Affinity) : Typed [] (.uniform .mean (.real 1) (.real 3)) (.float affinity) :=  .uniformMean .real .realdef meanWithDraw : Expr := .gaussian .mean (.real 0) (uniform .G)example : Typed [] meanWithDraw (.float .G) := .gaussianMean .real (typed_uniform .G)example : reduce meanWithDraw =    .sample (.sample .G, .uniform) (uniformFiber (.sample .G) 0 1)      (fun value ↦ .gaussian .mean (.real 0) (.real value)) := by  simp [meanWithDraw, uniform, reduce, Expr.isValue, realValue?, Action.wrap, Function.comp_def]example : traceAndOutputLawAt 1 (.uniform .mean (.real 1) (.real 3)) =    Measure.dirac ([], (2 : ℝ)) := by  norm_num [traceAndOutputLawAt, reduce, Expr.isValue, realValue?, uniformFiber]  have recordMean (v : ℝ) : (record (.mean, .uniform) v : Output → Output) = id := rfl  simp_rw [recordMean, Measure.map_id]  exact Measure.dirac_bind    (show Measurable (fun value : ℝ ↦ Measure.dirac (([] : Trace), value)) from      Measure.measurable_dirac.comp (measurable_const.prodMk measurable_id)) 2example : traceAndOutputLawAt 1 (.uniform .mean (.real 3) (.real 1)) = 0 := by  norm_num [traceAndOutputLawAt, reduce, Expr.isValue, realValue?, uniformFiber]example : ¬ DomainSafe (.uniform .mean (.real 3) (.real 1)) := by  intro safe  have h := safe 1  norm_num [DomainSafeAt, reduce, Expr.isValue, realValue?, uniformFiber] at hexample : Typed [] (.uniform .mean (.real 3) (.real 1)) (.float .E) :=  .uniformMean .real .realopen scoped ENNRealprivate theorem runningProbabilityAt_real (depth : Nat) (r : ℝ) :    runningProbabilityAt depth (.real r) = 0 := by  cases depth <;> simp [runningProbabilityAt, Expr.isValue]private theorem runningProbabilityAt_reject (depth : Nat) :    runningProbabilityAt depth .reject = 1 := by  induction depth with  | zero => rfl  | succ depth ih => simpa [runningProbabilityAt, reduce, Expr.isValue] using ihexample (r : ℝ) : divergenceProbability (.real r) = 0 := by  simp [divergenceProbability, runningProbabilityAt_real]example : divergenceProbability .reject = 1 := by  simp [divergenceProbability, runningProbabilityAt_reject]example : divergenceProbability (.div (.real 1) (.real 0)) = 0 := by  apply le_antisymm _ zero_le  calc    divergenceProbability (.div (.real 1) (.real 0)) ≤        runningProbabilityAt 1 (.div (.real 1) (.real 0)) := iInf_le _ 1    _ = 0 := by simp [runningProbabilityAt, reduce, Expr.isValue, realValue?]private noncomputable def halfReject : Expr :=  .ite (.lt (.bernoulli (.sample .G) (.real (1 / 2))) (.real 1)) (.real 7) .rejectprivate theorem runningProbabilityAt_halfReject (n : Nat) :    runningProbabilityAt (n + 3) halfReject = 1 / 2 := by  norm_num [halfReject, runningProbabilityAt, reduce, Expr.isValue, bernoulliFiber,    Action.wrap, realValue?, runningProbabilityAt_real, runningProbabilityAt_reject,      ENNReal.ofReal_div_of_pos]example : divergenceProbability halfReject = 1 / 2 := by  apply le_antisymm  · exact (iInf_le _ 3).trans_eq (runningProbabilityAt_halfReject 0)  · apply le_iInf    intro n    match n with    | 0 | 1 | 2 =>      norm_num [halfReject, runningProbabilityAt, reduce, Expr.isValue, bernoulliFiber,        Action.wrap, realValue?, ENNReal.ofReal_div_of_pos]    | n + 3 => exact (runningProbabilityAt_halfReject n).geexample : divergenceProbability loop = 1 := by  have running (depth : Nat) : runningProbabilityAt depth loop = 1 := by    induction depth with    | zero => rfl    | succ depth ih =>      simpa [runningProbabilityAt, loop, loopFunction, Expr.isValue, reduce,        Expr.substTwo, Expr.substAt, Expr.shift, Expr.mapVars] using ih  simp [divergenceProbability, running]end Determinize.Proof.Examples