Syntax and semantics section of this paper on probabilistic programming mentions that the return expression of the program is a function f satisfying $ f : \sum \rightarrow \mathbb{R}^{\inf}_{\geqslant0}$ where $\sum$ is the set of states. I do no not see the need of $\geqslant0$. Why can't the return values be negative?


The function $f$ is a probability sub-distribution, which means that it's a like a probability distribution, only its integral can be less than $1$ (due to the observe statements). The return statement normalizes $f$ back to a bona fide probability distribution.

Outside of quantum computing, probabilities are non-negative.

  • $\begingroup$ How is f a distribution? It is defined to be the return expression, see the Normalized semantics part. $\endgroup$ – nikhil_vyas Apr 3 '15 at 10:05
  • $\begingroup$ The return expression presumably normalizes it so that its values sum to 1, and so you get a probability distribution. In a paper on probabilistic computation, if you see a bunch of non-negative numbers, you can bet they are going to end up as probabilities. $\endgroup$ – Yuval Filmus Apr 3 '15 at 11:01
  • $\begingroup$ the return expression normalizes it so as to remove the cases in which observe is false. This does not imply that f is a distribution. $\endgroup$ – nikhil_vyas Apr 3 '15 at 13:23
  • $\begingroup$ You don't need to remove the cases in which observe is false, since they are already removed by the semantics of the observe statement. The semantics of return is the ratio of two quantities, and the text states that it normalizes $f$, and that you need to normalize because of the observe statements. So my guess is that after normalization you get an actual probability distribution. $\endgroup$ – Yuval Filmus Apr 3 '15 at 18:52
  • $\begingroup$ Have you tried reading the paper and understanding what the semantics mean? Try to understand the semantic rules, and this will make it very clear why the range of $f$ is always non-negative. My guess is that you'll find that my explanation is correct, but even if it isn't, it's all in the semantic rules, and you should be able to find out by understanding them. $\endgroup$ – Yuval Filmus Apr 3 '15 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.