Probabilistic programming

Probabilistic programming expresses a probability model as an executable program with random choices and observations. Executing the generative part induces a probability distribution; observations then restrict or weight executions, and inference computes the resulting conditional distribution. Program syntax and inference algorithm are separate choices: the same model can be evaluated by rejection sampling, importance sampling or Markov chain Monte Carlo.

A stochastic computation graph is a Directed acyclic graph combining deterministic transformations, random choices and costs. The changing probabilities of random choices contribute score-function gradient estimators, while differentiable deterministic paths contribute pathwise gradients. This accounts for both sources of a parameter's effect on an expected cost.^[ref]

A probabilistic program maps elementary random choices to outputs and observation weights. Its mathematical meaning can be specified by the pushforward measure on outputs, normalized after conditioning when the observation has finite positive mass. Different random-choice spaces can implement the same output law.

Let a model have parameter prior density $\rho$, observation probability $L(\theta )\in [0,1]$ and conditional binary-query probability $h(\theta )\in [0,1]$ after observation. Draw $\theta \sim \rho$ and an independent uniform random variable $U$. Accept exactly when $U<L(\theta )$, then output whether $U<L(\theta )h(\theta )$. At fixed $\theta$, the accepted true and false intervals have lengths $Lh$ and $L(1-h)$. Integrating against $\rho$ and dividing by the positive evidence proves equality of the joint posterior law of parameters and answer. This can replace many latent choices by one auxiliary coordinate. It preserves that joint law, not unreported latent traces. More generally the bounded factor must be a probability or first be divided by a valid common rejection envelope.