Positive Almost-Sure Termination of Polynomial Random Walks

Lorenz Winkler, Laura Kovács

The number of steps until termination of a probabilistic program is a random variable. Probabilistic program termination therefore requires qualitative analysis via almost-sure ter…