# Generating Functions for Probabilistic Programs

arXiv: https://arxiv.org/abs/2007.06327 · HTML: https://mlsanity.com/paper/2007.06327/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach](https://mlsanity.com/paper/2305.17058/) (2023)

## Abstract (arXiv)

This paper investigates the usage of generating functions (GFs) encoding measures over the program variables for reasoning about discrete probabilistic programs. To that end, we define a denotational GF-transformer semantics for probabilistic while-programs, and show that it instantiates Kozen's seminal distribution transformer semantics. We then study the effective usage of GFs for program analysis. We show that finitely expressible GFs enable checking super-invariants by means of computer algebra tools, and that they can be used to determine termination probabilities. The paper concludes by characterizing a class of -- possibly infinite-state -- programs whose semantics is a rational GF encoding a discrete phase-type distribution.