Documentation

PolyFun.PFunctor.Free.Measure.ExpectedCharge

Expected charge of free programs #

PFunctor.OpSpec.expectedCharge ν c reads a call at a as costing c a, followed by the expected value of its continuation under the answer measure ν a: c a + ∫⁻ b, k b ∂ν a. Its fold at the zero leaf cost, wpFold (OpSpec.expectedCharge ν c) x fun _ => 0, is the expected charge of x. The spec is the worst-case reading OpSpec.charge c, whose fold is FreeM.cost c x, with the integral in place of the supremum.

Main statements #

The expected-charge spec #

noncomputable def PFunctor.OpSpec.expectedCharge {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) :

The expected-charge reading of answer measures ν: a call at a costs c a, followed by the expected value of its continuation under ν a.

Equations
Instances For
    @[simp]
    theorem PFunctor.OpSpec.expectedCharge_apply {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) (a : P.A) (k : P.B a → ENNReal) :
    expectedCharge ν c a k = c a + ∫⁻ (b : P.B a), k b ∂ν a
    theorem PFunctor.OpSpec.expectedCharge_mono {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) :

    The expected-charge reading is monotone in the continuation.

    theorem PFunctor.OpSpec.expectedCharge_le_charge {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) [∀ (a : P.A), MeasureTheory.IsSubprobabilityMeasure (ν a)] (c : P.A → ENNReal) (a : P.A) (k : P.B a → ENNReal) :
    expectedCharge ν c a k ≤ charge c a k

    Under subprobability answers, the expected charge of a call is at most its worst-case charge.

    Expected and worst-case charge #

    theorem PFunctor.FreeM.wpFold_expectedCharge_eq_add {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) {α : Type v} [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] (x : P.FreeM α) (post : α → ENNReal) :
    wpFold (OpSpec.expectedCharge ν c) x post = (wpFold (OpSpec.expectedCharge ν c) x fun (x : α) => 0) + wpFold (OpSpec.lintegral ν) x post

    Over discrete answers, the leaf costs split off: the expected charge-to-go is the expected charge plus the expectation of the leaf costs. Integration is additive on the measurable continuations that discrete answers give.

    theorem PFunctor.FreeM.wpFold_expectedCharge_eq_add_lintegral {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) {α : Type v} [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] [MeasurableSpace α] (x : P.FreeM α) {post : α → ENNReal} (hpost : Measurable post) :
    wpFold (OpSpec.expectedCharge ν c) x post = (wpFold (OpSpec.expectedCharge ν c) x fun (x : α) => 0) + ∫⁻ (r : α), post r ∂measureFold ν x

    Over discrete answers, the expected charge-to-go of a measurable leaf cost is the expected charge plus the integral of the leaf cost under the measure fold.

    theorem PFunctor.FreeM.wpFold_expectedCharge_le_costWith {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) {α : Type v} [∀ (a : P.A), MeasureTheory.IsSubprobabilityMeasure (ν a)] (x : P.FreeM α) (post : α → ENNReal) :
    wpFold (OpSpec.expectedCharge ν c) x post ≤ costWith c x post

    Under subprobability answers, the expected charge-to-go is at most the worst-case charge-to-go.

    theorem PFunctor.FreeM.wpFold_expectedCharge_le_cost {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) (c : P.A → ENNReal) {α : Type v} [∀ (a : P.A), MeasureTheory.IsSubprobabilityMeasure (ν a)] (x : P.FreeM α) :
    (wpFold (OpSpec.expectedCharge ν c) x fun (x : α) => 0) ≤ cost c x

    Under subprobability answers, the expected charge is at most the worst-case charge.

    The charge of the completed path #

    theorem PFunctor.FreeM.wpFold_lintegral_withPathCharge {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) {α : Type v} [∀ (a : P.A), MeasureTheory.IsProbabilityMeasure (ν a)] {ω : Type w} [AddZeroClass ω] (φ : ω →+ ENNReal) (c : P.A → ω) (x : P.FreeM α) :
    wpFold (OpSpec.lintegral ν) (withPathCharge c x) ⇑φ = wpFold (OpSpec.expectedCharge ν (⇑φ ∘ c)) x fun (x : α) => 0

    Under probability answers, folding the integration spec over a program run with the charge of its path, read through an additive map φ into ℝ≥0∞, gives the expected charge φ ∘ c of the program. The charge of a call is paid before the call in the expected-charge reading and on the completed path in withPathCharge, so the two agree because every answer measure has total mass one.

    theorem PFunctor.FreeM.lintegral_measureFold_withPathCharge {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] (ν : (a : P.A) → MeasureTheory.Measure (P.B a)) {α : Type v} [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] [∀ (a : P.A), MeasureTheory.IsProbabilityMeasure (ν a)] (c : P.A → ENNReal) (x : P.FreeM α) :
    ∫⁻ (s : ENNReal), s ∂measureFold ν (withPathCharge c x) = wpFold (OpSpec.expectedCharge ν c) x fun (x : α) => 0

    Expected charge. Under probability answers over discrete answer types, the expected charge of a program is the integral of the charge of its completed path under the measure fold of withPathCharge c x.

    theorem PFunctor.FreeM.expectedQueryCount_eq_wpFold {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] {α : Type v} [P.AnswerMeasure] [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] (x : P.FreeM α) :

    The expected number of calls on a completed path is the expected charge of the unit charge.

    Expected-cost transfer #

    theorem PFunctor.FreeM.wpFold_expectedCharge_liftM_le {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] {Q : PFunctor.{uA₂, uB₂}} [(b : Q.A) → MeasurableSpace (Q.B b)] [∀ (b : Q.A), DiscreteMeasurableSpace (Q.B b)] (ν : (b : Q.A) → MeasureTheory.Measure (Q.B b)) (d : Q.A → ENNReal) (handler : (a : P.A) → Q.FreeM (P.B a)) {α : Type uB} (c : P.A → ENNReal) (hcall : ∀ (a : P.A), (wpFold (OpSpec.expectedCharge ν d) (handler a) fun (x : P.B a) => 0) ≤ c a) (x : P.FreeM α) (post : α → ENNReal) :
    wpFold (OpSpec.expectedCharge ν d) (FreeM.liftM handler x) post ≤ wpFold (OpSpec.expectedCharge (fun (a : P.A) => measureFold ν (handler a)) c) x post

    Expected-cost transfer. If each implementation of a free handler has expected charge at most c a, then the simulated program's expected charge-to-go is at most the source program's under the charge c, with each call answered by the measure fold of its implementation. Discrete answers on both interfaces make the leaf costs split off each implementation (wpFold_expectedCharge_eq_add_lintegral), which gives the per-call obligation of wpFold_liftM_le.

    theorem PFunctor.FreeM.wpFold_expectedCharge_liftM {P : PFunctor.{uA, uB}} [(a : P.A) → MeasurableSpace (P.B a)] [∀ (a : P.A), DiscreteMeasurableSpace (P.B a)] {Q : PFunctor.{uA₂, uB₂}} [(b : Q.A) → MeasurableSpace (Q.B b)] [∀ (b : Q.A), DiscreteMeasurableSpace (Q.B b)] (ν : (b : Q.A) → MeasureTheory.Measure (Q.B b)) (d : Q.A → ENNReal) (handler : (a : P.A) → Q.FreeM (P.B a)) {α : Type uB} (x : P.FreeM α) (post : α → ENNReal) :
    wpFold (OpSpec.expectedCharge ν d) (FreeM.liftM handler x) post = wpFold (OpSpec.expectedCharge (fun (a : P.A) => measureFold ν (handler a)) fun (a : P.A) => wpFold (OpSpec.expectedCharge ν d) (handler a) fun (x : P.B a) => 0) x post

    Expected-cost transfer, exact form. The simulated program's expected charge-to-go is the source program's, with each call charged the expected charge of its implementation and answered by the measure fold of its implementation.