Documentation

Determinize.Theorems

The theorems #

Every theorem of the development is stated here in full, over the definitions in Spec/, and proved by one term from Proof/. A reviewer reads the statements and the definitions they use, not the proofs: the command at the end of this file fails the build unless every theorem depends only on the standard axioms and its statement uses nothing from Proof except proofs.

The first four sections state the paper's theorems, under the paper's names. There e is program, Determinize(e) is program.determinize, the output law μ_e is bigStepMeasure program, the joint law J_e is traceAndOutputLaw program with trace marginal traceLaw program, the conditional law μ_e(· | τ) is (traceAndOutputLaw program).condKernel τ, and q_e, 𝔼_ret[e] and Var_ret[e] are returnProbability, returnedExpectation and returnedVariance. The remaining sections state results the paper does not.

Affinity inference (paper, Section 3) #

theorem Determinize.Theorems.inference_correctness (input : Spec.Paper.Input) :
match Frontend.infer input with | Except.error a => ¬∃ (program : Spec.Paper.Annotated), Spec.Completion input program | Except.ok (program, ty) => input.Matches program ∧ Spec.Paper.Typed [] (Spec.Paper.interpret ↑program) ty ∧ ∀ (completion : Spec.Paper.Annotated), Spec.Completion input completion → Spec.AffinityLE completion program

Inference correctness. Inference fails only when the input has no completion. Otherwise it returns a completion, typed at the returned type, and every completion lies below it.

Determinization (paper, appendix) #

theorem Determinize.Theorems.determinization_preserves_typing (context : List Spec.Paper.Ty) (program : Spec.Paper.Expr) (ty : Spec.Paper.Ty) (typed : Spec.Paper.Typed context program ty) :
Spec.Paper.Typed context program.determinize ty

Determinization preserves typing.

Tracewise soundness (paper, Section 4.2) #

The output marginal of the joint law: erasing terminating traces recovers the ordinary output semantics.

Equality of total masses. The trace marginal, the joint law and the output law have the same total mass: the probability that the program returns.

Trace preservation. Determinization preserves domain safety and the law of terminating G traces.

Tracewise soundness. For almost every terminating G trace, the source's conditional output law has a finite mean and the target's conditional output law is the Dirac mass at that mean. These are Mathlib's regular conditional distributions of the joint laws over their trace marginals, unique up to null sets. No global integrability assumption is required.

Expectation along traces. The expectation conditioned on returning is the integral over the trace law of the conditional expectation of the output's positive part given the trace, minus that of its negative part, divided by the return probability. It is meaningful when the return probability is positive and the expectation conditioned on returning is well-defined.

Global soundness (paper, Section 4.1 and the appendix) #

Output-mass preservation. The source and the target return with the same probability.

Expectation preservation. If the source returns with positive probability and its expectation conditioned on returning is well-defined in the extended reals, then the same holds for the target, and the two expectations agree. They may be infinite.

Variance non-increase. If the source returns with positive probability and its output law has a finite second moment, then the same holds for the target, and the target's variance conditioned on returning is at most the source's.

theorem Determinize.Theorems.convex_function_inequality (program : Spec.Paper.Expr) (typed : Spec.Paper.Typed [] program (Spec.Paper.Ty.float Spec.Paper.Affinity.E)) (safe : Spec.Paper.DomainSafe program) (φ : ℝ → ℝ) (convex : ConvexOn ℝ Set.univ φ) (nonneg : ∀ (value : ℝ), 0 ≤ φ value) :

Convex function inequality. Every nonnegative convex function integrates to at most as much under the target's output law as under the source's. Both sides may be +∞.

Probabilistic type safety. The target is domain-safe, the source either returns or diverges (rejection counts as divergence), and the target returns, and diverges, with the same probabilities as the source.

Trace variance decomposition. If the source returns with positive probability and its output law has a finite second moment, then its variance conditioned on returning is the target's plus the average, over the trace law normalized by the return probability, of the variance of the source's output given the trace. That average is finite.

Further results on returned values (not stated in the paper) #

The first equation of probabilistic_type_safety at either affinity: a domain-safe, real-typed program either returns or continues forever. Rejection counts as divergence.

expectation_preservation for finite expectations. If the source returns with positive probability and its output law is integrable, then the returned laws of source and target are probability laws with finite, equal means.

Determinization preserves the expectation conditioned on acceptance, which is what makes observe meaningful: rejection sampling on the determinized program preserves the conditional expectation. An observation that fails contributes no output mass, so the return probability is the probability of terminating with a real value and every observation on the way succeeding. Because every Boolean is G information, the same traces are rejected in the source and in the target, and both the unnormalized mean and the return probability (output_mass_preservation) are preserved; hence so is their quotient (0 for a program that is always rejected, as 0 / 0 = 0).

The target's output law is the law of the source's conditional mean given the terminating G trace. Only typing and domain safety are assumed: the target's expectation, when defined, is the source's conditional mean averaged over the trace law, whether or not the source has an expectation.

Finite models (not stated in the paper) #

Return, rejection and divergence probabilities of a finite model sum to one.

Every finite reward model has finite output moments, without extra premises.

The theorems above may depend only on the standard axioms, and their statements may rely on Proof only for proofs, which cannot change what they mean: Lean treats any two proofs of a proposition as equal. Following the statements through the declarations they use, stopping at proofs, must reach nothing declared in a Proof module. Otherwise the build fails. The constructors of an inductive are followed through their types even when they are proofs: the constructors of a predicate such as Typed define it.