I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is semicomputable if the probability it assigns to a given string can be computed to arbitratry precision from above or below by a Turing machine. If it can be computed from above and below, it's computable. (formal description here)

Now, I prefer to think of the space of distributions that can be sampled by a probabilistic Turing machine (PTM). That is the distributions $p$ for which a PTM with no input outputs the string $x$ with probability $p(x)$.

I have a (rough) proof that the two classes of distributions the class of lower semicomputable semimeasures and the class of semimeasures samplable by PTM are equivalent: every lower semicomputable semimeasure can be sampled by a PTM and vice versa. However, this seems like the sort of thing that has been worked out ages ago, and is well known to everybody. Can anybody help me with a reference that asserts and proves this equivalence?

edited after @domothorp's comments

  • $\begingroup$ I could not find a convincing reference, so I ended up writing a proof myself. I doubt it's the first, but for what it's worth, it can be found in the appendix of this paper. $\endgroup$ – Peter May 7 '17 at 17:55
  • 1
    $\begingroup$ I wrote a more or less isomorphic question about computable probability measures on Cantor space, and was suggested this. Thanks for writing up this (surely classical?) fact, so I don't have to have an appendix. $\endgroup$ – Ville Salo Jan 9 at 8:09

This answer is not a reference but rather to make some of the notions precise in your question. First, semicomputable does stand for what you say but I think there is a big difference between upper and lower semicomputable - in case of the former I have no clue how you would sample.

Second, do you have a measure or a semimeasure? In a semimeasure the sum of the probabilities is at most 1, so I again do not know how you would sample, as there is no full distribution (of course you can say that you normalize by dividing the sum of the probabilities but that might not be computable, you could never know when to give up a computational path).

Finally, if you have a lower semicomputable measure, then it is in fact equivalent to have a PTM that can sample with this distribution (although we must allow the sampling to run for arbitrarily long, as long as it stops eventually).

I think the best reference on the topic is Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. For another available online see chapter 6.2 of László Lovász: Complexity of Algorithms at http://www.cs.elte.hu/~dom/complexitynew.pdf

| cite | improve this answer | |
  • $\begingroup$ You're absolutely right (I guess this is the problem with rough proofs). The proof only works on lower semicomputable semimeasures. The way to deal with semimeasures that the 'left-over' probability mass is taken up by non-halting programs. It may not be sampling as you'd like in an experimental setting, but you have to account for the halting problem somewhere. I didn't find any reference to the sampling perspective in Li & Vitanyi (I'll have another look though). I'll see if the Lovasz book contains anything useful. $\endgroup$ – Peter May 28 '13 at 12:00
  • $\begingroup$ I don't think there is any reference to sampling in any of these books, I've only suggested them as a reference for semicomputable semimeasures. $\endgroup$ – domotorp May 28 '13 at 15:00

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.