Determinize

Type inference finds the random draws in a probabilistic program that can be replaced by the means of their distributions. For domain-safe programs of type float[E], the replacement keeps the expected output and does not increase its variance.

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
Histograms of 10 000 runs of each program on one axis: the source spreads from about −2 to 3, the determinized program stays between 0 and 1; both have expected output 1/3. 24 runs of the source lie outside the axis.Sourcevariance 19/45Determinizedvariance 4/45expected output 1/3−2−10123Histograms of 10 000 runs of each program on one axis; both have expected output 1/3.Sourcevariance 19/45Determinizedvariance 4/45expected output 1/3−2−10123

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.

SourceDeterminized
Expected output1/31/3
Variance19/454/45
Variance-reduction factor4.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.

Output of 320 runs of each program against x. The source's runs scatter between −2 and 3; the determinized program's runs lie on the curve x squared. A shaded band marks the runs with x near 0.7. 1 runs of the source lie outside the plot.x near 0.7−2−1012300.51x, the G drawoutputdeterminized: x²1/3, the expected output of bothOutput of 320 runs of each program against x.x near 0.7−2−1012300.51x, the G drawoutputdeterminized: x²1/3, the expectedoutput of both

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):

  1. it returns with the same probability as e;

    returnProbability program.determinize = returnProbability program
    output_mass_preservation
  2. if 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;

    0 < returnProbability program.determinize ∧
      HasExpectation (bigStepMeasure program.determinize) ∧
      returnedExpectation program.determinize = returnedExpectation program
    expectation_preservation
  3. if 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;

    0 < returnProbability program.determinize ∧
      MemLp id 2 (bigStepMeasure program.determinize) ∧
      returnedVariance program.determinize ≤ returnedVariance program
    variance_non_increase
  4. for almost every terminating G trace, it returns e’s mean output given that trace.

    ∀ᵐ trace ∂traceLaw program,
      Integrable id ((traceAndOutputLaw program).condKernel trace) ∧
      (traceAndOutputLaw program.determinize).condKernel trace =
        Measure.dirac (∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace)
    tracewise_soundness

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.