Kaminski, BL;
Katoen, J-P;
Matheja, C;
(2016)
Inferring Covariances for Probabilistic Programs.
In: Agha, G and Van Houdt, B, (eds.)
Quantitative Evaluation of Systems: 13th International Conference, QEST 2016, Quebec City, QC, Canada, August 23-25, 2016, Proceedings.
(pp. pp. 191-206).
Springer: Cham, Switzerland.
Preview |
Text
main.pdf - Accepted Version Download (480kB) | Preview |
Abstract
We study weakest precondition reasoning about the (co)variance of outcomes and the variance of run–times of probabilistic programs with conditioning. For outcomes, we show that approximating (co)variances is computationally more difficult than approximating expected values. In particular, we prove that computing both lower and upper bounds for (co)variances is Σ02–complete. As a consequence, neither lower nor upper bounds are computably enumerable. We therefore present invariant–based techniques that do enable enumeration of both upper and lower bounds, once appropriate invariants are found. Finally, we extend this approach to reasoning about run–time variances.
| Type: | Proceedings paper |
|---|---|
| Title: | Inferring Covariances for Probabilistic Programs |
| Event: | 13th International Conference on Quantitative Evaluation of Systems (QEST) |
| Location: | Quebec City, CANADA |
| Dates: | 23 August 2016 - 25 August 2016 |
| ISBN-13: | 978-3-319-43424-7 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-319-43425-4_14 |
| Publisher version: | https://doi.org/10.1007/978-3-319-43425-4_14 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Probabilistic programs, Covariance, Run–time |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10089695 |
Archive Staff Only
 |
View Item |
