import Determinize.Proof.Traces.CompactSoundnessimport Mathlib.Probability.Kernel.Disintegration.Unique/-!# The replay kernel as the regular conditional distribution`Traces.outputGivenTrace` is a finite kernel, and by trace soundness the joint law of the sourceis its trace law followed by the replay, the joint law of the target the same trace law followedby the target's replay. Mathlib's disintegration kernel is almost everywhere unique among thefinite kernels with this factorization property (`eq_condKernel_of_measure_eq_compProd`), soeach replay is a version of the regular conditional distribution of the output given the trace,and the almost-sure clause of trace soundness transfers to the conditional laws.-/namespace Determinize.Proof.Tracesopen MeasureTheory ProbabilityTheory Determinize.Spec.Paper Determinize.Spec.Tracesopen Determinize.Proof.Paperopen StepTraces (normalizedOutputGivenTrace outputGivenTraceKernel outputGivenTraceKernel_apply outputGivenTrace_mass_le_one)open scoped ProbabilityTheory/-- The compact replay is a finite kernel: its mass is at most one. -/instance isFiniteKernel_outputGivenTraceKernel (program : Expr) : IsFiniteKernel (outputGivenTraceKernel program) := ⟨1, ENNReal.one_lt_top, fun trace ↦ by rw [outputGivenTraceKernel_apply] exact outputGivenTrace_mass_le_one program trace⟩theorem outputGivenTraceKernel_coe (program : Expr) : ⇑(outputGivenTraceKernel program) = outputGivenTrace program := funext (outputGivenTraceKernel_apply program)/-- A joint law that is a trace law followed by the replay of `program` has that replay as itsdisintegration kernel, for almost every trace. -/theorem outputGivenTrace_ae_eq_condKernel (program : Expr) {traces : Measure Trace} [IsFiniteMeasure traces] {joint : Measure Output} [IsFiniteMeasure joint] (factor : joint = traceThenOutput traces (outputGivenTrace program)) (marginal : joint.fst = traces) : outputGivenTrace program =ᵐ[traces] joint.condKernel := by have compProd : joint = joint.fst ⊗ₘ outputGivenTraceKernel program := by rw [marginal, compProd_eq_traceThenOutput, outputGivenTraceKernel_coe, factor] have unique := eq_condKernel_of_measure_eq_compProd (outputGivenTraceKernel program) compProd rw [marginal] at unique filter_upwards [unique] with trace h rw [← h, outputGivenTraceKernel_apply]/-- The determinized program has the trace law of its source. -/theorem traceLaw_determinize (affinity : Affinity) (program : Expr) (typed : Typed [] program (.float affinity)) (safe : DomainSafe program) : traceLaw program.determinize = traceLaw program := by let output := kernelMean (normalizedOutputGivenTrace program) obtain ⟨-, ⟨-, measurableOutput, -, targetMap, -⟩, -, -⟩ := soundness_data affinity program typed safe have pairMeasurable : Measurable fun trace : Trace ↦ (trace, output trace) := measurable_id.prodMk measurableOutput calc traceLaw program.determinize = ((traceLaw program).map fun trace ↦ (trace, output trace)).map Prod.fst := by rw [traceLaw, targetMap] _ = traceLaw program := by rw [Measure.map_map measurable_fst pairMeasurable] exact Measure.map_id/-- The public conditional-law theorem: both replays are versions of the regular conditionaldistributions of the outputs given the trace, and trace soundness holds for those. -/theorem conditional_law (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : DomainSafe program.determinize ∧ traceLaw program.determinize = traceLaw program ∧ ∀ᵐ trace ∂traceLaw program, Integrable id ((traceAndOutputLaw program).condKernel trace) ∧ (traceAndOutputLaw program.determinize).condKernel trace = Measure.dirac (∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace) := by obtain ⟨targetSafe, sourceFactor, targetFactor, ae⟩ := replay_soundness program typed safe have sameTraces := traceLaw_determinize .E program typed safe have sourceAe := outputGivenTrace_ae_eq_condKernel program sourceFactor rfl have targetAe := outputGivenTrace_ae_eq_condKernel program.determinize targetFactor sameTraces refine ⟨targetSafe, sameTraces, ?_⟩ filter_upwards [ae, sourceAe, targetAe] with trace good sourceEq targetEq rw [← sourceEq, ← targetEq] exact good/-- Trace preservation: the first two clauses of `conditional_law`. -/theorem trace_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : DomainSafe program.determinize ∧ traceLaw program.determinize = traceLaw program := ⟨(conditional_law program typed safe).1, (conditional_law program typed safe).2.1⟩/-- Tracewise soundness: the almost-sure clause of `conditional_law`. -/theorem tracewise_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : ∀ᵐ trace ∂traceLaw program, Integrable id ((traceAndOutputLaw program).condKernel trace) ∧ (traceAndOutputLaw program.determinize).condKernel trace = Measure.dirac (∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace) := (conditional_law program typed safe).2.2/-- The target's output law is the trace law pushed forward by the source's conditional mean.The target's joint law is the trace law followed by the Dirac mass at the replay mean, whichagrees almost everywhere with the conditional mean because both describe the target'sconditional law. -/theorem determinized_output_law (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : bigStepMeasure program.determinize = (traceLaw program).map fun trace ↦ ∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace := by obtain ⟨-, ⟨-, measurableMean, -, targetMap, -⟩, -, targetDirac⟩ := soundness_data .E program typed safe obtain ⟨-, -, targetFactor, -⟩ := replay_soundness program typed safe have targetAe := outputGivenTrace_ae_eq_condKernel program.determinize targetFactor (traceLaw_determinize .E program typed safe) have meanAe : kernelMean (normalizedOutputGivenTrace program) =ᵐ[traceLaw program] fun trace ↦ ∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace := by filter_upwards [targetDirac, targetAe, tracewise_soundness program typed safe] with trace replay conditional sound rw [← dirac_eq_dirac_iff, ← replay, conditional, sound.2] have pairMeasurable : Measurable fun trace : Trace ↦ (trace, kernelMean (normalizedOutputGivenTrace program) trace) := measurable_id.prodMk measurableMean rw [← correspondence, targetMap, Measure.map_map measurable_snd pairMeasurable] exact Measure.map_congr meanAeend Determinize.Proof.Traces