Discrete Choice in the Presence of Numerical Uncertainties

Numerical uncertainties from noisy inputs or finite-precision roundoff errors are unavoidable on resource-constrained systems. While techniques exist to compute worst-case bounds on these errors for arithmetic operations, these approaches do not generalize to programs which take discrete decisions. In this case, the more interesting quantity is the probability of the program making the wrong decision. In this paper, we study two approaches to compute a guaranteed bound on this probability: 1) exact probabilistic inference and 2) probabilistic static analysis. By themselves, they provide accuracy and scalability, respectively, but unfortunately not at the same time. We propose an extension to the latter approach which allows us to bound the probability tightly and fully automatically while scaling to small but interesting embedded examples.