# Exact Bayesian Inference for Loopy Probabilistic Programs using Generating Functions

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

## Key facts

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

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

- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)

## Abstract (arXiv)

We present an exact Bayesian inference method for inferring posterior distributions encoded by probabilistic programs featuring possibly unbounded loops. Our method is built on a denotational semantics represented by probability generating functions, which resolves semantic intricacies induced by intertwining discrete probabilistic loops with conditioning (for encoding posterior observations). We implement our method in a tool called Prodigy; it augments existing computer algebra systems with the theory of generating functions for the (semi-)automatic inference and quantitative verification of conditioned probabilistic programs. Experimental results show that Prodigy can handle various infinite-state loopy programs and exhibits comparable performance to state-of-the-art exact inference tools over loop-free benchmarks.