The signal example
Source (modes inferred)
let x = uniform[G](0, 1) in
let y = gaussian[E](x, 1) in
x * y
Determinized
let x = uniform[G](0, 1) in
let y = mean_gauss(x, 1) in
x * y
The outputs of 10 000 runs of each program. Both have expected output 1/3, marked by the dashed line. The determinized program’s outputs stay between 0 and 1, so its variance is smaller.
| Source | Determinized | |
|---|---|---|
| Expected output | 1/3 | 1/3 |
| Variance | 19/45 | 4/45 |
| Variance-reduction factor | 4.75 |
Why the expected output stays the same: for each value of x, the determinized program returns the source’s average over the noise y.
Runs with x near 0.7: the source’s outputs spread from −1.3 to 1.7. Averaged over y, the source returns 0.7² = 0.49 there, and that is exactly what the determinized program returns.
Each open circle is one run of the source, at its draw of x. Each filled point is the run of the determinized program with the same x; they all lie on the curve x². Averaged over x, both give 1/3; the spread of the circles around the curve is the variance that determinization removes.
320 runs of each program. Open this example in the simulator.
What is proved
For a closed program e (program in Lean) of type float[E] that is domain-safe (DomainSafe), and its determinization (Expr.determinize):
it returns with the same probability as e;
output_mass_preservationreturnProbability program.determinize = returnProbability programif e returns with positive probability and its expectation is defined, the same holds for its determinization, and its expected output given that it returns equals e’s, possibly infinite;
expectation_preservation0 < returnProbability program.determinize ∧ HasExpectation (bigStepMeasure program.determinize) ∧ returnedExpectation program.determinize = returnedExpectation programif e returns with positive probability and has a finite second moment, the same holds for its determinization, and its variance given that it returns is at most e’s;
variance_non_increase0 < returnProbability program.determinize ∧ MemLp id 2 (bigStepMeasure program.determinize) ∧ returnedVariance program.determinize ≤ returnedVariance programfor almost every terminating G trace, it returns e’s mean output given that trace.
tracewise_soundness∀ᵐ trace ∂traceLaw program, Integrable id ((traceAndOutputLaw program).condKernel trace) ∧ (traceAndOutputLaw program.determinize).condKernel trace = Measure.dirac (∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace)
Inference fails only when no assignment of modes agrees with the modes written in the program. Otherwise it returns the assignment with the most E draws: every draw that some valid assignment marks E is marked E (inference_correctness). Domain safety and integrability are premises; typing does not establish them.