Generating Functions Meet Occupation Measures: Invariant Synthesis for Probabilistic Loops (Extended Version)

Darion Haase ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Adrian Gallus, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Lutz Klinkenberg, Tobias Winkler · 2026

Read Generating Functions Meet Occupation Measures: Invariant Synthesis for Probabilistic Loops (Extended Version) by Darion Haase ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Adrian Gallus, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Lutz Klinkenberg, Tobias Winkler (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13991.txt.

Introduction

Darion Haase and co-authors join two tools for exact reasoning about probabilistic loops in 2026. Probabilistic programs need their output distribution inferred from an initial one. Loops and unbounded recursion make that task challenging. Most past work uses statistical approximation to guess the distribution.

The team addresses mathematically exact inference instead. Generating functions meet occupation measures in their invariant synthesis method. Invariants are facts that stay true through each loop pass. Exact answers matter when a program controls money, doses, or safety. Exact proof of what a loop will do beats a good guess in such code. The method gives that proof for a class of loops that was hard to check.

Catalog record

CREATORDarion Haase ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Adrian Gallus, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Lutz Klinkenberg, Tobias Winkler
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE144 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-13991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generating Functions Meet Occupation Measures: Invariant Synthesis for Probabilistic Loops (Extended Version) Darion Haase ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Adrian Gallus, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Lutz Klinkenberg, Tobias Winkler Abstract A fundamental computational task in probabilistic programming is to infer a program’s output (posterior) distribution from a given initial (prior) distribution. This problem is challenging, especially for expressive languages that feature loops or unbounded recursion. While most of the existing literature focuses on statistical approximation, in this paper we address the problem of mathematically exact inference. To achieve this for programs with loops, we rely on a relatively underexplored type of probabilistic loop invariant, which is linked to a loop’s so-called occupation measure . The occupation measure associates program states with their expected number of visits, given the initial distribution. Based on this, we derive the notion of an occupation invariant . Such invariants are essentially dual to probabilistic martingales, the predominant technique for formal probabilistic loop analysis in the literature. A key feature of occupation invariants is that they can take the initial distribution into account and often yield a proof of positive almost sure termination as a by-product. Finally, we present an automatic, template-based invariant synthesis approach for occupation invariants by encoding them as generating functions . The approach is implemented and evaluated on a set of benchmarks. 1 Introduction Probabilistic programs (PPs) are like ordinary programs with the added ability to flip coins or, more generally, sample values from probability distributions. PPs are ubiquitous in modern computing; they appear, for example, in randomized algorithms [ 27 ] , random sampling [ 40 ] , statistical inference routines [ 10 , 22 , 8 ] , cognitive science [ 23 ] , and autonomous systems [ 41 ] . Probabilistic Programs as Measure Transformers. Intuitively, running a PP on a given input produces a probability distribution 1 1 1 Or sub- distribution, if the program does not terminate with probability 1 . over possible outputs. Nearly half a century ago, [ 35 ] [ 35 ] has cast this intuition into a formal (denotational) program semantics, which associates each program C with a function 2 2 2 Notice that \mathcal{K}\,\llbracket{\cdot}\rrbracket operates on general measures , including (sub-)probability distributions as a special case. {\color[rgb]{0.5,0.5,0.5}\overbrace{{\color[rgb]{0,0,0}\mathcal{K}\,\llbracket{C}\rrbracket}}^{\mathclap{\hskip 16.38895pt\text{$\mathcal{K}$ozen's measure transformer semantics of program $C$\hskip 15.94449pt\hskip 15.94449pt}}}}\colon\quad{\color[rgb]{0.5,0.5,0.5}\underbrace{{\color[rgb]{0,0,0}\mathcal{M}\left({\mathsf{States}}\right)}}_{\mathclap{\hskip 8.19447pt\hskip 16.38895pt\hskip 16.38895pt\text{measures over input states}}}}~{}\to{}~{\color[rgb]{0.5,0.5,0.5}\overbrace{{\color[rgb]{0,0,0}\mathcal{M}\left({\mathsf{States}}\right)}}^{\mathclap{\hskip 16.38895pt\hskip 16.38895pt\hskip 16.38895pt\text{measures over output states}}}}~. In this paper we restrict to discrete measures over a countable state space \mathsf{States} . For example, the program in Figure 1 transforms the initial point-mass distribution on state [x\mapsto 1,\,c\mapsto 0] to a distribution where c is geometrically distributed with parameter \nicefrac{{1}}{{2}} (and x=0 with probability 1 ). Notice that Figure 1 uses generating function (GF) notation for distributions. GFs play an important role for our development, which we explain later on page 1 . \!\begin{aligned} &{{\color[rgb]{0,0,0}\!\fatslash\!\!\!\fatslash~~\vphantom{G^{\prime}}{{X}}}}\\ &{\textbf{{{\color[rgb]{0,0,1}while}}}}\,(x=1)\{\\ &\quad\{{{c}:={c+1}}\}\,[{\nicefrac{{1}}{{2}}}]\,\{{{x}:={0}}\}\\ &\}\\ &{{\color[rgb]{0,0,0}\!\fatslash\!\!\!\fatslash~~\vphantom{G^{\prime}}{\tfrac{1}{2}~{}+{}~\tfrac{1}{4}{C}~{}+{}~\tfrac{1}{8}{C}^{2}~{}+{}~\tfrac{1}{16}{C}^{3}\ldots}}}\end{aligned} 1,0 {\color[rgb]{0,0,0}1} 1 1,1 {\color[rgb]{0,0,0}\nicefrac{{1}}{{2}}} 1,2 {\color[rgb]{0,0,0}\nicefrac{{1}}{{4}}} 1,3 {\color[rgb]{0,0,0}\nicefrac{{1}}{{8}}} \ldots 0,0 {\color[rgb]{0,0,0}\nicefrac{{1}}{{2}}} 0,1 {\color[rgb]{0,0,0}\nicefrac{{1}}{{4}}} 0,2 {\color[rgb]{0,0,0}\nicefrac{{1}}{{8}}} 0,3 {\color[rgb]{0,0,0}\nicefrac{{1}}{{16}}} \ldots \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} \nicefrac{{1}}{{2}} Figure 1: Left: A probabilistic loop, annotated with initial and final distributions. The annotations use probability generating functions (PGFs), where indeterminates represent program variables (e.g., X for x ), exponents represent values (variables with value 0 are omitted since {X}^{0}=1 ; exponent 1 is omitted since {X}^{1}=X ), and coefficients represent probabilities (coefficient 1 is also omitted) [ 32 ] . For example, the PGF {X} represents the Dirac distribution where, with probability 1 , x has value 1 and c has value 0 . Right: Markov chain representation of the program (transitions mimic entire loop iterations). The upper part of each state is the variable valuation x,c . The red numbers constitute the occupation measure (expected number of visits). Our Goal: Inference for Loops — Exact and Automatic. Characterizing a program’s exact output distribution is desirable for many applications — yet extremely challenging in general, especially in the presence of loops. The goal of this paper is to push the limits of exact and automatic loop analysis: Problem statement: Given a discrete probabilistic loop {\textbf{{{\color[rgb]{0,0,1}while}}}}\,({\phi})\,\{{C}\} with a distribution \mu over input states, automatically compute an exact representation of the output distribution \mathcal{K}\,\llbracket{{\textbf{{{\color[rgb]{0,0,1}while}}}}\,({\phi})\,\{{C}\}}\rrbracket(\mu) . Two remarks on our problem statement are in order: (1) Due to standard undecidability results for while loops, no complete algorithmic solution exists. We thus provide heuristics covering many instances. (2) Since the final distribution may have infinite support (as in Figure 1 ), we employ closed-form generating functions as a succinct encoding of probability distributions [ 32 ] (details follow). Automatic Reasoning with Kozen’s Definition — Infeasible? [ 35 ] [ 35 ] characterizes the semantics of loops by the functional least fixed point equation 3 3 3 The equation may have multiple solutions; as usual, the least one w.r.t. a suitable order is of interest (see Section 4.2 ). \mathcal{K}\,\llbracket{{\textbf{{{\color[rgb]{0,0,1}while}}}}\,({\phi})\,\{{C}\}}\rrbracket\quad{}={}\quad\mathcal{K}\,\llbracket{{\textbf{{{\color[rgb]{0,0,1}while}}}}\,({\phi})\,\{{C}\}}\rrbracket~{}\circ{}~\mathcal{K}\,\llbracket{C}\rrbracket~{}\circ{}~\llbracket{\phi}\rrbracket\quad{}+{}\quad\llbracket{\neg\phi}\rrbracket~, where \llbracket{\phi}\rrbracket and \llbracket{\neg\phi}\rrbracket filter the incoming distribution according to \phi and \neg\phi , respectively. This equation reflects the intuition that a loop is unaffected by unrolling it once. However, there is a discrepancy between ( 1 ) and our problem statement: Our goal is to determine \mathcal{K}\,\llbracket{{\textbf{{{\color[rgb]{0,0,1}while}}}}\,({\phi})\,\{{C}\}}\rrbracket(\mu) for a given initial distribution \mu — yet ( 1 ) does not depend on such a \mu . In other words, an approach based on solving ( 1 ) would require to reason about all possible initial distributions simultaneously (see [ 32 , 13 , 33 , 34 ] ), whereas we are interested in the solution of the functional equation only at one point, namely at the initial distribution \mu . Occupation Measures to the Rescue. An equivalent but seemingly less well-known 4 4 4 Beyond [ 49 ] , we are not aware of any other work on occupation measures of PPs. characterization of a loop’s output distribution is due to [ 49 ] [ 49 ] . Their technique takes the initial distribution into account and considers the so-called occupation measure (e.g., [ 47 ] ) of the induced stochastic process. The occupation measure associates each program state with its expected number of visits at the loop header . To see how occupation measures help determine the final distribution after the loop, the following observations are key: • For states satisfying the loop guard , the number of visits is a random value in \mathbb{N}\cup\{\infty\} . (Unlike in deterministic programs, a probabilistic loop can return to the same state multiple times without necessarily entering an infinite cycle.) The expected number of visits thus lies in the interval [0,\infty] . • For states violating the loop guard , the situation is different: Such states are visited at most once at the loop header, since the loop terminates immediately upon entering them. Therefore, the expected number of visits to such a terminal state s equals \displaystyle 0\cdot Pr(\text{$s$ is never reached}) \displaystyle\hskip-10.00002pt~{}+{}~1\cdot Pr(\text{$s$ is reached once}) \displaystyle~{}+{}~ \displaystyle{\color[rgb]{0.5,0.5,0.5}\underbrace{{\color[rgb]{0,0,0}2\cdot Pr(\text{$s$ is reached twice})~{}+{}~\ldots}}_{\mathclap{=0}}} \displaystyle\hskip-10.00002pt~{}={}~Pr(\text{$s$ is reached once})~. Consequently, the expected number of visits to s is precisely the probability of ever reaching s — and thus the probability of the loop terminating in s . To summarize, if we denote the occupation measure with \mathit{OM} , then we

Read the complete text