# New Approaches for Almost-Sure Termination of Probabilistic Programs

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

## Key facts

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

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

- [Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving](https://mlsanity.com/paper/2303.09692/) (2023)

## Abstract (arXiv)

We study the almost-sure termination problem for probabilistic programs. First, we show that supermartingales with lower bounds on conditional absolute difference provide a sound approach for the almost-sure termination problem. Moreover, using this approach we can obtain explicit optimal bounds on tail probabilities of non-termination within a given number of steps. Second, we present a new approach based on Central Limit Theorem for the almost-sure termination problem, and show that this approach can establish almost-sure termination of programs which none of the existing approaches can handle. Finally, we discuss algorithmic approaches for the two above methods that lead to automated analysis techniques for almost-sure termination of probabilistic programs.