Source lean/Determinize/Proof/Traces/CompactSoundness.lean
import Determinize.Proof.Traces.CompactFiberSoundnessimport Determinize.Proof.Traces.Factorizationimport Determinize.Proof.Traces.Mass/-!# Compact trace soundnessThe detailed step-trace results are transported to compact traces of general-affinity draws, with`Proof.Traces.outputGivenTrace` as the fiber: the Markov version `normalizedOutputGivenTrace`factors the joint laws, and almost surely it agrees with `outputGivenTrace` on the source, whileon the target `outputGivenTrace` is the Dirac mass at the target output.-/namespace Determinize.Proof.Tracesopen MeasureTheory ProbabilityTheory Determinize.Spec.Paper Determinize.Spec.Tracesopen Determinize.Proof.Paperopen StepTraces (retain measurable_retain FiberSound mapTraceOutput measurable_mapTraceOutput  normalizedOutputGivenTrace normalizedOutputGivenTrace_eq outputGivenTraceKernel  outputGivenTraceKernel_apply outputGivenTrace_eq_outputGivenTraceAt  compactFiber_apply compactHistoryReplay_nil measurableSet_kernel_eq_dirac)open scoped ProbabilityTheorynoncomputable sectiontheorem joint_eq_detailed (e : Expr) :    traceAndOutputLaw e = (StepTraces.jointMeasure e).map eraseOutput := by  rw [traceAndOutputLaw, StepTraces.jointMeasure,    Measure.map_sum measurable_eraseOutput.aemeasurable]  simp_rw [exact_eq_detailed]theorem correspondence (e : Expr) :    (traceAndOutputLaw e).map Prod.snd = Determinize.Spec.Paper.bigStepMeasure e := by  rw [joint_eq_detailed, Measure.map_map measurable_snd measurable_eraseOutput]  exact StepTraces.correspondence etheorem exact_succ_next (depth : Nat) (e next : Expr) (nv : e.isValue ≠ true)    (h : reduce e = .next next) :    traceAndOutputLawAt (depth + 1) e = traceAndOutputLawAt depth next := by  simp [traceAndOutputLawAt, nv, h]/-! ### The compact replay as the fiber -//-- `Proof.Traces.outputGivenTrace` normalized to a Markov kernel, as an s-finite kernel. -/def normalizedKernel (source : Expr) : SFiniteKernel Trace ℝ :=  ⟨normalizedOutputGivenTrace source, inferInstance⟩instance normalizedKernel_markov (source : Expr) :    IsMarkovKernel (normalizedKernel source).kernel :=  inferInstanceAs (IsMarkovKernel (normalizedOutputGivenTrace source))/-- The normalized compact replay read through the retained draws of a detailed trace. -/def normalizedFiber (source : Expr) : SFiniteKernel StepTraces.Trace ℝ :=  SFiniteKernel.pullback (normalizedKernel source) retain measurable_retaintheorem measurableSet_selfReplay_compact (target : Expr) :    MeasurableSet {q : Output | outputGivenTrace target q.1 = Measure.dirac q.2} := by  let κ := SFiniteKernel.pullback ⟨outputGivenTraceKernel target, inferInstance⟩    (Prod.fst : Output → Trace) measurable_fst  have := κ.sfinite  have eq : {q : Output | outputGivenTrace target q.1 = Measure.dirac q.2} =      {q | κ.kernel q = Measure.dirac q.2} := by    ext q    simp only [Set.mem_ofPred_eq, κ, MeasurableActionFamily.pullback_apply,      outputGivenTraceKernel_apply]  rw [eq]  exact measurableSet_kernel_eq_dirac κ.kernel measurable_sndtheorem measurableSet_massOne_compact (source : Expr) :    MeasurableSet {q : Output | outputGivenTrace source q.1 Set.univ = 1} := by  have eq : {q : Output | outputGivenTrace source q.1 Set.univ = 1} =      Prod.fst ⁻¹' {trace | outputGivenTraceKernel source trace Set.univ = 1} := by    ext q    simp only [Set.mem_ofPred_eq, Set.mem_preimage, outputGivenTraceKernel_apply]  rw [eq]  exact (measurableSet_eq_fun ((outputGivenTraceKernel source).measurable_coe MeasurableSet.univ)    measurable_const).preimage measurable_fst/-- On the detailed joint laws, the normalized compact replay is a sound fiber. -/theorem joint_normalized_fiberSound (source : Expr) (typed : Typed [] source (.float .E))    (safe : DomainSafe source) :    FiberSound (normalizedFiber source) (StepTraces.jointMeasure source)      (StepTraces.jointMeasure source.determinize) := by  apply StepTraces.FiberSound.sum  intro depth  have sound := StepTraces.compact_exactDepth_source_fiberSound source typed safe depth  have transported := StepTraces.FiberSound.mapTrace_ae _ (normalizedFiber source) _ _ sound id    measurable_id (by      filter_upwards [sound.2] with point good      have massOne : outputGivenTraceAt depth source (retain point.1) Set.univ = 1 := by        have h := good.1        rwa [compactFiber_apply, compactHistoryReplay_nil] at h      change (normalizedFiber source).kernel point.1 = _      rw [normalizedFiber, MeasurableActionFamily.pullback_apply, compactFiber_apply,        compactHistoryReplay_nil]      change normalizedOutputGivenTrace source (retain point.1) = _      rw [normalizedOutputGivenTrace_eq _ _ (by        rw [outputGivenTrace_eq_outputGivenTraceAt depth source _ massOne]        exact massOne), outputGivenTrace_eq_outputGivenTraceAt depth source _ massOne])  simpa only [show mapTraceOutput (id : StepTraces.Trace → StepTraces.Trace) = id from rfl,    Measure.map_id] using transported/-- On the compact joint laws, the normalized compact replay is a sound fiber. -/theorem compact_normalized_fiberSound (source : Expr) (typed : Typed [] source (.float .E))    (safe : DomainSafe source) :    FiberSound (normalizedKernel source) (traceAndOutputLaw source)        (traceAndOutputLaw source.determinize) := by  rw [joint_eq_detailed, joint_eq_detailed]  exact StepTraces.FiberSound.mapTrace _ _ _ _ (joint_normalized_fiberSound source typed safe)    retain measurable_retain    (fun trace ↦ by rw [normalizedFiber, MeasurableActionFamily.pullback_apply])/-- Almost every terminating target trace gives the source replay mass one. -/theorem compact_source_massOne (source : Expr) (typed : Typed [] source (.float .E))    (safe : DomainSafe source) :    ∀ᵐ q ∂traceAndOutputLaw source.determinize, outputGivenTrace source q.1 Set.univ = 1 := by  rw [joint_eq_detailed, ae_map_iff measurable_eraseOutput.aemeasurable    (measurableSet_massOne_compact source), StepTraces.jointMeasure, Measure.ae_sum_iff]  intro depth  filter_upwards [(StepTraces.compact_exactDepth_source_fiberSound source typed safe depth).2]    with point good  have massOne : outputGivenTraceAt depth source (retain point.1) Set.univ = 1 := by    have h := good.1    rwa [compactFiber_apply, compactHistoryReplay_nil] at h  change outputGivenTrace source (retain point.1) Set.univ = 1  rw [outputGivenTrace_eq_outputGivenTraceAt depth source _ massOne]  exact massOne/-- Replaying the target along its own compact trace returns its output. -/theorem compact_target_selfReplay (source : Expr) (typed : Typed [] source (.float .E))    (safe : DomainSafe source) :    ∀ᵐ q ∂traceAndOutputLaw source.determinize,      outputGivenTrace source.determinize q.1 = Measure.dirac q.2 := by  rw [joint_eq_detailed, ae_map_iff measurable_eraseOutput.aemeasurable    (measurableSet_selfReplay_compact source.determinize), StepTraces.jointMeasure,    Measure.ae_sum_iff]  intro depth  filter_upwards [StepTraces.target_selfReplay_source source typed safe depth] with point hp  change outputGivenTrace source.determinize (retain point.1) = Measure.dirac point.2  rw [outputGivenTrace_eq_outputGivenTraceAt depth _ _ (by rw [hp]; simp), hp]/-! ### The factorization with its almost-sure identifications -//-- Trace soundness for an expectation-affinity source, as a factorization by the normalizedcompact replay together with the identifications that give the public statement: almostsurely the source fiber is `outputGivenTrace` itself, and the target replay is the Dirac massat the target output. -/theorem soundness_data_of_E (source : Expr) (typed : Typed [] source (.float .E))    (safe : DomainSafe source) :    DomainSafe source.determinize ∧      TraceFactorization source source.determinize (normalizedOutputGivenTrace source)        (kernelMean (normalizedOutputGivenTrace source)) ∧      (∀ᵐ trace ∂traceLaw source,        outputGivenTrace source trace = normalizedOutputGivenTrace source trace) ∧      ∀ᵐ trace ∂traceLaw source,        outputGivenTrace source.determinize trace =            Measure.dirac (kernelMean (normalizedOutputGivenTrace source) trace) := by  refine ⟨domainSafe_determinize typed safe, ?_⟩  let ν := (traceAndOutputLaw source.determinize).map Prod.fst  let f := kernelMean (normalizedOutputGivenTrace source)  rcases (compact_normalized_fiberSound source typed safe).factorization    (traceAndOutputLaw_mass_le_one source.determinize) with ⟨hm, hf, hs, ht, hmean⟩  have hν : traceLaw source = ν := by    let : IsFiniteMeasure ν := ⟨hm.trans_lt (by simp)⟩    rw [traceLaw, hs]    exact Measure.fst_compProd ν (normalizedKernel source).kernel  change _ = ν ⊗ₘ _ at hs  change _ = ν.map (fun trace ↦ (trace, f trace)) at ht  change ∀ᵐ trace ∂ν, _ at hmean  rw [← hν] at hs ht hmean  have pairMeasurable : Measurable (fun trace : Trace ↦ (trace, f trace)) :=    measurable_id.prodMk hf  refine ⟨⟨inferInstance, hf, hs, ht, hmean⟩, ?_, ?_⟩  · have massOne := compact_source_massOne source typed safe    rw [ht] at massOne    filter_upwards [ae_of_ae_map pairMeasurable.aemeasurable massOne] with trace mass    exact (normalizedOutputGivenTrace_eq source trace mass).symm  · have dirac := compact_target_selfReplay source typed safe    rw [ht] at dirac    exact ae_of_ae_map pairMeasurable.aemeasurable dirac/-- Apply expectation-affinity soundness using silent subtyping for general-affinity programs. -/theorem soundness_data (affinity : Affinity) (program : Expr)    (typed : Typed [] program (.float affinity))    (safe : DomainSafe program) :    DomainSafe program.determinize ∧      TraceFactorization program program.determinize (normalizedOutputGivenTrace program)        (kernelMean (normalizedOutputGivenTrace program)) ∧      (∀ᵐ trace ∂traceLaw program,        outputGivenTrace program trace = normalizedOutputGivenTrace program trace) ∧      ∀ᵐ trace ∂traceLaw program,        outputGivenTrace program.determinize trace =            Measure.dirac (kernelMean (normalizedOutputGivenTrace program) trace) := by  cases affinity with  | E => exact soundness_data_of_E program typed safe  | G => exact soundness_data_of_E program (.sub typed .general) safe/-- Some trace factorization exists: the input of the corollaries. -/theorem meanOnTraces_determinize (affinity : Affinity) (program : Expr)    (typed : Typed [] program (.float affinity))    (safe : DomainSafe program) :    DomainSafe program.determinize ∧ MeanOnTraces program program.determinize :=  let ⟨targetSafe, factor, _, _⟩ := soundness_data affinity program typed safe  ⟨targetSafe, _, factor⟩/-- A measure composed with a kernel is the bind that pairs each point with its draw. -/theorem compProd_eq_traceThenOutput (traces : Measure Trace) [SFinite traces]    (fiber : Kernel Trace ℝ) [IsSFiniteKernel fiber] :    traces ⊗ₘ fiber = traceThenOutput traces fiber :=  StepTraces.compProd_eq_bind_pair traces fiber/-- Determinization returns the canonical replay mean on each terminating trace. -/theorem traceAndOutputLaw_determinize (program : Expr) (typed : Typed [] program (.float .E))    (safe : DomainSafe program) :    traceAndOutputLaw program.determinize =      (traceLaw program).map (fun trace ↦ (trace, replayMean program trace)) := by  obtain ⟨_, factor, sameFiber, _⟩ := soundness_data_of_E program typed safe  refine factor.2.2.2.1.trans (Measure.map_congr ?_)  filter_upwards [sameFiber] with trace same  simp only [kernelMean, replayMean, same]/-- Replay factorization and its conditional-mean property, used to identify the conditionallaws. -/theorem replay_soundness :  ∀ (program : Expr),    Typed [] program (.float .E) → DomainSafe program →      DomainSafe program.determinize ∧      traceAndOutputLaw program = traceThenOutput (traceLaw program) (outputGivenTrace program) ∧      traceAndOutputLaw program.determinize =        traceThenOutput (traceLaw program) (outputGivenTrace program.determinize) ∧      ∀ᵐ trace ∂traceLaw program,        Integrable id (outputGivenTrace program trace) ∧        outputGivenTrace program.determinize trace =          Measure.dirac (replayMean program trace) := by  intro program typed safe  let f := kernelMean (normalizedOutputGivenTrace program)  obtain ⟨targetSafe, factor, massAe, diracAe⟩ :=    soundness_data .E program typed safe  obtain ⟨markov, hf, hs, ht, hmean⟩ := factor  have := markov  refine ⟨targetSafe, ?_, ?_, ?_⟩  · rw [hs, compProd_eq_traceThenOutput, traceThenOutput, traceThenOutput]    exact Measure.bind_congr_right (massAe.mono fun trace h ↦ by simp only [h])  · rw [ht, traceThenOutput, ← Measure.bind_dirac_eq_map _      (show Measurable (fun trace : Trace ↦ (trace, f trace)) from measurable_id.prodMk hf)]    apply Measure.bind_congr_right    filter_upwards [diracAe] with trace h    rw [h, Measure.map_dirac' (show Measurable (fun value : ℝ ↦ (trace, value)) from      measurable_const.prodMk measurable_id)]  · filter_upwards [hmean, massAe, diracAe] with trace mean mass dirac    simp only [replayMean, mass]    exact ⟨mean.1, by rw [dirac, mean.2]⟩endend Determinize.Proof.Traces