A Model Counter's Guide to Probabilistic Systems
This work offers a systematic guide for researchers in formal methods and AI, but it is incremental as it builds on existing model counting techniques.
The paper systematizes modeling of probabilistic systems for analysis with model counting techniques, providing a conceptual framework for deriving #SAT encodings for probabilistic inference.
In this paper, we systematize the modeling of probabilistic systems for the purpose of analyzing them with model counting techniques. Starting from unbiased coin flips, we show how to model biased coins, correlated coins, and distributions over finite sets. From there, we continue with modeling sequential systems, such as Markov chains, and revisit the relationship between weighted and unweighted model counting. Thereby, this work provides a conceptual framework for deriving #SAT encodings for probabilistic inference.