Documentation

Determinize.Proof.Traces.CompactReplay

The compact replay as a measurable kernel #

Proof.Traces.outputGivenTraceAt replays a program along a compact trace of general-affinity draws. This file packages it as an s-finite kernel in the trace and the expression (compactReplayKernel), proves the one-step unfolding lemmas the lockstep arguments use, bounds the total mass of Proof.Traces.outputGivenTrace by one, and builds the Markov kernel that agrees with it wherever it has mass one. Lemmas about Proof.Traces.outputGivenTraceAt are named ogtAt_* throughout this file.

Unfolding lemmas #

theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_value (depth : ℕ) {expression : Spec.Paper.Expr} (value : expression.isValue = true) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression tape = 0
theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_next (depth : ℕ) {expression next : Spec.Paper.Expr} (notValue : expression.isValue ≠ true) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.next next) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression tape = Traces.outputGivenTraceAt depth next tape
theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_stuck (depth : ℕ) {expression : Spec.Paper.Expr} (notValue : expression.isValue ≠ true) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.stuck) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression tape = 0
theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_sampleE (depth : ℕ) {expression : Spec.Paper.Expr} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} {fiber : MeasureTheory.Measure ℝ} {continuation : ℝ → Spec.Paper.Expr} (notValue : expression.isValue ≠ true) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation) (notGeneration : siteOp site = none) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression tape = fiber.bind fun (value : ℝ) => Traces.outputGivenTraceAt depth (continuation value) tape

An expectation-affinity draw, or a mean site, is integrated and leaves the tape alone.

theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_sampleG (depth : ℕ) {expression : Spec.Paper.Expr} {op : Spec.Paper.Op} {fiber : MeasureTheory.Measure ℝ} {continuation : ℝ → Spec.Paper.Expr} (notValue : expression.isValue ≠ true) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample (Spec.Paper.DistributionAction.sample Spec.Paper.Affinity.G, op) fiber continuation) (value : ℝ) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression ((op, value) :: tape) = Traces.outputGivenTraceAt depth (continuation value) tape

A general-affinity draw is read from the tape when the primitive fits.

theorem Determinize.Proof.StepTraces.outputGivenTraceAt_succ_sampleG_mismatch (depth : ℕ) {expression : Spec.Paper.Expr} {op op' : Spec.Paper.Op} {fiber : MeasureTheory.Measure ℝ} {continuation : ℝ → Spec.Paper.Expr} (notValue : expression.isValue ≠ true) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample (Spec.Paper.DistributionAction.sample Spec.Paper.Affinity.G, op) fiber continuation) (mismatch : op ≠ op') (value : ℝ) (tape : DrawTrace) :
Traces.outputGivenTraceAt (depth + 1) expression ((op', value) :: tape) = 0

The value unit, the sink of a rejected execution, has no output at any depth.

The active generation site determines the reduction #

When the skeleton names an active general-affinity site, reduction samples at it with that primitive, or is stuck on operands that are values but not reals.

The compact replay kernel #

The active general-affinity site of the expression fits the head of the tape.

Equations
  • One or more equations did not get rendered due to their size.
Instances For

    One replay step: a deterministic step or an expectation-affinity draw leaves the tape alone; a general-affinity draw consumes the head of the tape when its primitive fits, and stops otherwise.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For

      The compact replay at a fixed depth, jointly measurable in the tape and the expression.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Determinize.Proof.StepTraces.compactReplayKernel_apply (depth : ℕ) (tape : DrawTrace) (expression : Spec.Paper.Expr) :
        (compactReplayKernel depth).kernel (tape, expression) = Traces.outputGivenTraceAt depth expression tape
        theorem Determinize.Proof.StepTraces.measurable_outputGivenTraceAt_continuation (depth : ℕ) {expression : Spec.Paper.Expr} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} {fiber : MeasureTheory.Measure ℝ} {continuation : ℝ → Spec.Paper.Expr} (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation) (tape : DrawTrace) :
        Measurable fun (value : ℝ) => Traces.outputGivenTraceAt depth (continuation value) tape

        The compact replay at every depth, summed: Proof.Traces.outputGivenTrace as a kernel.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For

          Total mass #

          Where a fixed-depth replay already has mass one, it is the whole replay law: a finite measure below another of the same total mass equals it.

          A Markov version and a measurability lemma #

          Proof.Traces.outputGivenTrace where it has mass one, the Dirac mass at 0 elsewhere.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For

            The traces on which a kernel is the Dirac mass at a measurable function form a measurable set.